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 array or 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_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)