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:

Here are some things you might use this for:

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!):

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