Robust topological sorting and Tarjan's algorithm in Python

The Strongly Connected Components of a directed graph are subsets of nodes such that each node within a subset can be reached from each other node. Tarjan's algorithm can identify these components efficiently (thanks njh for finding this algorithm).

By identifying strongly connected components ahead of time we can create a topological sorting algorithm that does the best it can in the presence of cycles.

Here is an implementation in Python:

sort.py

Here are some things you might use this for:

Install packages with circular dependencies in the best order you can.

Work out in which order a set of equations must be solved, and which must be solved simultaneously.

In a revision control system align as well as possible many versions of a file. (This is basically what I am using this for, but with DNA.)

Note 11/1/2012: Dries Verdegem reports that the above Strongly Connected Components code has a bug in it, and offers this version, which has withstood heavy testing (the graph of all Wikipedia articles!):

tarjan.py

I place the code linked to on this page in the public domain. Use it as you will.