Topological Sorting

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:

Introduction to Programming (IP)
Data Structures (DS)
Algorithms (ALG)
Database Systems (DB)
Web Development (WD)
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:

Start with Introduction to Programming (IP) as it has no prerequisites.
We can then take either Data Structures (DS) or Database Systems (DB), as both only require IP.
Let’s choose DS next.
Now we can take ALG (which requires DS) or DB.
Let’s choose DB.
At this point, we can take either ALG or WD.
We’ll choose ALG.
Now we can only take WD as ML needs WD.
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:

IP will always come first
ML will always come last
DS will always come before ALG
DB will always come before WD and ML
ALG and WD will always come before ML

Topological Sorting Using Depth First Search

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:


def dfs(graph, node, visited, sorted_nodes):
  """
  Perform a Depth-First Search (DFS) starting from a given node.

  Args:
    graph: A dictionary representing the adjacency list of the graph.
    node: The starting node for the DFS.
    visited: A set to keep track of visited nodes.
    sorted_nodes: A list to store the topologically sorted nodes.
  """
  # Mark the current node as visited
  visited.add(node)

  # Iterate through the neighbors of the current node
  for neighbor in graph[node]:
    # If the neighbor has not been visited, recursively call DFS
    if neighbor not in visited:
      dfs(graph, neighbor, visited, sorted_nodes)

  # Add the current node to the sorted list
  sorted_nodes.append(node)

def topological_sort(graph):
  """
  Perform a topological sort on a directed graph.

  Args:
    graph (dict): A dictionary representing the adjacency list of the graph.

  Returns:
    list: A list of nodes in topologically sorted order.
  """
  # Initialize an empty list to store the sorted nodes
  sorted_nodes = []

  # Initialize a set to keep track of visited nodes
  visited = set()

  # Iterate through all the nodes in the graph
  for node in graph:
    # If the node has not been visited, perform DFS
    if node not in visited:
      dfs(graph, node, visited, sorted_nodes)

  # Reverse the list to get the correct topological order
  sorted_nodes.reverse()

  return sorted_nodes

# Let's test the function with courses dependencies discussed before
courses_graph = {
  "IP" : ["DS", "DB"],
  "DS" : ["ALG", "WD"],
  "DB" : ["WD"],
  "ALG" : ["ML"],
  "WD" : ["ML"],
  "ML" : []
}

topological_order = topological_sort(courses_graph)
print("Below is one valid order in which courses can be taken:")
print(topological_order)


#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

// Perform a Depth-First Search (DFS) starting from a given node
void dfs(unordered_map<string, vector<string>>& graph, string node, unordered_set<string>& visited, vector<string>& sorted_nodes) {
  // Mark the current node as visited
  visited.insert(node);

  // Iterate through the neighbors of the current node
  for (const auto& neighbor : graph[node]) {
    // If the neighbor has not been visited, recursively call DFS
    if (visited.find(neighbor) == visited.end()) {
      dfs(graph, neighbor, visited, sorted_nodes);
    }
  }

  // Add the current node to the sorted list
  sorted_nodes.push_back(node);
}

// Perform a topological sort on a directed graph
vector<string> topological_sort(unordered_map<string, vector<string>>& graph) {
  // Initialize an empty list to store the sorted nodes
  vector<string> sorted_nodes;

  // Initialize a set to keep track of visited nodes
  unordered_set<string> visited;

  // Iterate through all the nodes in the graph
  for (const auto& node : graph) {
    // If the node has not been visited, perform DFS
    if (visited.find(node.first) == visited.end()) {
      dfs(graph, node.first, visited, sorted_nodes);
    }
  }

  // Reverse the list to get the correct topological order
  reverse(sorted_nodes.begin(), sorted_nodes.end());

  return sorted_nodes;
}

int main() {
  // Let's test the function with courses dependencies discussed before
  unordered_map<string, vector<string>> courses_graph = {
    {"IP", {"DS", "DB"}},
    {"DS", {"ALG", "WD"}},
    {"DB", {"WD"}},
    {"ALG", {"ML"}},
    {"WD", {"ML"}},
    {"ML", {}}
  };

  vector<string> topological_order = topological_sort(courses_graph);

  cout << "Below is one valid order in which courses can be taken:" << endl;
  for (const auto& course : topological_order) {
    cout << course << " ";
  }
  cout << endl;

  return 0;
}


