# What is a topological ordering?

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).

# Example: Getting Dressed

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).

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).

Wow! You read the whole thing. People who make it this far sometimes want to receive emails when I post something new.

I also have an RSS feed.