Topological Sort

Photo by Martin Martz

Topological Sort is a linear ordering of vertices such that for every directed edge u->v, vertex u comes before v in the ordering.

Let's illustrate a simplified problem within a build system scenario, which is a common application of Topological Sorting.

Imagine you are working on a software project with multiple modules. Some modules depend on others to be built first. You are required to find a build order that will allow all modules to be built without any dependency errors.

Here's a representation of the modules and dependencies:

• Module $A$ depends on Module $B$ and Module $C$
• Module $B$ depends on Module $C$ and Module $D$
• Module $C$ depends on Module $D$
• Module $D$ has no dependencies

This scenario can be represented by a directed graph. In this graph, an edge from Module $X$ to Module $Y$ means $X$ must be built before $Y$, as $Y$ depends on $X$.

1. Vertices (Modules):
   • Let $V = \{A, B, C, D\}$ represent the set of vertices, where each vertex is a module.
2. Edges (Dependencies):
   • Let $E \subseteq V \times V$ represent the set of directed edges, where each edge is a dependency. An edge from vertex $u$ to vertex $v$ (denoted as $(u, v)$) implies that module $u$ depends on module $v$.
3. Adjacency List Representation:
   • Given the input, the adjacency list can be represented as follows:
     • $Adj(A) = \{B, C\}$ - Module A depends on modules B and C.
     • $Adj(B) = \{C, D\}$ - Module B depends on modules C and D.
     • $Adj(C) = \{D\}$ - Module C depends on module D.
     • $Adj(D) = \emptyset$ - Module D has no dependencies.
4. Graph Notation:
   • The graph can be denoted as $G = (V, E)$ where:
     • $V = \{A, B, C, D\}$
     • $E = \{(A, B), (A, C), (B, C), (B, D), (C, D)\}$ Where $V$ is the set of vertices (modules) and $E$ is the set of directed edges (dependencies). The direction of an edge indicates the direction of dependency. For instance, the edge $(A, B)$ implies that module A is dependent on module B.
5. Reverse Graph Construction:
   • Construct a reverse graph $G' = (V, E')$ where $E'$ contains edges in the opposite direction of $E$.
   • For each dependency $(u, v) \in E$ in the original graph $G$, add an edge $(v, u)$ to $E'$.
   • If $(u, v) \in E$ then $(v, u) \in E'$.
6. Indegree Calculation:
   • For each vertex $v \in V$ in $G'$, calculate the indegree, $indeg'(v)$, representing the number of incoming edges in $G'$.
   • $indeg'(v) = |\{ u \in V : (v, u) \in E' \}|$.
7. Queue Initialization:
   • Initialize a queue $Q$ with all vertices $v \in V$ where $indeg'(v) = 0$.
8. Topological Sorting Using Queue:
   • Initialize an empty list $L$.
   • While $Q$ is not empty:
     • Dequeue vertex $v$ from $Q$.
     • Add $v$ to $L$.
     • For each vertex $u$ where $(v, u) \in E'$ (in the reverse graph):
       • Decrement $indeg'(u)$ by 1.
       • If $indeg'(u) = 0$, enqueue $u$ into $Q$.
9. Cycle Detection and Order Validation:
   • If the length of $L$ is not equal to the number of vertices $|V|$, it implies that a cycle exists in the graph or not all nodes are connected, making topological sorting impossible.