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