Algorithm Deep Dive Topological Sorting

Topological Sorting

4 min read

Topological sorting is a concept in computer science, which is used in scenarios where a set of tasks must be performed in a specific order such that all the required conditions are satisfied. This concept is widely applied in task scheduling, dependency management, and graph theory.

Example of Topological Sorting

Let’s consider a sample example using academic subjects and their prerequisites/dependencies to demonstrate topological sorting.

Assume that below are the list of subjects a student has to complete:

  1. Introduction to Programming (IP)
  2. Data Structures (DS)
  3. Algorithms (ALG)
  4. Database Systems (DB)
  5. Web Development (WD)
  6. Machine Learning (ML)

Below are the dependencies/requirements before enrolling for each subject:

  • “Data Structures” requires completion of “Introduction to Programming”
  • “Algorithms” requires completion of “Data Structures”
  • “Database Systems” requires “Introduction to Programming”
  • “Web Development” requires “Data Structures” and “Database Systems”
  • “Machine Learning” requires “Algorithms” and “Web Development”

We can represent the dependencies as a directed acyclic graph (DAG):

IP ---> DS ---> ALG ---> ML
 |       |              ^
 |       |             /
 v       v            /
DB ----> WD ----------

Now, let’s find a valid topological ordering for these subjects:

  1. Start with Introduction to Programming (IP) as it has no prerequisites.
  2. We can then take either Data Structures (DS) or Database Systems (DB), as both only require IP.
  3. Let’s choose DS next.
  4. Now we can take ALG (which requires DS) or DB.
  5. Let’s choose DB.
  6. At this point, we can take either ALG or WD.
  7. We’ll choose ALG.
  8. Now we can only take WD as ML needs WD.
  9. Let’s finish with WD, then ML.

So, a valid topological ordering would be:

IP -> DS -> DB -> ALG -> WD -> ML

This ordering ensures that each subject is taken only after its prerequisites have been completed.

It’s important to note that this is not the only valid topological ordering. For example, another valid ordering could be:

IP -> DB -> DS -> WD -> ALG -> ML

In this alternative ordering, we took DB before DS, which is also valid since both only depend on IP. We also took WD before ALG, which is fine because WD doesn’t depend on ALG.

The key point is that in any valid topological ordering:

  1. IP will always come first
  2. ML will always come last
  3. DS will always come before ALG
  4. DB will always come before WD and ML
  5. ALG and WD will always come before ML

Depth-First Search (DFS) recursively explores a graph, fully visiting all connected nodes before backtracking. This property is useful for topological sorting, which orders nodes in a directed graph such that for every edge A -> B, A comes before B.

In the DFS-based topological sort, we maintain a list and add each node to this list after exploring all its neighbors. This ensures that a node is added only after all nodes depending on it are added. However, this process actually creates a reverse topological order.

For example, in a graph with A -> B -> D, DFS exploration would add nodes to the list in the order [D, B, A]. To get the correct topological order, we must reverse this list, resulting in [A, B, D]. This final reversed list ensures that each node appears before any nodes that depend on it, satisfying the definition of a topological sort.

Below is the implementation of topological sort using DFS:

Loading code…

Topological Sorting Using Khan’s Algorithm

Kahn’s algorithm for topological sorting works by repeatedly finding and removing nodes that have no dependencies. We start by identifying all nodes with no prerequisites (no incoming edges to the node). These are our “ready to process” nodes. We add them to our result list and remove them from the graph. As we remove each node, we also remove its outgoing dependencies. If this causes any other nodes to lose all their dependencies, we add those to our “ready to process” list. We repeat this process until all nodes are completed.

Below is the implementation of topological sort using Kahn’s algorithm:

Loading code…

Applications of Topological Sorting

Topological sorting has numerous real-world applications:

  • Task Scheduling and Dependency Management: Ensuring tasks are executed in the correct order based on dependencies.
  • Compiler Design and Build Systems: Determining the order of compilation for source code files.
  • Ordering of Courses in an Academic Curriculum: Ensuring prerequisites are completed before advanced courses.
  • Dependency Analysis in Software Engineering: Managing package dependencies in software projects.
  • Sequencing Problems in Various Domains: Solving problems where a sequence must respect certain constraints.