Introduction to Topological Sort

About the pattern

Topological sorting is a technique used to organize a collection of items or tasks based on their dependencies. Imagine there is a list of tasks to complete, but some tasks can only be done after others are finished. There are many such tasks that depend on each other, or there’s a specific sequence of actions that must be followed. For example, when baking a cake, there are several steps one needs to follow, and some steps depend on others. We can’t frost the cake until it’s baked, and we can’t bake it until we’ve mixed the batter. To ensure that we don’t frost the cake before baking it or mix the batter after preheating the oven, we need to sort the steps based on their dependencies. This is where topological sorting helps us. It figures out the correct sequence of steps to bake the cake efficiently.

The topological sort pattern is used to find valid orderings of elements that have dependencies on or priority over each other. These elements can be represented as the nodes of a graph, so in technical terms, topological sort is a way of ordering the nodes of a directed graph such that for every directed edge $[a,b]$ from node $a$ to node $b$ , $a$ comes before $b$ in the ordering.

Note: Topological sort is only applicable to directed acyclic graphs (DAGs), meaning there should be no cycles present in the graph.

If we write a recipe for baking a cake, then the list of tasks goes like first mix the batter, then bake the cake, and finally, frost it. These tasks can also be organized in a graph, where each task is a node, and the dependencies between tasks are represented by directed edges.

However, if we mistakenly add an additional step in our recipe that contradicts any of the existing steps, it introduces a cycle in our graph. For example, if the recipe goes like mix the batter, frost the cake, bake the cake, and frost the cake, we can’t frost a cake that hasn’t been baked and can’t bake a cake that’s already frosted. Similarly, in a graph with cycles, we can’t establish a clear order of tasks, making topological sorting impossible. Therefore, topological sorting is only applicable to directed acyclic graphs (DAGs), where tasks are organized in a logical sequence without any contradictions or cycles.

Topological sorting is crucial for converting a partial ordering to a complete ordering, especially when certain tasks have defined dependencies while others do not. For instance, consider a research project involving five tasks, labeled as $A$ , $B$ , $C$ , $D$ , and $E$ . Some tasks depend on others: Task $A$ must be completed before Task $B$ and Task $C$ , Task $B$ must be finished before the Task $D$ , and Task $C$ must be done before Task $E$ . However, when it comes to performing Tasks $B$ and $C$ , it’s unclear which one should be done first. This is where topological sorting comes in. It helps us convert this partial ordering of tasks into a complete ordering, providing clarity on the sequence of tasks to ensure efficient execution. There can be multiple possible valid ordering of the elements. For example, based on the given dependencies in our example, some valid orderings of the tasks could be:

$A, B, C, D, E$
$A, C, B, D, E$
$A, B, C, E, D$

Here is the template for topological sorting, in which tasks or elements are ordered based on dependencies in a directed acyclic graph (DAG).

FUNCTION topologicalSort(graph):
  # Initialize in-degree map
  inDegree = {node: 0 FOR each node in graph}
  # Calculate in-degrees of all nodes
  FOR node IN graph:
    # Find the neighbors of each node in the given graph
    FOR neighbor IN graph[node]:
      inDegree[neighbor] += 1
  # Add nodes with 0 in-degree to the queue
  queue = new Queue()
  FOR node IN inDegree:
    IF inDegree[node] == 0:
      queue.enqueue(node)
  topologicalOrder = []
  # Process nodes in topological order
  WHILE queue is not empty:
    current = queue.dequeue()
    topologicalOrder.append(current)
    # Reduce in-degree of neighbors and enqueue if they become 0
    FOR neighbor IN graph[current]:
      inDegree[neighbor] -= 1
      IF inDegree[neighbor] == 0:
        queue.enqueue(neighbor)
  # Check for cycles (If not all nodes are processed, a cycle exists)
  IF length of topologicalOrder != length of graph:
    RETURN "Cycle detected, topological sort not possible"
  RETURN topologicalOrder

We first calculate the in-degree of each node, representing the number of incoming edges or dependencies. Nodes with inDegree = 0 are added to a queue as they have no dependencies and can be processed first. We then process nodes from the queue, adding them to topologicalOrder and reducing the in-degree of their neighbors. If a neighbor’s in-degree becomes zero, it is added to the queue, ensuring proper ordering. If, in the end, the number of processed nodes is less than the total nodes in the graph, a cycle exists, preventing topological sorting as some nodes remain unprocessed.

Now, let’s have a visual demonstration of the example we discussed above:

About the pattern

Note: Topological sort is only applicable to directed acyclic graphs (DAGs), meaning there should be no cycles present in the graph.

$A, B, C, D, E$
$A, C, B, D, E$
$A, B, C, E, D$

Here is the template for topological sorting, in which tasks or elements are ordered based on dependencies in a directed acyclic graph (DAG).

FUNCTION topologicalSort(graph):
  # Initialize in-degree map
  inDegree = {node: 0 FOR each node in graph}
  # Calculate in-degrees of all nodes
  FOR node IN graph:
    # Find the neighbors of each node in the given graph
    FOR neighbor IN graph[node]:
      inDegree[neighbor] += 1
  # Add nodes with 0 in-degree to the queue
  queue = new Queue()
  FOR node IN inDegree:
    IF inDegree[node] == 0:
      queue.enqueue(node)
  topologicalOrder = []
  # Process nodes in topological order
  WHILE queue is not empty:
    current = queue.dequeue()
    topologicalOrder.append(current)
    # Reduce in-degree of neighbors and enqueue if they become 0
    FOR neighbor IN graph[current]:
      inDegree[neighbor] -= 1
      IF inDegree[neighbor] == 0:
        queue.enqueue(neighbor)
  # Check for cycles (If not all nodes are processed, a cycle exists)
  IF length of topologicalOrder != length of graph:
    RETURN "Cycle detected, topological sort not possible"
  RETURN topologicalOrder

Now, let’s have a visual demonstration of the example we discussed above:

Introduction to Topological Sort

About the pattern

Examples

Does your problem match this pattern?

Real-world problems

Strategy time!

About the pattern

Examples

Does your problem match this pattern?

Real-world problems

Strategy time!