strongly_connected_components.py

"""
https://en.wikipedia.org/wiki/Strongly_connected_component

Finding strongly connected components in directed graph

"""

test_graph_1= {0: [2, 3], 1: [0], 2: [1], 3: [4], 4: []}

test_graph_2= {0: [1, 2, 3], 1: [2], 2: [0], 3: [4], 4: [5], 5: [3]}


deftopology_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]
 """

visited[vert] =True
order= []

forneighbouringraph[vert]:
ifnotvisited[neighbour]:
order+=topology_sort(graph, neighbour, visited)

order.append(vert)

returnorder


deffind_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]
 """

visited[vert] =True
component= [vert]

forneighbourinreversed_graph[vert]:
ifnotvisited[neighbour]:
component+=find_components(reversed_graph, neighbour, visited)

returncomponent


defstrongly_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]]
 """

visited=len(graph) * [False]
reversed_graph: dict[int, list[int]] = {vert: [] forvertinrange(len(graph))}

forvert, neighboursingraph.items():
forneighbourinneighbours:
reversed_graph[neighbour].append(vert)

order= []
fori, was_visitedinenumerate(visited):
ifnotwas_visited:
order+=topology_sort(graph, i, visited)

components_list= []
visited=len(graph) * [False]

foriinrange(len(graph)):
vert=order[len(graph) -i-1]
ifnotvisited[vert]:
component=find_components(reversed_graph, vert, visited)
components_list.append(component)

returncomponents_list