What is a topological ordering?
May 09, 2019
Now that we know the basics of directed acyclic graphs, we’re going to move to a more specialized data structure, one that is wholly derivable from a DAG.
A topological ordering of a directed graph G = (V, E) is a linear ordering such that for every directed edge u -> v in E, u precedes v (in the linear ordering).
For those of you who need an algorithm to figure out how to put your clothes on in the morning, you’re saved! Let’s define the task dependency graph for getting dressed. An edge x -> y in this graph means “you must put on x before y“, i.e. socks -> shoes is an edge, because you must put on your socks before your shoes.
Without going into the details of how the topological sorting algorithm works (algorithm here), let’s run it on the graph.
We’ll use the
tsort command, which has this implemented already implemented on most Unix based platforms. (As you can see below, we just provide space-separated tuples representing all edges in the graph).
tsort <<EOFunderwear shoessocks shoesunderwear pantspants beltshirt beltEOF# output - a valid way to get dressedshirtsocksunderwearpantsshoesbelt
Note that topological orderings are not guaranteed to be unique. (You could put your shirt or socks on first, right? It doesn’t matter).
Also notice that the notion of a cycle in this graph makes no sense. (e.g. “You must put on your socks before your shoes, and your shoes before your underwear, and your underwear before your socks.” Good luck with that one).