Calculus

Set Theory

Set Theory Logo

Topological Sorting

Definition and Some Examples

Let \({\left( {A, \preccurlyeq} \right)}\) be a partially ordered set. Suppose we want to transform the partial order into a total order that does not violate the partial order. So if \(a \preccurlyeq b\) in the partial order, then \(a\, {\preccurlyeq_T}\, b\) in the total order as well. Such a total order is called compatible with the partial order.

The process of constructing a compatible total order for a given partial order is called topological sorting.

It is known that every finite partially ordered set \({\left( {A, \preccurlyeq} \right)}\) can be represented by a directed graph \(G.\) The vertices of \(G\) correspond to the elements of set \(A,\) and the edge from \(a\) to \(b\) exists if and only if \(a \preccurlyeq b.\) For example, a simple partially ordered set may look as follows:

A DAG representing a simple partially ordered set.
Figure 1.

Topological sorting only works for directed acyclic graphs \(\left({DAG}\right),\) that is, only for graphs without cycles. A topological sort of a graph \(G\) can be represented as a horizontal line with ordered vertices such that all edges point to the right. So, a topological sort for the above poset has the following form:

Topological sort of a partially ordered set.
Figure 2.

Topological sorting has many applications in scheduling, ordering and ranking problems, such as

Algorithms

There are two basic algorithms for topological sorting - Kahn's algorithm and the Depth First Search \(\left({DFS}\right)\) based algorithm. The running time for both the algorithms is \(\mathcal{O}(V + E),\) where \(V\) is the number of vertices and \(E\) is the number of edges.

Kahn's Algorithm

This method is based on the fact that every directed acyclic graph has at least one vertex without incoming edges (minimal element). On the first step, we find any minimal element and remove it from the graph together with all its outgoing edges. The removed element is inserted into the set of sorted elements. Then we repeat the process until no more elements are left.

Consider the set \(A = \left\{ {a,b,c,d,e,f,g,h} \right\}\) with a partial ordering \(\preccurlyeq\) given by the digraph:

A set with a partial ordering
Figure 3.

The set has \(3\) minimal elements: \(a,b\) and \(c.\) We can remove any of them. Let it be \(c.\)

Digraph of set A with removed minimal element c.
Figure 4.

Next we choose the minimal element \(b.\)

Digraph of set A with removed elements c and b.
Figure 5.

We have again \(2\) choices - \(a\) and \(e\). Pick, for example, \(e.\)

Digraph of set A with removed elements c, b and e.
Figure 6.

In this step, there is only one minimal element - the element \(a.\) We remove it from the digraph.

Digraph of set A with removed elements c, b, e, a.
Figure 7.

We continue the process by removing the element \(d.\)

Digraph of set A with removed elements c, b, e, a, d.
Figure 8.

The remaining elements \(f, g\) and \(h\) can be removed in the same order.

Thus, we get the following total order as a result of topological sorting:

\[c \,{\preccurlyeq_T}\, b \,{\preccurlyeq_T}\, e \,{\preccurlyeq_T}\, a \,{\preccurlyeq_T}\, d \,{\preccurlyeq_T}\, f \,{\preccurlyeq_T}\, g \,{\preccurlyeq_T}\, h.\]

This total order preserves the partial ordering in the initial poset:

Topological sorting of a poset.
Figure 9.

This is one of the possible topological sorts. There may often be more than one topological sort of a digraph.

Depth Search First

Another algorithm for topological sorting is based on depth first search. Here, similarly to the Kanh's algorithm, first we need to identify all vertices without incoming edges. Then we perform a depth first search \(\left({DFS}\right)\) for each of the vertices. The idea behind \(\left({DFS}\right)\) is to traverse all vertices reachable from a given vertex. During a traversal, we must keep track of which vertices have been visited to avoid visiting the same vertex twice. At the end of the process, we combine the results of different depth first searches to build a topologically sorted list of vertices.

Let's do a \({DFS}\) for the poset \(\left( {\left\{ {a,b,c,d,e,f,g,h} \right\}, \preccurlyeq} \right)\) from the previous section.

A poset to be topologically sorted using DFS algorithm.
Figure 10.

Perform a \({DFS}\) for the minimal elements \(a,b\) and \(c.\) For each of the traversals we list all adjacent vertices:

Adjacent vertices for starting elements a,b,c of a graph.
Figure 11.

Filter out repeating elements so that each vertex is visited only once.

Filtered out adjacent vertices for starting elements a,b,c of a graph.
Figure 12.

Now we build a stack of sorted elements by attaching each block to the front of the previous sequence:

Topological sorting of a poset using DFS algorithm.
Figure 13.

This stack represents a topological sort of the original poset \(\left( {\left\{ {a,b,c,d,e,f,g,h} \right\}, \preccurlyeq} \right).\)

See solved problems on Page 2.

Page 1 Page 2