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: csgraph : array_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.
directed : bool, 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].
connection : str, 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_labels : bool, 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
[R14] D. J. Pearce, “An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph”, Technical Report, 2005