scipy.sparse.csgraph.

csgraph_to_dense

scipy.sparse.csgraph.csgraph_to_dense(csgraph, null_value=0)

Konvertiert eine spärliche Graphenrepräsentation in eine dichte Repräsentation

Hinzugefügt in Version 0.11.0.

Parameter:

csgraphcsr_array, csc_array oder lil_array

Spärliche Repräsentation eines Graphen.

null_valuefloat, optional

Der Wert, der zur Angabe von Nullkanten in der dichten Darstellung verwendet wird. Standard ist 0.

Rückgabe:

graphndarray

Die dichte Repräsentation des spärlichen Graphen.

Hinweise

Bei normalen spärlichen Graphenrepräsentationen liefert der Aufruf von csgraph_to_dense mit null_value=0 ein äquivalentes Ergebnis wie die Verwendung von dichten Formatkonvertierungen im Hauptpaket für spärliche Daten. Wenn die spärlichen Repräsentationen wiederholte Werte aufweisen, unterscheiden sich die Ergebnisse jedoch. Die Werkzeuge in scipy.sparse addieren wiederholte Werte, um einen Endwert zu erhalten. Diese Funktion wählt das Minimum aus wiederholten Werten aus, um einen Endwert zu erhalten. Hier erstellen wir beispielsweise einen gerichteten spärlichen Graphen mit zwei Knoten und mehreren Kanten von Knoten 0 zu Knoten 1 mit den Gewichten 2 und 3. Dies verdeutlicht den Unterschied im Verhalten.

>>> from scipy.sparse import csr_array, csgraph
>>> import numpy as np
>>> data = np.array([2, 3])
>>> indices = np.array([1, 1])
>>> indptr = np.array([0, 2, 2])
>>> M = csr_array((data, indices, indptr), shape=(2, 2))
>>> M.toarray()
array([[0, 5],
       [0, 0]])
>>> csgraph.csgraph_to_dense(M)
array([[0., 2.],
       [0., 0.]])

Der Grund für diesen Unterschied besteht darin, dass eine komprimierte spärliche Graphenrepräsentation mehrere Kanten zwischen beliebigen zwei Knoten darstellen kann. Da die meisten Algorithmen für spärliche Graphen sich mit der Kante mit dem geringsten Kostenwert zwischen zwei beliebigen Knoten befassen, ergibt das Standardverhalten von scipy.sparse, mehrere Gewichte zu summieren, in diesem Kontext keinen Sinn.

Der andere Grund für die Verwendung dieser Routine ist die Möglichkeit, Graphen mit Kanten mit Gewicht Null darzustellen. Betrachten wir das Beispiel eines gerichteten Graphen mit zwei Knoten, der durch eine Kante mit Gewicht Null verbunden ist.

>>> from scipy.sparse import csr_array, csgraph
>>> data = np.array([0.0])
>>> indices = np.array([1])
>>> indptr = np.array([0, 1, 1])
>>> M = csr_array((data, indices, indptr), shape=(2, 2))
>>> M.toarray()
array([[0., 0.],
       [0., 0.]])
>>> csgraph.csgraph_to_dense(M, np.inf)
array([[inf,  0.],
       [inf, inf]])

Im ersten Fall geht die Kante mit Gewicht Null in der dichten Darstellung verloren. Im zweiten Fall können wir einen anderen Nullwert wählen und die wahre Form des Graphen sehen.

Beispiele

Probieren Sie es in Ihrem Browser aus!

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import csgraph_to_dense

>>> graph = csr_array( [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [0, 0, 0, 3],
... [0, 0, 0, 0]
... ])
>>> graph
<Compressed Sparse Row sparse array of dtype 'int64'
    with 4 stored elements and shape (4, 4)>

>>> csgraph_to_dense(graph)
array([[0., 1., 2., 0.],
       [0., 0., 0., 1.],
       [0., 0., 0., 3.],
       [0., 0., 0., 0.]])

ZurückIn Tab öffnen