/**
 * Perform a Depth-First Search (DFS) starting from a given node.
 * 
 * @param {Object} graph - A dictionary representing the adjacency list of the graph.
 * @param {string} node - The starting node for the DFS.
 * @param {Set} visited - A set to keep track of visited nodes.
 * @param {Array} sortedNodes - A list to store the topologically sorted nodes.
 */
function dfs(graph, node, visited, sortedNodes) {
  // Mark the current node as visited
  visited.add(node);

  // Iterate through the neighbors of the current node
  for (const neighbor of graph[node]) {
    // If the neighbor has not been visited, recursively call DFS
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, sortedNodes);
    }
  }

  // Add the current node to the sorted list
  sortedNodes.unshift(node);
}

/**
 * Perform a topological sort on a directed graph.
 * 
 * @param {Object} graph - A dictionary representing the adjacency list of the graph.
 * @returns {Array} - A list of nodes in topologically sorted order.
 */
function topologicalSort(graph) {
  // Initialize an empty list to store the sorted nodes
  const sortedNodes = [];

  // Initialize a set to keep track of visited nodes
  const visited = new Set();

  // Iterate through all the nodes in the graph
  for (const node of Object.keys(graph)) {
    // If the node has not been visited, perform DFS
    if (!visited.has(node)) {
      dfs(graph, node, visited, sortedNodes);
    }
  }

  return sortedNodes;
}

// Let's test the function with courses dependencies discussed before
const coursesGraph = {
  "IP": ["DS", "DB"],
  "DS": ["ALG", "WD"],
  "DB": ["WD"],
  "ALG": ["ML"],
  "WD": ["ML"],
  "ML": []
};

const topologicalOrder = topologicalSort(coursesGraph);
console.log("Below is one valid order in which courses can be taken:");
console.log(topologicalOrder);


import java.util.*;

public class Main {
  
  // Perform a Depth-First Search (DFS) starting from a given node
  public static void dfs(Map<String, List<String>> graph, String node, Set<String> visited, List<String> sortedNodes) {
    // Mark the current node as visited
    visited.add(node);
    
    // Iterate through the neighbors of the current node
    for (String neighbor : graph.get(node)) {
      // If the neighbor has not been visited, recursively call DFS
      if (!visited.contains(neighbor)) {
        dfs(graph, neighbor, visited, sortedNodes);
      }
    }
    
    // Add the current node to the sorted list
    sortedNodes.add(0, node);
  }

  // Perform a topological sort on a directed graph
  public static List<String> topologicalSort(Map<String, List<String>> graph) {
    // Initialize an empty list to store the sorted nodes
    List<String> sortedNodes = new ArrayList<>();
    
    // Initialize a set to keep track of visited nodes
    Set<String> visited = new HashSet<>();
    
    // Iterate through all the nodes in the graph
    for (String node : graph.keySet()) {
      // If the node has not been visited, perform DFS
      if (!visited.contains(node)) {
        dfs(graph, node, visited, sortedNodes);
      }
    }
    
    return sortedNodes;
  }

  public static void main(String[] args) {
    // Let's test the function with courses dependencies discussed before
    Map<String, List<String>> coursesGraph = new HashMap<>();
    coursesGraph.put("IP", Arrays.asList("DS", "DB"));
    coursesGraph.put("DS", Arrays.asList("ALG", "WD"));
    coursesGraph.put("DB", Arrays.asList("WD"));
    coursesGraph.put("ALG", Arrays.asList("ML"));
    coursesGraph.put("WD", Arrays.asList("ML"));
    coursesGraph.put("ML", new ArrayList<>());

    List<String> topologicalOrder = topologicalSort(coursesGraph);
    System.out.println("Below is one valid order in which courses can be taken:");
    System.out.println(topologicalOrder);
  }
}

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:


