Directed Acyclic Graphs

Graphs are often used to solve many types of problems. One well-known example is ordering, commonly known as topological sorting of directed acyclic graphs (DAGs). It’s the reason people don’t show up to work dressed as Superman.

Suppose a set of tasks must be accomplished, and some sub-tasks must be completed before others. A topological sort gives an ordering that satisfies these requirements.

In daily life, a shirt is worn before a blazer, so “wearing a shirt” must come before “wearing a blazer” in any valid topological ordering.

Applications that process tabular data, spreadsheets, for example, allow cell values to be calculated using formulas that reference other cells. Before a cell’s value can be computed, the values of all cells it depends on must already be calculated. To do this correctly, the application builds a dependency graph and topologically sorts it, then evaluates each cell in that order.

This is exactly why circular references cause errors in spreadsheets: a cycle in the dependency graph means no valid topological ordering exists.

Topological sort is commonly implemented using depth-first search, though other approaches, such as Kahn’s algorithm, are widely used too.