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:

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 sorting has many applications in scheduling, ordering and ranking problems, such as

• Project management with task dependencies.
• Determining the assembly sequence for a \(3D\) object.
• Data migration in relational databases.
• Creating a lesson plan for a course.
• Routing in networks.
• Detecting cycles in a graph.

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:

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

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

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

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

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

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:

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

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.

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

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

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

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