# Calculus

## Set Theory # 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:

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:

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

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

## 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. 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: Determine an order in which these courses can be taken.

### Example 4

A partially ordered set is given by the digraph 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:

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):$$

### 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.

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:

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.

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}.$

### 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.

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}$