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

Added 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)
  (np.int32(0), np.int32(1))        1
  (np.int32(0), np.int32(2))        1
  (np.int32(1), np.int32(2))        1
  (np.int32(3), np.int32(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)