scipy.sparse.csgraph.connected_components¶
-
scipy.sparse.csgraph.connected_components(csgraph, directed=True, connection='weak', return_labels=True)¶ Analyze the connected components of a sparse graph
New in version 0.11.0.
- Parameters
- csgrapharray_like or sparse matrix
The N x N matrix representing the compressed sparse graph. The input csgraph will be converted to csr format for the calculation.
- directedbool, optional
If True (default), then operate on a directed graph: only move from point i to point j along paths csgraph[i, j]. If False, then find the shortest path on an undirected graph: the algorithm can progress from point i to j along csgraph[i, j] or csgraph[j, i].
- connectionstr, optional
[‘weak’|’strong’]. For directed graphs, the type of connection to use. Nodes i and j are strongly connected if a path exists both from i to j and from j to i. A directed graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. If directed == False, this keyword is not referenced.
- return_labelsbool, optional
If True (default), then return the labels for each of the connected components.
- Returns
- n_components: int
The number of connected components.
- labels: ndarray
The length-N array of labels of the connected components.
References
- 1
D. J. Pearce, “An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph”, Technical Report, 2005
Examples
>>> from scipy.sparse import csr_matrix >>> 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_matrix(graph) >>> print(graph) (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)