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. Nodes i and j are weakly connected if only one of these paths exists. 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 lengthN 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)