scipy.sparse.csgraph.

connected_components

scipy.sparse.csgraph.connected_components(csgraph, directed=True, connection='weak', return_labels=True)

Analysiert die verbundenen Komponenten eines dünnbesetzten Graphen

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder dünnbesetzte Array oder Matrix

Die N x N Matrix, die den dünnbesetzten Graphen repräsentiert. Die Eingabe csgraph wird für die Berechnung in das csr-Format konvertiert.

directedbool, optional

Wenn True (Standard), dann wird auf einem gerichteten Graphen gearbeitet: es wird nur von Punkt i zu Punkt j entlang der Pfade csgraph[i, j] navigiert. Wenn False, dann wird der kürzeste Pfad in einem ungerichteten Graphen gesucht: der Algorithmus kann von Punkt i zu j entlang csgraph[i, j] oder csgraph[j, i] fortschreiten.

connectionstr, optional

[‘weak’|’strong’]. Für gerichtete Graphen wird die Art der Verbindung verwendet. Knoten i und j sind stark verbunden, wenn ein Pfad sowohl von i nach j als auch von j nach i existiert. Ein gerichteter Graph ist schwach verbunden, wenn das Ersetzen aller seiner gerichteten Kanten durch ungerichtete Kanten einen verbundenen (ungerichteten) Graphen ergibt. Wenn directed == False, wird dieses Schlüsselwort nicht referenziert.

return_labelsbool, optional

Wenn True (Standard), werden die Labels für jede der verbundenen Komponenten zurückgegeben.

Rückgabe:

n_components: int

Die Anzahl der verbundenen Komponenten.

labels: ndarray

Das Längen-N-Array der Labels der verbundenen Komponenten.

Referenzen

[1]

D. J. Pearce, „An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph“, Technical Report, 2005

Beispiele

Probieren Sie es in Ihrem Browser aus!

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

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

>>> n_components, labels = connected_components(csgraph=graph, directed=False, return_labels=True)
>>> n_components
2
>>> labels
array([0, 0, 0, 1, 1], dtype=int32)

ZurückIn Tab öffnen