def topological_sort(graph):
    """
    Perform a topological sort on a directed graph using Kahn's algorithm.

    Args:
        graph (dict): A dictionary representing the adjacency list of the graph.

    Returns:
        list: A list of nodes in topologically sorted order
    """
    # Create a list to store nodes with 0 in-degree
    zero_indegree_nodes = []
    
    # Create a dictionary to store the in-degree of each node
    in_degree = {}
    
    # Initialize in-degree of all nodes to 0
    for node in graph:
        in_degree[node] = 0
    
    # Calculate the in-degree of each node
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # Add nodes with 0 in-degree to the zero_indegree_nodes list
    for node in in_degree:
        if in_degree[node] == 0:
            zero_indegree_nodes.append(node)
    
    # Perform topological sort
    topological_order = []
    while zero_indegree_nodes:
        # Remove a node from the end of the list
        current_node = zero_indegree_nodes.pop()
        topological_order.append(current_node)
        
        # Decrement the in-degree of its neighbors
        for neighbor in graph[current_node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                zero_indegree_nodes.append(neighbor)
    
    # Check if there is a cycle in the graph
    if len(topological_order) != len(graph):
        print("Error: Cycle detected in the graph")
        return []
    
    return topological_order

# Let's test the function with courses dependencies discussed before
courses_graph = {
    "IP": ["DS", "DB"],
    "DS": ["ALG", "WD"],
    "DB": ["WD"],
    "ALG": ["ML"],
    "WD": ["ML"],
    "ML": []
}

topological_order = topological_sort(courses_graph)
print("Below is one valid order in which courses can be taken:")
print(topological_order)


#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

// Function to perform topological sort on a directed graph
vector<string> topological_sort(unordered_map<string, vector<string>>& graph) {
  // Create a list to store nodes with 0 in-degree
  vector<string> zero_indegree_nodes;
  
  // Create a dictionary to store the in-degree of each node
  unordered_map<string, int> in_degree;
  
  // Initialize in-degree of all nodes to 0
  for (const auto& [node, neighbors] : graph) {
    in_degree[node] = 0;
  }
  
  // Calculate the in-degree of each node
  for (const auto& [node, neighbors] : graph) {
    for (const auto& neighbor : neighbors) {
      in_degree[neighbor]++;
    }
  }
  
  // Add nodes with 0 in-degree to the zero_indegree_nodes list
  for (const auto& [node, degree] : in_degree) {
    if (degree == 0) {
      zero_indegree_nodes.push_back(node);
    }
  }
  
  // Perform topological sort
  vector<string> topological_order;
  while (!zero_indegree_nodes.empty()) {
    // Remove a node from the end of the list
    string current_node = zero_indegree_nodes.back();
    zero_indegree_nodes.pop_back();
    topological_order.push_back(current_node);
    
    // Decrement the in-degree of its neighbors
    for (const auto& neighbor : graph[current_node]) {
      in_degree[neighbor]--;
      if (in_degree[neighbor] == 0) {
        zero_indegree_nodes.push_back(neighbor);
      }
    }
  }
  
  // Check if there is a cycle in the graph
  if (topological_order.size() != graph.size()) {
    cout << "Error: Cycle detected in the graph" << endl;
    return {};
  }
  
  return topological_order;
}

int main() {
  // Let's test the function with courses dependencies discussed before
  unordered_map<string, vector<string>> courses_graph = {
    {"IP", {"DS", "DB"}},
    {"DS", {"ALG", "WD"}},
    {"DB", {"WD"}},
    {"ALG", {"ML"}},
    {"WD", {"ML"}},
    {"ML", {}}
  };

  vector<string> topological_order = topological_sort(courses_graph);
  cout << "Below is one valid order in which courses can be taken:" << endl;
  for (const auto& course : topological_order) {
    cout << course << " ";
  }
  cout << endl;

  return 0;
}


/**
 * Perform a topological sort on a directed graph using Kahn's algorithm.
 *
 * @param {Object} graph - A dictionary representing the adjacency list of the graph.
 * @returns {Array} - A list of nodes in topologically sorted order, or an error message if a cycle is detected.
 */
function topologicalSort(graph) {
  // Create a list to store nodes with 0 in-degree
  const zeroInDegreeNodes = [];

  // Create a dictionary to store the in-degree of each node
  const inDegree = {};

  // Initialize in-degree of all nodes to 0
  for (const node in graph) {
    inDegree[node] = 0;
  }

  // Calculate the in-degree of each node
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      inDegree[neighbor]++;
    }
  }

  // Add nodes with 0 in-degree to the zeroInDegreeNodes list
  for (const node in inDegree) {
    if (inDegree[node] === 0) {
      zeroInDegreeNodes.push(node);
    }
  }

  // Perform topological sort
  const topologicalOrder = [];
  while (zeroInDegreeNodes.length > 0) {
    // Remove a node from the end of the list
    const currentNode = zeroInDegreeNodes.pop();
    topologicalOrder.push(currentNode);

    // Decrement the in-degree of its neighbors
    for (const neighbor of graph[currentNode]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        zeroInDegreeNodes.push(neighbor);
      }
    }
  }

  // Check if there is a cycle in the graph
  if (topologicalOrder.length !== Object.keys(graph).length) {
    console.log("Error: Cycle detected in the graph");
    return [];
  }

  return topologicalOrder;
}

