graphs.strongly_connected_components¶

Finding strongly connected components in directed graph

Attributes¶

`test_graph_1`
`test_graph_2`

`find_components`(→ list[int])	Use depth first search to find strongly connected
`strongly_connected_components`(→ list[list[int]])	This function takes graph as a parameter
`topology_sort`(→ list[int])	Use depth first search to sort graph

graphs.strongly_connected_components.find_components(reversed_graph: dict[int, list[int]], vert: int, visited: list[bool]) → list[int]¶: Use depth first search to find strongly connected vertices. Now graph is reversed >>> find_components({0: [1], 1: [2], 2: [0]}, 0, 5 * [False]) [0, 1, 2] >>> find_components({0: [2], 1: [0], 2: [0, 1]}, 0, 6 * [False]) [0, 2, 1]

graphs.strongly_connected_components.strongly_connected_components(graph: dict[int, list[int]]) → list[list[int]]¶: This function takes graph as a parameter and then returns the list of strongly connected components >>> strongly_connected_components(test_graph_1) [[0, 1, 2], [3], [4]] >>> strongly_connected_components(test_graph_2) [[0, 2, 1], [3, 5, 4]]

graphs.strongly_connected_components.topology_sort(graph: dict[int, list[int]], vert: int, visited: list[bool]) → list[int]¶: Use depth first search to sort graph At this time graph is the same as input >>> topology_sort(test_graph_1, 0, 5 * [False]) [1, 2, 4, 3, 0] >>> topology_sort(test_graph_2, 0, 6 * [False]) [2, 1, 5, 4, 3, 0]