Topological sort

When I left academia [1] my first job was working as a programmer. I was very impressed by a new programmer we hired who hit the ground running. His first week he looked at some problem we were working on and said Oh, you need a topological sort." I'd never heard of a topological sort and it sounded exotic. What could this have to do with topology?!

A topological sort of a directed graph lists source nodes before target nodes. For example, if there is a directed edge from A to B and from C to A, then the nodes would be list C, A, B. It's just a way of listing items in a directed graph so that no item in the list points to an item earlier in the list. All arrows point forward.

This is not exotic at all. It's something you've likely done, maybe by hand. As pointed out in the comments, the make utility does this, compiling source files in the order that they're needed [2].

Where does topology come in? Imagine your directed graph made of beads and strings. You want to pick up the graph by some bead so that all beads are higher than the beads they point to. It's topological in the sense that you don't need to preserve the geometry of the graph, only its connectivity.

tsort

The Unix utility tsort will do a topological sort. The input to the utility is a text file with two items per line, separated by white space, indicating a directed edge from the first item to the second.

Example

Here is a thumbnail image of a graph of relationships between special functions. See this page for a full-sized image and an explanation of what the arrows represent.

I took the GraphViz file used to create the graph and formatted it for tsort. Then I randomly shuffled the file with shuf.

 Gegenbauer_polynomials Legendre_polynomials Gegenbauer_polynomials Chebyshev_polynomials_Second_kind Hypergeometric_2F1 Jacobi_polynomials Error_function Fresnel_S ... Hypergeometric_1F1 Error_function

The lines are not sorted topologically because, for example, the Gegenbauer polynomials are special cases of the Hypergeometric 2F1 functions, so Hypergeometric 2F1 should be listed before Gegenbauer polynomials.

When I ran the shuffled file through tsort I got

 Elliptic_F Hypergeometric_2F1 Elliptic_E Hypergeometric_1F1 .... Beta

and now in this list more general functions always come before special cases.

Related posts

• Insertion sort as a fold
• Quick sort and prime numbers
• Six degrees of Kevin Bacon, Paul Erdos, and Wikipedia

[1] After a postdoc at Vanderbilt, I took a job as a programmer. I got the job because they needed a programmer who knew some DSP. A few years later I got a job at MD Anderson Cancer Center managing a group of programmers. It's fuzzy whether my time at MDACC should be considered time in Academia. My responsibilities there were sometimes academic-writing journal articles, teaching classes-and sometimes not-developing software and managing software developers.

[2] The make software can be used to run any directed acyclic graph of tasks, but is most often used to compile software.

The post Topological sort first appeared on John D. Cook.