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 checkoutschemas → api → appsortPkgs orders schemas before the web app and the API that depend on it.Related terms
- Kahn's algorithm — A topological sort that repeatedly removes a vertex with no remaining incoming edges and lowers the in-degree of its neighbours.
- directed acyclic graph — A directed graph with no cycles, so following edges can never bring you back to where you started.
- in-degree — The number of edges pointing into a vertex of a directed graph; out-degree counts the edges leaving it.
- dependency — Anything a program needs in order to work, such as a library, a tool or another service.
- BIA — A study of which business processes matter most and how the harm from an outage grows over time, used to set recovery targets.
- RTO — Recovery time objective: how long the business can accept a service being down before it is restored.
- Python — A popular general-purpose programming language known for readable code and a large standard library.
- task graph — A map of which build tasks depend on which others, used to decide what must run first and what can run at the same time.
- dependsOn — The turbo.json setting that lists which tasks must finish before a task runs, where a leading caret means the same task in every dependency package.
Taught in
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Business Impact Analysis, RTO & RPO Modeling — Cybersecurity Fundamentals, GRC & Cryptography
- Monorepo Architecture: Workspaces & Turborepo — Production Full-Stack Engineering
- Unified Build Pipelines: Caching & Dependency Graphs — Production Full-Stack Engineering