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

**Vertices (Modules)**:- Let $V = \{A, B, C, D\}$ represent the set of vertices, where each vertex is a module.

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

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

- Given the input, the adjacency list can be represented as follows:
**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.

- The graph can be denoted as $G = (V, E)$ where:
**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'$.

**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' \}|$.

**Queue Initialization**:- Initialize a queue $Q$ with all vertices $v \in V$ where $indeg'(v) = 0$.

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

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