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.

Press + to interact

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.

Press + to interact

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:

Press + to interact

Does your problem match this pattern?

Yes, if either of these conditions is fulfilled:
- Dependency relationships: The problem involves tasks, jobs, courses, or elements with dependencies between them. These dependencies create a partial order, and topological sorting can be used to establish a total order based on these dependencies.
- Ordering or sequencing: The problem requires determining a valid order or sequence to perform tasks, jobs, or activities, considering their dependencies or prerequisites.
No, if either of these conditions is fulfilled:
- Presence of cycles: If the problem involves a graph with cycles, topological sorting cannot be applied because there is no valid linear ordering of vertices that respects the cyclic dependencies.
- Dynamic dependencies: If the dependencies between elements change dynamically during the execution of the algorithm, topological sorting may not be suitable. Topological sorting assumes static dependencies that are known beforehand.

Real-world problems

Many problems in the real world share the topological sort pattern. Let’s look at some examples.

Course scheduling: In academic institutions, students need to enroll in courses based on prerequisites. Topological sorting helps determine the order in which courses should be taken to ensure that students meet the prerequisites for each course.
Recipe planning in cooking: Recipes often have steps that must be performed in a specific order. For example, a cake can’t be baked until we’ve mixed the batter. Topological sorting can help plan the steps of a recipe to ensure that they are performed in the correct sequence.
Process scheduling in computer systems: During system boot-up, the operating system needs to initiate various processes, some of which depend on others. These dependencies are represented as ordered pairs. Circular dependencies are not allowed. The operating system selects an order for executing processes, ensuring that each process’s dependencies are met before execution.

Strategy time!

Match the problems that can be solved using the topological sort pattern.

Note: Select a problem in the left-hand column by clicking it, and then click one of the two options in the right-hand column.

Cyclic Sort

Topological Sort

Conclusion

Introduction to Topological Sort

About the pattern

Examples

Does your problem match this pattern?

Real-world problems

Strategy time!