This site runs best with JavaScript enabled.Topological Sort

Topological Sort


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 AA depends on Module BB and Module CC
  • Module BB depends on Module CC and Module DD
  • Module CC depends on Module DD
  • Module DD has no dependencies

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

Graph

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

James is a software Engineer who lives in the Nairobi, Kenya. He loves to share his knowledge and help others