Running DFS on large graph
<p>I am trying to find Strongly Connected Components in a large graph implementing Kosaraju's algorithm. It requires running a DFS on a graph in reverse, and then forward. If you're interested the list of edges for this graph are here: <a href="https://dl.dropboxusercontent.com/u/28024296/SCC.txt.tar.gz" rel="nofollow">https://dl.dropboxusercontent.com/u/28024296/SCC.txt.tar.gz</a></p>

<p>I can't implement this recursively in Python, it exceeds its recursive limits and crashes if I increase them. I'm trying to implement through iteration.</p>

<p>Below is my code for 1. Loading the graph in reverse into a Dictionary, and 2. Running the DFS on it iteratively for each node from n -> 1.</p>

<p>This code runs perfect for small sample graphs but just doesn't run for this large graph. I get it's inefficient but any tips on how to make it work?</p>

<pre><code>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 &gt;= 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 &gt;= 1):
        print "running for " + str(i)
        source = i
        DFS(graph, i)
        i -= 1
</code></pre>

<p>Kosaraju's algorithm probably requires that checking whether an element has been seen is an O(1) operation. But your seen data structure has O(n) time membership testing. Converting <code>seen</code> from a list to a set makes the code execute in a few seconds on my system (after also removing the prints which took up most of the remaining execution time).</p>

<p>For completeness the changes you need to make are</p>

<ul>
<li>Change <code>seen = []</code> to <code>seen = set()</code></li>
<li>Change each  <code>seen.append(...)</code> to <code>seen.add(...)</code>.</li>
</ul>

python graph graph-algorithm