Topological Sorting

Ever had a situation where you had a set of things to choose from and you had to decide which one should come first, before the other, that is, the order of priority?

For example, you have a list of courses to take and you have to decide which course precedes the other for maximum understanding. That can be solved with Topological Sort.

It involves precedence scheduling, deciding what comes before what.

It is most commonly used in scheduling and graph processing and only works when the graph is directed and has no cycles - Directed Acyclic Graph (DAG).

Using the course example and relating it to graph:

1. The courses are the vertices.
2. The edges imply precedence.

So if you have a course A, that points to another course B, it simply means that A must be taken before B; represented as A -> B.

Implementation

First, let's understand how topological sort works in reality.

1. Lay out all the course names on your table.
2. Starting from the first course 0, check if any course should come before it.
3. If there is none, you take out that course 1 and add it to stack that shows course order.
4. However, if there's a course 1 that should come before 0, you proceed to check that course 2 for a course 3 that should come before it.
5. Continue till you find a course that doesn't have any course before it and subsequently add to your stack in that order.
6. Thus, popping from the stack, gives you the topological ordering.

Notice how this translates to a Depth First Search - recursively checking each node till you reach a base value and then return - in this case: before you return from the function, you add the vertex to your stack.

Here’s a simple pseudocode:

1. Store the input as a Directed Graph
2. Starting from vertex i,
3. Check for vertices connected to it
4. If no vertex, add i to your stack and return
5. Else, repeat from 3.

Code Solution

Let’s go through the Digraph data structure first of all.

Digraph

To understand the digraph structure, go through the comments and test with different values;

Topological Sort

Cyclic Graphs

The approach of the topological sorting can be used to detect if a graph has cycles. A graph that has a cycle, will try to visit a vertex when it has not returned from it’s recursive call.

Using our course prerequisites for example, suppose we have courses A B C D
A → B - A must be taken before B
B → C - B must be taken before C
C → D - C must be taken before D
D → A - D must be taken before A, we see that this effectively creates an impossible scenario. We are still in A’s recursion of courses to take and it is saying that we must have taken A.. What a bummer!!

To detect this in our algorithm; have an array of vertices in the recursion stack, so that once we return from a vertex, we remove it from the stack. If we get to a vertex that is still in the stack, we note that, our tree has a cycle.

Cycle Detection

I suggest you try this out yourself for better understanding and internalization of the working principle.

Leave a comment or tweet at me @dera_jo.

PS: I’m currently looking for a job 🙂 . If you’re in need of a Software Developer, with major experience in Back-end Development and some Front-end, I’m your girl!!