Kosaraju's SCC

scc.py

'''
Gabriel C. 2015
 
Kosaraju's algorithm for strongly connected components in a DAG
'''

import sys
import resource

sys.setrecursionlimit(10 ** 6)
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, 2 ** 30))

def read_file(filename):
    graph = {}
    for line in open(filename):
        vs = [int(v) for v in line.strip().split(" ")]
        if vs[0] not in graph:
            graph[vs[0]] = set()

        graph[vs[0]].add(vs[1])

    return graph

def revert_graph(graph):
    rev_graph = {}

    for from_node in graph:
        for to_node in graph[from_node]:
            if to_node not in rev_graph:
                rev_graph[to_node] = set()

            rev_graph[to_node].add(from_node)

    return rev_graph

t = 0
leader = None

def dfs(graph, node, visited, finishing_times, leaders):
    global t
    global leader
    visited.add(node)
    leaders[node] = leader

    if node in graph:
        for v in graph[node] - visited:
            if v not in visited:
                dfs(graph, v, visited, finishing_times, leaders)

    t += 1
    finishing_times[node] = t

def dfs_loop(graph):
    n = max([v for v in graph] + [v2 for v in graph for v2 in graph[v]])
    visited = set()
    finishing_times = {}
    leaders = {}
    global leader
    global t
    t = 0
    leader = None
    reverted_graph = revert_graph(graph)

    for i in xrange(n, 0, -1):
        if i not in visited:
            dfs(reverted_graph, i, visited, finishing_times, leaders)

    visited = set()
    rev_f = {v: k for k, v in finishing_times.items()}
    
    for i in xrange(n, 0, -1):
        if rev_f[i] not in visited:
            leader = rev_f[i]
            dfs(graph, rev_f[i], visited, finishing_times, leaders)

    return leaders

def max_leaders(leaders):
    count_per_leader = {}
    
    for leader in leaders.values():
        if leader not in count_per_leader:
            count_per_leader[leader] = 1
        else:
            count_per_leader[leader] += 1

    counts = [v for k, v in count_per_leader.items()]
    counts.sort()
    counts.reverse()
    counts = [str(v) for v in counts] + ['0'] * (5 - len(counts))

    return ','.join(counts[:5])

def strongly_connected_components(graph):
    return max_leaders(dfs_loop(graph))

'''
assert(strongly_connected_components(read_file("scc54321.txt")) == "5,4,3,2,1")
assert(strongly_connected_components(read_file("scc32221.txt")) == "3,2,2,2,1")
assert(strongly_connected_components(read_file("scc61100.txt")) == "6,1,1,1,1")
assert(strongly_connected_components(read_file("scc63210.txt")) == "6,3,2,1,0")
assert(strongly_connected_components(read_file("scc71000.txt")) == "7,1,0,0,0")
assert(strongly_connected_components(read_file("scc33110.txt")) == "3,3,1,1,0")
assert(strongly_connected_components(read_file("scc33200.txt")) == "3,3,2,0,0")
assert(strongly_connected_components(read_file("scc33300.txt")) == "3,3,3,0,0")
'''

#print strongly_connected_components(read_file('SCC.txt'))