Topological Sorting

To demonstrate that computer scientists can turn just about anything into a graph problem, let’s consider the difficult problem of stirring up a batch of pancakes. The recipe is really quite simple: 1 egg, 1 cup of pancake mix, 1 tablespoon oil, and 343 \over 4 cup of milk. To make pancakes you must heat the griddle, mix all the ingredients together and spoon the mix onto a hot griddle. When the pancakes start to bubble you turn them over and let them cook until they are golden brown on the bottom. Before you eat your pancakes you are going to want to heat up some syrup. Here is this process as a graph:

The steps for making pancakes
The steps for making pancakes

The difficult thing about making pancakes is knowing what to do first. As you can see above you might start by heating the griddle or by adding any of the ingredients to the pancake mix. To help us decide the precise order in which we should do each of the steps required to make our pancakes we turn to a graph algorithm called the topological sort.

A topological sort takes a directed acyclic graph and produces a linear ordering of all its vertices such that if the graph GG contains an edge (v,w)(v,w) then the vertex vv comes before the vertex ww in the ordering. Directed acyclic graphs are used in many applications to indicate the precedence of events. Making pancakes is just one example; other examples include software project schedules, precedence charts for optimizing database queries, and multiplying matrices.

The topological sort is a simple but useful adaptation of a depth first search. The algorithm for the topological sort is as follows:

  1. Perform a depth first search over the graph in order to compute the finish times for each of the vertices.
  2. Store the vertices in a list in decreasing order of finish time.
  3. Return the ordered list as the result of the topological sort

The diagram below shows the depth first forest constructed by conducting a depth first search on the pancake-making graph shown above.

Result of Depth First Search on the Pancake Graph
Result of Depth First Search on the Pancake Graph

Finally, the diagram below shows the results of applying the topological sort algorithm to our graph. Now all the ambiguity has been removed and we know exactly the order in which to perform the pancake making steps.

Result of Topological Sort on Directed Acyclic Graph
Result of Topological Sort on Directed Acyclic Graph

Next: Shortest Path with Dijkstra’s Algorithm

Practical Algorithms and Data Structures

Introduction

Analysis

  1. The Big Picture
  2. Big O Notation
  3. An Anagram Detection Example
  4. Performance of Python Types

Stacks

  1. Introduction to Stacks
  2. A Stack Implementation
  3. Balanced Parentheses
  4. Converting Number Bases
  5. Infix, Prefix and Postfix Expressions

Queues

  1. Introduction to Queues
  2. A Queue Implementation
  3. Simulating Hot Potato

Deques

  1. Introduction to Deques
  2. A Deque Implementation
  3. Palindrome Checker

Lists

  1. Introduction to Lists
  2. Implementing an Unordered List
  3. Implementing an Ordered List

Recursion

  1. Introduction to Recursion
  2. Calculating the Sum of a List of Numbers
  3. The Three Laws of Recursion
  4. Converting an Integer to Any Base
  5. Tower of Hanoi
  6. Dynamic Programming

Searching

  1. Searching
  2. The Sequential Search
  3. The Binary Search
  4. Hashing

Trees

  1. Introduction to Trees
  2. Representing a Tree
  3. Parse Trees
  4. Tree Traversals
  5. Priority Queues with Binary Heaps
  6. Binary Search Trees
  7. AVL Trees

Graphs

  1. Introduction to Graphs
  2. Representing a Graph
  3. Word Ladders
  4. A Knight’s Tour
  5. General Depth First Search
  6. Topological Sorting
  7. Shortest Path with Dijkstra’s Algorithm
  8. Strongly Connected Components
  9. Prim’s Spanning Tree Algorithm