// Let's test the function with courses dependencies discussed before
const coursesGraph = {
  IP: ["DS", "DB"],
  DS: ["ALG", "WD"],
  DB: ["WD"],
  ALG: ["ML"],
  WD: ["ML"],
  ML: [],
};

const topologicalOrder = topologicalSort(coursesGraph);
console.log("Below is one valid order in which courses can be taken:");
console.log(topologicalOrder);


import java.util.*;

public class Main {
  public static List<String> topological_sort(Map<String, List<String>> graph) {
    // Create a list to store nodes with 0 in-degree
    List<String> zero_indegree_nodes = new ArrayList<>();
    
    // Create a map to store the in-degree of each node
    Map<String, Integer> in_degree = new HashMap<>();
    
    // Initialize in-degree of all nodes to 0
    for (String node : graph.keySet()) {
      in_degree.put(node, 0);
    }
    
    // Calculate the in-degree of each node
    for (String node : graph.keySet()) {
      for (String neighbor : graph.get(node)) {
        in_degree.put(neighbor, in_degree.get(neighbor) + 1);
      }
    }
    
    // Add nodes with 0 in-degree to the zero_indegree_nodes list
    for (String node : in_degree.keySet()) {
      if (in_degree.get(node) == 0) {
        zero_indegree_nodes.add(node);
      }
    }
    
    // Perform topological sort
    List<String> topological_order = new ArrayList<>();
    while (!zero_indegree_nodes.isEmpty()) {
      // Remove a node from the end of the list
      String current_node = zero_indegree_nodes.remove(zero_indegree_nodes.size() - 1);
      topological_order.add(current_node);
      
      // Decrement the in-degree of its neighbors
      for (String neighbor : graph.get(current_node)) {
        in_degree.put(neighbor, in_degree.get(neighbor) - 1);
        if (in_degree.get(neighbor) == 0) {
          zero_indegree_nodes.add(neighbor);
        }
      }
    }
    
    // Check if there is a cycle in the graph
    if (topological_order.size() != graph.size()) {
      System.out.println("Error: Cycle detected in the graph");
      return new ArrayList<>();
    }
    
    return topological_order;
  }

  public static void main(String[] args) {
    // Let's test the function with courses dependencies discussed before
    Map<String, List<String>> courses_graph = new HashMap<>();
    courses_graph.put("IP", Arrays.asList("DS", "DB"));
    courses_graph.put("DS", Arrays.asList("ALG", "WD"));
    courses_graph.put("DB", Arrays.asList("WD"));
    courses_graph.put("ALG", Arrays.asList("ML"));
    courses_graph.put("WD", Arrays.asList("ML"));
    courses_graph.put("ML", new ArrayList<>());

    List<String> topological_order = topological_sort(courses_graph);
    System.out.println("Below is one valid order in which courses can be taken:");
    System.out.println(topological_order);
  }
}

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.