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