Running DFS on a Large Chart

Question

I am trying to find Strongly connected components in a large graph that implements the Kosaraju algorithm. This requires running DFS on the chart in reverse order, and then forward. If you are interested, the list of edges for this graph is here: https://dl.dropboxusercontent.com/u/28024296/SCC.txt.tar.gz

I cannot implement this recursively in Python, it exceeds its recursive limits and crashes if I increase them. I am trying to implement through iteration.

Below is my code for 1. Loading the graph in reverse order into the dictionary and 2. Initializing DFS on each of them node from n → 1.

This code is great for small sample graphs, but just doesn't run for this large graph. I get it ineffective, but all the tips on how to make it work?

def reverseFileLoader():

    graph = collections.defaultdict(lambda: {'g': [], 's': False, 't': None, 'u': None })
    for line in open('/home/edd91/Documents/SCC.txt'):
        k, v = map(int, line.split())
        graph[v]['g'].append(k)

    return graph

def DFS(graph, i):
    global t
    global source
    stack = []
    seen = []
    seen.append(i)
    stack.append(i)

    while stack:
        s = stack[-1]
        j = len(graph[s]['g']) - 1
        h = 0
        while (j >= 0):
            if graph[s]['g'][j] not in seen and graph[graph[s]['g'][j]]['t'] == None:
                seen.append(graph[s]['g'][j])
                stack.append(graph[s]['g'][j])
                h += 1
            j -= 1

        if h == 0:
            if graph[s]['t'] == None:
                t += 1
                graph[s]['u'] = source
                graph[s]['t'] = t 
            stack.pop()

def DFSLoop(graph):
    global t
    t = 0
    global source
    source = None
    i = len(graph)
    while (i >= 1):
        print "running for " + str(i)
        source = i
        DFS(graph, i)
        i -= 1

Answer 1

Kosaraju, , , , , O (1). O (n) . seen ( , ).

, ,

• seen = [] seen = set()
• seen.append(...) seen.add(...).