Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.strongly_connected_components

strongly_connected_components(graph, /)

Find the strongly connected components in a directed graph

A strongly connected component (SCC) is a maximal subset of vertices such that every vertex is reachable from every other vertex within that subset.

This function is implemented using Kosaraju’s algorithm.

>>> G = rx.PyDiGraph()
>>> G.extend_from_edge_list([(0, 1), (1, 2), (2, 0), (3, 4)])
>>> rx.strongly_connected_components(G)
[[4], [3], [0, 1, 2]]

See also [weakly_connected_components].

For undirected graphs, see [connected_components].

Parameters:

graph (PyDiGraph) – The directed graph to find the strongly connected components in

Returns:

A list of lists of node indices of strongly connected components

Return type:

list[list[int]]