Tarjan's algo for finding strongly connected components in a directed graph Uses two main attributes of each node to track reachability, the index of that node within a component(index), and the lowest index reachable from that node(lowlink). We then perform a dfs of the each comp
(g)
| 2 | |
| 3 | |
| 4 | def tarjan(g): |
| 5 | """ |
| 6 | Tarjan's algo for finding strongly connected components in a directed graph |
| 7 | |
| 8 | Uses two main attributes of each node to track reachability, the index of that node within a component(index), |
| 9 | and the lowest index reachable from that node(lowlink). |
| 10 | |
| 11 | We then perform a dfs of the each component making sure to update these parameters for each node and saving the |
| 12 | nodes we visit on the way. |
| 13 | |
| 14 | If ever we find that the lowest reachable node from a current node is equal to the index of the current node then it |
| 15 | must be the root of a strongly connected component and so we save it and it's equireachable vertices as a strongly |
| 16 | connected component. |
| 17 | |
| 18 | Complexity: strong_connect() is called at most once for each node and has a complexity of O(|E|) as it is DFS. |
| 19 | Therefore this has complexity O(|V| + |E|) for a graph G = (V, E) |
| 20 | |
| 21 | """ |
| 22 | |
| 23 | n = len(g) |
| 24 | stack = deque() |
| 25 | on_stack = [False for _ in range(n)] |
| 26 | index_of = [-1 for _ in range(n)] |
| 27 | lowlink_of = index_of[:] |
| 28 | |
| 29 | def strong_connect(v, index, components): |
| 30 | index_of[v] = index # the number when this node is seen |
| 31 | lowlink_of[v] = index # lowest rank node reachable from here |
| 32 | index += 1 |
| 33 | stack.append(v) |
| 34 | on_stack[v] = True |
| 35 | |
| 36 | for w in g[v]: |
| 37 | if index_of[w] == -1: |
| 38 | index = strong_connect(w, index, components) |
| 39 | lowlink_of[v] = lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v] |
| 40 | elif on_stack[w]: |
| 41 | lowlink_of[v] = lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v] |
| 42 | |
| 43 | if lowlink_of[v] == index_of[v]: |
| 44 | component = [] |
| 45 | w = stack.pop() |
| 46 | on_stack[w] = False |
| 47 | component.append(w) |
| 48 | while w != v: |
| 49 | w = stack.pop() |
| 50 | on_stack[w] = False |
| 51 | component.append(w) |
| 52 | components.append(component) |
| 53 | return index |
| 54 | |
| 55 | components = [] |
| 56 | for v in range(n): |
| 57 | if index_of[v] == -1: |
| 58 | strong_connect(v, 0, components) |
| 59 | |
| 60 | return components |
| 61 |
no test coverage detected