pygraphs.bfs_components#

bfs_components(graph, *, strongly_connected=False, scc_mode='tarjan', _skip_check=False)[source]#

Extract the connected components (or strongly connected components if strongly_connected=True) of the graph.

Note

Vertices A and B are in the same component if :

  • connected component: there is a path from vertex A to vertex B OR from vertex B to vertex A.

  • strongly connected component : there is a path from vertex A to vertex B AND from vertex B to vertex A.

Parameters:

  • graph (Graph) – An instance of the Graph class representing the graph to be traversed.

  • strongly_connected (bool (default: False)) – Compute the strongly connected components instead.

  • scc_mode (str (default: 'tarjan')) – The efficient method to compute strongly connected components. Available options are 'tarjan' or 'kosaraju'.

  • _skip_check (bool)

Returns:

A list of lists, where each inner list represents a connected component of the graph. Each connected component is a list of vertex indices that are reachable from each other. If the graph is empty, an empty list is returned.

Return type:

List[List[int]]

Notes

For strongly_connected=False, considering the undirected graph associated with the provided, a BFS is performed starting from an unvisited vertex, and all vertices that are reachable from that vertex are added to the same component.

For strongly_connected=True, call Tarjan or Kosaraju algorithm.

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_reachable()

Perform a breadth-first search (BFS) to extract the vertices that are reachable from a starting vertex in the graph.

Examples

Create a simple disconnected graph of 7 vertices and compute the connected components of the graph.

../../_images/graph.png

Disconnected graph with 7 vertices for BFS example. The graph has 2 connected components: {0, 1, 2, 3, 4} and {5, 6}.#

1from pygraphs import bfs_components, Graph
2
3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
4graph = Graph.from_adjacency(graph)
5
6components = bfs_components(graph)
7print(components)

[[0, 1, 2, 3, 4], [5, 6]]

This method can be applied for directed graphs as well, where the adjacency list represents the outgoing neighbors of each vertex.

../../_images/graph_directed.png

Directed graph with 7 vertices for BFS example. The graph has 2 connected components: {0, 1, 2, 3, 4}, {5,6} using strongly_connected=False and 4 connected components: {0, 1, 2}, {3, 4}, {5} and {6} using strongly_connected=True.#

1from pygraphs import bfs_components, Graph
2
3graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
4graph = Graph.from_adjacency(graph)
5
6components = bfs_components(graph, strongly_connected=False)
7print(components)

[[0, 1, 2, 3, 4], [5, 6]]

1from pygraphs import bfs_components, Graph
2
3graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
4graph = Graph.from_adjacency(graph)
5
6components = bfs_components(graph, strongly_connected=True)
7print(components)

[[0, 1, 2], [3, 4], [5], [6]]