Calculus

Set Theory

Set Theory Logo

Topological Sorting

Definition and Some Examples

Let \(\require{AMSsymbols}{\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

  • 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:

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).\)


Solved Problems

Click or tap a problem to see the solution.

Example 1

The set \(A = \left\{ {2,3,4,6,8,9,12,18} \right\}\) is ordered by the divisibility relation “|”. Determine a topological sort of the poset.

Example 2

The set of geometric shapes is partially ordered by area.
Set of geometric shapes partially ordered by area.
Find a topological sort of the shapes.

Example 3

General relativity requires a knowledge of mathematics and physics, which is illustrated by the following diagram:
Prerequisites of math and physics courses for learning general relativity.
Determine an order in which these courses can be taken.

Example 4

A partially ordered set is given by the digraph
Digraph of a partially ordered set to be topologically sorted.
Find a topological sort of the graph using \(DFS\) algorithm.

Example 1.

The set \(A = \left\{ {2,3,4,6,8,9,12,18} \right\}\) is ordered by the divisibility relation “|”. Determine a topological sort of the poset.

Solution.

The Hasse diagram of the partially ordered set \(\left( {A, \mid} \right)\) looks like this:

Hasse diagram of a partially ordered set ordered by divisibility relation.
Figure 14.

For topological sorting we can use the usual “less than or equal” relation \(\le\). This relation preserves the ordering defined by divisibility, so if \(a\mid b\) for numbers \(a\) and \(b,\) then \(a \le b.\) As a result, we obtain a topological sort of the poset \(\left( {A, \mid} \right)\) in the form of an ascending number sequence:

\[{2 \le 3 \le 4 \le 6 \le 8 \le 9 \le 12 \le 18.}\]

We can also build another topological sort for the poset. Using Kahn’s method, we identify two minimal elements – \(2\) and \(3.\) Starting, for example, from \(3,\) we remove the elements in the following order: \(3, 9, 2, 6, 18, 4, 12, 8.\) This sequence forms a total order of kind

\[3 \preccurlyeq 9 \preccurlyeq 2 \preccurlyeq 6 \preccurlyeq 18 \preccurlyeq 4 \preccurlyeq 12 \preccurlyeq 8.\]

We can easily make sure that this total order preserves the divisibility ordering in the original set and, hence, is a topological sort of \(\left( {A, \mid} \right):\)

Alternative topological sort of a poset with the divide relation.
Figure 15.

Example 2.

The set of geometric shapes is partially ordered by area as shown in Figure \(16.\) Find a topological sort of the shapes.

Solution.

Set of geometric shapes partially ordered by area.
Figure 16.

We assume that the area of a shape \(A\) is less than the area of a shape \(B\) and denote is as \(A \preccurlyeq B,\) if the shape \(A\) is inscribed in shape \(B.\)

We identify the following relations between the given shapes:

\[2 \preccurlyeq 1,\;3 \preccurlyeq 2,\;4 \preccurlyeq 2,\;5 \preccurlyeq 4,\;6 \preccurlyeq 1,\;7 \preccurlyeq 6,\;8 \preccurlyeq 7,\;9 \preccurlyeq 6.\;\]

Draw the Hasse diagram for the partially ordered set:

Hasse diagram of the poset with geometric shapes.
Figure 17.

A possible topological sort (it can be easily built using Kahn’s algorithm) has the following form:

\[8 \preccurlyeq 5 \preccurlyeq 9 \preccurlyeq 7 \preccurlyeq 4 \preccurlyeq 3 \preccurlyeq 6 \preccurlyeq 2 \preccurlyeq 1.\]

Example 3.

General relativity requires a knowledge of mathematics and physics, which is illustrated by the diagram in Figure \(18.\) Determine an order in which these courses can be taken.

Solution.

Prerequisites of math and physics courses for learning general relativity.
Figure 18.

First we note that the relation defined by the digraph is antisymmetric and transitive. Assuming, for simplicity, that it is also reflexive, we get a partially ordered set, which can be topologically sorted.

There are two vertices that have no incoming edges – Calculus and Linear Algebra. By applying Kahn’s algorithm, we select Calculus and remove it from the digraph. This will be the first course in the sorted output list (aren’t we lucky?). Then we repeat the process by successively removing Linear Algebra, ODE, and so on.

One of the possible topological sorts looks like this:

\[\text{Calculus} \preccurlyeq \text{Linear Algebra} \preccurlyeq \text{ODE} \preccurlyeq \text{PDE} \preccurlyeq \text{Classical Mechanics} \preccurlyeq \text{Electromagnetism} \preccurlyeq \text{Real Analysis} \preccurlyeq \text{Differential Geometry} \preccurlyeq \text{General Relativity}.\]

Teaching general relativity
Figure 19.

Example 4.

A partially ordered set is given by the digraph shown in Figure \(20.\) Find a topological sort of the graph using DFS algorithm.

Solution.

Digraph of a partially ordered set to be topologically sorted.
Figure 20.

We identify \(4\) nodes that have no incoming edges: \(1,2,3\) and \(4.\) For each of these elements, we determine the list of adjacent vertices:

\[\text{Vertex }1 : 1, 5, 8, 6, 9, 10, 11\]

\[\text{Vertex }2 : 2, 5, 9, 11\]

\[\text{Vertex }3 : 3, 5, 8, 6, 9, 10, 11, 7\]

\[\text{Vertex }4 : 4, 6\]

Filter out coinciding elements:

\[\require{cancel}\text{Vertex }2 : 2, \cancel{5}, \cancel{9}, \cancel{11}\]

\[\text{Vertex }3 : 3, \cancel{5}, \cancel{8}, \cancel{6}, \cancel{9}, \cancel{10}, \cancel{11}, 7\]

\[\text{Vertex }4 : 4, \cancel{6}\]

Combine the blocks to get a topological sort:

\[\underbrace {4}_{4} \preccurlyeq \underbrace{3 \preccurlyeq 7}_{3} \preccurlyeq \underbrace {2}_ {2} \preccurlyeq \underbrace{1 \preccurlyeq 5 \preccurlyeq 8 \preccurlyeq 6 \preccurlyeq 9 \preccurlyeq 10 \preccurlyeq 11}_{1}\]