topological sort

An ordering of a directed graph's vertices in which every edge points from an earlier vertex to a later one.

In more detail

For a dependency graph it gives an order in which every task comes after everything it depends on. It exists only if the graph has no cycles, and there are often several valid orders. It can be computed with Kahn's algorithm or with DFS finishing times, both O(V + E).

Examples

for p in TopologicalSorter(deps).static_order():
identity is restored before payments, and both before checkout
schemas → api → app
sortPkgs orders schemas before the web app and the API that depend on it.

Related terms

Taught in

References