Skip to content

Instantly share code, notes, and snippets.

@aneksteind
Last active July 8, 2020 17:16
Show Gist options
  • Save aneksteind/d822c2ebebd04adb3d6014e9c0e163be to your computer and use it in GitHub Desktop.
Save aneksteind/d822c2ebebd04adb3d6014e9c0e163be to your computer and use it in GitHub Desktop.
# A naive implementation of Kosajaru's algorithm to align with
# Hassam Uddin's pseudocode (https://hassamuddin.com/blog/kosaraju/)
# Other (better) Python implementations can be found elsewhere:
# - https://www.geeksforgeeks.org/strongly-connected-components/
# - https://rosettacode.org/wiki/Kosaraju#Python
s = None
order = []
explored = set()
leader = {}
def dfs_loop(G, seq=None):
global s, explored
nodes = G if seq is None else seq
for node in nodes:
if node not in explored:
explored.add(node)
s = node
dfs(G, node)
explored = set()
def dfs(G, v):
global order, explored
explored.add(v)
leader[v] = s
for w in G[v]:
if w not in explored:
dfs(G, w)
order = [v] + order
def reverse(G):
R = {node:[] for node in G}
for source in G:
for dest in G[source]:
R[dest].append(source)
return R
def kosaraju(G):
global leader, order, s, explored
dfs_loop(reverse(G))
dfs_loop(G, seq=order)
leaders = [leader[node] for node in G]
leader = {}
order = []
s = None
explored = set()
return leaders
if __name__ == '__main__':
G = {
1:[2],
2:[3],
3:[1,4,5,6],
4:[9,10],
5:[6,7],
6:[7],
7:[8],
8:[5],
9:[11],
10:[8,9],
11:[10]
}
# from https://rosettacode.org/wiki/Kosaraju#Python
H = {
0:[1],
1:[2],
2:[0],
3:[1,2,4],
4:[3,5],
5:[2,6],
6:[5],
7:[4,6,7]
}
print(kosaraju(G))
print(kosaraju(H))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment