# Strongly connected components algorithm

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 = {}
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)
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)
else:

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

sccs.append(tuple(scc))
removed.update(scc)
return sccs


• 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]
...