kosaraju.py

# 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))