Topological sort

Imagine, that you are a project manager and are in charge of the work of the whole team. You need to keep track of all of the tasks, that your colleagues have to perform, in order for you to release updates on time. However, some of them may get down to work only after another employee finishes their part. Your task is to distribute the employees' time in the most efficient way and assess, how much time you need to complete all of the work.

The thought of doing all of this manually may be rather scary, especially if there are 10, 15, 20, or even more people on your team. However, don't be afraid! In this topic, we're going to cover the concept of the topological sort, which is exactly what you need to solve such a task. Therefore, keep reading it to become an expert in managing employees' work time and many other fields of application of topological ordering!

Formal definition

So, basically, a topological sort is such a way of ordering the nodes, that the child nodes come after the parent ones. In a more formal way, for a directed acyclic graph $G$, it is an order of nodes such that for each edge $(u, v) \in E$ the node $u$ comes before the node $v$ in the ordering.

Returning to our example of managing the employees, suppose you have visualized the tasks with the use of a graph. Each vertice stands for one of your colleagues and each edge $(u, v)$ shows that the task of employee $v$ may be completed only after employee $u$finishes his work. Imagine, that the graph looks like this:

For such a simple example, it is easy to see how the nodes can be sorted by just looking at the graph. For instance, the topological sort for this graph may look like $\{Alice, Charlie, Dave, Bob, Eve\}$.

Despite the strict formal definition, there exist many different topological sorts for almost any graph, and all of these sortings would be correct. However, sometimes no topological sorting may be found for a graph. It happens in cases when the graph has a cycle, which makes it impossible to figure out, which vertex should appear earlier in a sorting. For example, in this graph there is a cycle $ABC$, therefore no sorting may be found:

When a graph is acyclic, it has at least one topological ordering. But can there be exactly one? Of course! There is no strict rule for finding such graphs, however, we can try to think of them ourselves. First of all, such a graph should have only one vertex with no incoming edges, so that only one node may stand in the first position of the sorting. Secondly, there should be a path, that connects all of the vertices of the graph. In this case, the order of the nodes is determined, which is why only one sorting is possible. For instance, look at the following graph. It has exactly one sorting: $\{A, B, C, E, D\}$.

Example

Now, let's practice getting a topological ordering from a directed acyclic graph. The steps described here are not the exact algorithm, but rather some general ideas that may help you. As for the algorithms, they will be mentioned in the paragraph below and discussed in greater detail in the following topics.

So, let's get down to figuring out the topological ordering right now! Suppose you have a tiny graph with letters:

As you remember (you do, right?), in a sort the child vertices should be placed after the parent ones. Therefore, the first idea, that may cross your mind, is to write down the nodes, that don't have any incoming edges. Let's do exactly that!

We have 3 such vertices in our graph: $A$, $B$ and $C$. Now it's time to look at the rest of them. You can see, that the vertices $D$ and $E$ don't have any parent nodes except for already mentioned ones. Therefore, you may write them down next in the topological ordering. For now, it looks like this: $\{A, B, C, D, E\}$. It doesn't seem so difficult anymore, does it?

If you look at the rest of the nodes once again, you'll see that, just like in the previous step, they do not have any parent vertices except for the already sorted ones, so you can just add them to the final result: $\{A, B, C, D, E, F, G, H\}$. Hooray, you've just found your first topological sort! If we visualize the sequence of the nodes in a sort, it will look like this:

However, this is not the only way to get a sorting. There are many more valid ways to obtain some other orders from this example. For instance, you may have followed a path like this, getting the ordering $\{A, B, C, E, D, H, G, F\}$.

Or you may have even found the ordering $\{A, B, D, F, C, E, G, H\}$, that would look like this on the graph:

Solving the problem

As promised, let's discuss the algorithms, that are widely used to find the topological sort of the graph.

There are two certain and determined algorithms of topological ordering for directed acyclic graphs. They are Depth-first search and Kahn's algorithm.

• The depth-first search goes repeatedly through each node in an arbitrary order. It stops when it meets any node that has already been visited since the beginning of the topological sort, or the node has no outgoing edges.

• Kahn's algorithm works by keeping track of the number of incoming edges into each node. It repeatedly finds nodes with no incoming edge and stores the nodes with no dependency in a queue, deleting them from the original graph.

Both of these algorithms process in linear time, depending on the number of nodes and the number of edges: $O(\left|{V}\right|+\left|{E}\right|)$. Further down the line, we will get acquainted with these algorithms in greater detail.

Applications

While learning about the algorithm may be interesting itself, it is crucial to understand, how exactly it may be used in real-life problems. Topological sorting helps construct a correct sequence of actions, so it's a perfect solution to the tasks of ordering some events, especially in cases when they may depend on each other. Here are some examples:

• Topological order relates to the sequence of students taking training courses and passing topics on this platform, where topics are nodes and their prerequisites and postrequisites provide edges.

• It is also used in package managers, as it is important to understand, which programs should be installed first, as the other ones may be using them.

• The source code of programs using Makefiles is assembled with the use of topological sorting.

• Project management techniques, used to find the minimum time a project can take, work with the help of topological ordering. A part of a project may have predecessor activities, and it is necessary to finish the previous activities to start a new one. Such tools calculate the longest path of the activity graph, where tasks represent vertices, and edges represent the preceding relationship between them, so activities are listed in topological order.

Conclusion

In this topic, you looked at topological sorting (a.k.a. topological order), which is widely used in projects with determined sequences of tasks, schedule planning, and other fields that require planning or ordering. Here's a summary of what was covered:

• Topological sorting of a directed acyclic graph is an ordering of its vertices such that the child nodes come after the parent ones;

• You can arrange nodes in a lot of diverse ways, and all of them will be called topological sortings. However, there are only two determined algorithms for ordering: Depth-first search and Kahn's algorithm;

• It's best to use topological sorting in cases when you need to specify the order of some actions that depend on each other.

Now let's practice with some problems before diving deeper into topological sorting algorithms in the following topics!