Topological Orderings

Let’s say that you are getting dressed in the morning. You know that you can’t put your clothes on in just any order. For example:

-You must put on your socks before you put on your shoes
-You must put on your pants before you puts on your shoes
-You must put on your pants before you put on your belt
-You must put on your shirt before you put on your belt

We can use a directed acyclic graph to represent these facts.

I defined what an acyclic graph is in my post on minimum spanning trees. To recap:

A graph is a set of vertices connected by a set of edges.

In our above example, vertices represent items of clothing (i.e., socks, shoes, pants, belt, and shirt), and edges represent a must-put-on-before relation. So, for example, because you must put on your socks before you put on your shoes, an edge connects socks and shoes.

But, to properly represent the must-put-on-before relation, the edges must have direction. If there were just an edge connecting socks and shoes, then we couldn’t tell from the graph whether you must put your socks on before your shoes or your shoes on before your socks! So, the graph must be directed.

A graph has a cycle if there is a path from some vertex back to itself. So, for example, say that there is the path {(socks, shoes), (shoes, belt), (belt, socks)}. Then you must put your socks on before your shoes, your shoes on before your belt, and your belt on before your socks. So, you must put your socks on before you put your socks on. And, well, you can’t do that. So, the graph can’t have cycles in it. In other words, it must be acyclic.

A directed acyclic graph (or dag) is just a graph that is directed and acyclic.

Dags come up all the time. They can represent temporal dependency, causality, hierarchy, precedence, and a whole lot more. In general, they can represent partial orders.

A graph has a topological ordering if and only if the graph is a dag. So, now that I have (hopefully) clarified what a dag is, let’s talk about topological orderings.

I know that I must put on my socks before I put on my shoes, that I must put on my pants before I put on my shoes, etc., etc. I am aware of all of these temporal dependencies. And that is all well and good, but now I want to know an exact order in which I can put the clothes on. In other words, I want to find a topological ordering of the dag.

In this case, I can put my clothes on in this order: Pants, socks, shoes, shirt, belt.

The above order is a topological ordering of the dag. In a topological ordering, you order the vertices of a dag one after another in such a way that, if there is a directed edge from vertex u to vertex v in the dag, vertex u comes before vertex v in the topological ordering.

There are often several topological orderings of a dag. For example, I can put my clothes on in this order, too: Socks, pants, shirt, belt, shoes.

Topological orderings come in handy in a lot of situations. The classic example is when you are given a set of temporal constraints and you want to devise a schedule. That is actually what we did above when we came up with the order in which to put the clothes on.

There are a number of ways to topologically order a dag. When I implemented topological ordering in Python, I used depth-first search. Depth-first search’s cousin is breadth-first search.

My Python implementation of topological ordering is up at my GitHub.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s