5
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$
  • 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]
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.