SCC.py

from sys import argv
from collections import defaultdict, deque

finishing_time = 0 # number of nodes processed so far; for finishing times in first pass
finishing_order = []
scc_sizes = []

def stack_DFS(graph, seen, start, pass_one=True, pass_two=False):
# pass_one tracks finishing time; pass_two counts scc sizes
    global finishing_time, finishing_order, scc_sizes

    stack = deque([start])
    seen[start - 1] = True
    if pass_two:
        scc_size = 1

    while stack:
        last = stack[-1]
        adj_verts = graph[last]
        if adj_verts:
            # If possible, find an adjacent vertex which hasn't been explored, and push it
            adj_vert = adj_verts.pop()
            while seen[adj_vert - 1] and adj_verts:
                adj_vert = adj_verts.pop()

            if not seen[adj_vert - 1]:
                stack.append(adj_vert)
                seen[adj_vert - 1] = True
                if pass_two:
                    scc_size += 1
            else: # Last vertex has no more adjacent vertices to explore, so pop it
                stack.pop()
                if pass_one:
                    finishing_time += 1
                    finishing_order.append(last)
        else:
            stack.pop()
            if pass_one:
                finishing_time += 1
                finishing_order.append(last)

    if pass_two:
        scc_sizes.append(scc_size)

def DFS_loop(G, seen, order, pass_one=True, pass_two=False):
    for i in order:
        if not seen[i - 1]:
            stack_DFS(G, seen, i, pass_one, pass_two)

def reverse_graph(G):
    d = defaultdict(list)
    for vertex in G:
        for v in G[vertex]:
            d[v].append(vertex)
        # Ensure that sinks are not lost on reversal
        if vertex not in d:
            d[vertex] = []
    return d

def get_graph(filename):
    # Read (not necessarily ordered) list of head-to-tail edges into adjacency list
    G = defaultdict(list)
    with open(filename) as f:
        for line in f:
            head, tail = map(int, line.split())
            G[head].append(tail)
            # Ensure that sinks are entered
            if tail not in G:
                G[tail] = []
    print "Created adjacency list."
    return G

def main():
    # Compute the sizes of the five largest strongly connected components of a directed graph.
    # Graph initially represented as list of edges.
    filename = argv[1]
    G = get_graph(filename)

    # Run DFS_loop on reversed graph to identify leader vertices for second pass
    seen = [False] * len(G)
    order = xrange(len(G), 0, -1)
    G_rev = reverse_graph(G)
    DFS_loop(G_rev, seen, order)

    # Run DFS_loop on original graph, using vertex order derived from first pass
    order = reversed(finishing_order)
    seen = [False] * len(G)
    DFS_loop(G, seen, order, False, True)

    scc_sizes.sort()
    scc_sizes.reverse()
    print "number of SCCs:", len(scc_sizes)
    print "Sizes of largest strongly connected components:", scc_sizes[:5]
    print "sum of SCC sizes:", sum(scc_sizes)

if __name__ == '__main__':
    main()