kosaraju.py

from graph import *

def kosaraju(g):
    def dfs(g, start, s, visited=set()):
        for n in g.vertex_out[start]:
            if n in visited: continue
            visited.add(n)
            dfs(g, n, s, visited)
        s.append(start)
    from random import sample
    s = []
    all_vertices = set(g.vertex_in.keys()) | set(g.vertex_out.keys())
    while True:
        ss = set(s)
        if all_vertices.issubset(ss): break
        rand_v = sample(all_vertices - ss, 1)[0]
        dfs(g, rand_v, s)
    gt = DirectedGraph({(edge[1], edge[0]): label for edge, label in g.items()})
    while s:
        v = s.pop()
        comp = set()
        dfs(gt, v, [], comp)
        print('comp: %s' % comp)
        for v in comp: del gt[v]
        s = [e for e in s if e not in comp] # !!