python - Running DFS on large graph -

i trying find connected components in large graph implementing kosaraju's algorithm. requires running dfs on graph in reverse, , forward. if you're interested list of edges graph here: https://dl.dropboxusercontent.com/u/28024296/scc.txt.tar.gz

i can't implement recursively in python, exceeds recursive limits , crashes if increase them. i'm trying implement through iteration.

below code 1. loading graph in reverse dictionary, , 2. running dfs on iteratively each node n -> 1.

this code runs perfect small sample graphs doesn't run large graph. it's inefficient tips on how make work?

def reversefileloader():      graph = collections.defaultdict(lambda: {'g': [], 's': false, 't': none, 'u': none })     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 , 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     = len(graph)     while (i >= 1):         print "running " + str(i)         source =         dfs(graph, i)         -= 1 

kosaraju's algorithm requires checking whether element has been seen o(1) operation. seen data structure has o(n) time membership testing. converting seen list set makes code execute in few seconds on system (after removing prints took of remaining execution time).

for completeness changes need make are

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