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]