Strongly connected components algorithm

Question

In my Python application, I am using Tarjan's algorithm to compute strongly connected components. Unfortunately, it shows up under profiling as one of the top functions in my application (at least under cPython, I haven't figured out how to profile under Pypy yet).

I've looked at the code, but I don't see any obvious performance mistakes, and I can't figure out how to make it faster. Any suggestions?

Note: The profiler reports a lot of time spent inside the function, so it's not just a matter of slow callbacks.

def tarjanSCC(roots, getChildren):
 """Return a list of strongly connected components in a graph. If getParents is passed instead of getChildren, the result will be topologically sorted.
 roots - list of root nodes to search from
 getChildren - function which returns children of a given node
 """
 sccs = []
 indexCounter = itertools.count()
 index = {}
 lowlink = {}
 removed = set()
 subtree = []
 #Use iterative version to avoid stack limits for large datasets
 stack = [(node, 0) for node in roots]
 while stack:
 current, state = stack.pop()
 if state == 0: #before recursing
 if current not in index: #if it's in index, it was already visited (possibly earlier on the current search stack)
 lowlink[current] = index[current] = next(indexCounter)
 children = [child for child in getChildren(current) if child not in removed]
 subtree.append(current)
 stack.append((current, 1))
 stack.extend((child, 0) for child in children)
 else: #after recursing
 children = [child for child in getChildren(current) if child not in removed]
 for child in children:
 if index[child] <= index[current]: #backedge (or selfedge)
 lowlink[current] = min(lowlink[current], index[child])
 else:
 lowlink[current] = min(lowlink[current], lowlink[child])
 assert(lowlink[current] <= index[current])
 if index[current] == lowlink[current]:
 scc = []
 while not scc or scc[-1] != current:
 scc.append(subtree.pop())
 sccs.append(tuple(scc))
 removed.update(scc)
 return sccs

Answer 1

• You iterate twice over the children in both branches. Avoid that by combining these lines

  children = [child for child in getChildren(current) if child not in removed]
  stack.extend((child, 0) for child in children)
  

  to

  stack.extend((child, 0) for child in getChildren(current) if child not in removed)
  

  and these

  children = [child for child in getChildren(current) if child not in removed]
  for child in children:
  

  to

  for child in getChildren(current):
   if child not in removed:
  

---

• Instead of looping in Python and moving one item at a time here

   scc = []
   while not scc or scc[-1] != current:
   scc.append(subtree.pop())
   sccs.append(tuple(scc))
  

  try to use slicing like this. A possible disadvantage is that index searches from the beginning.

   i = subtree.index(current)
   scc = tuple(reversed(subtree[i:]))
   del subtree[i:]
   sccs.append(scc)
  

• Use local variables to reduce dictionary lookups. You can also bind methods such as stack.pop to local variables to avoid attribute lookup inside the loop.

• Also to reduce dictionary lookups, you could combine index and lowlink dictionaries. Put the pair of values in as a tuple or a list to take advantage of unpacking into local variables:

  next_index = next(indexCounter)
  index[current] = [next_index, next_index]
  ...
  index_current, lowlink_current = index[current]