The formula (the core equation(s), each with a one-line reading of what it says)
A directed acyclic graph is a set of vertices V and directed edges E, where each edge points from one vertex to another and no path ever returns to where it started.
Edge u -> v means "u must come before v"
Reads: the arrow is a precedence constraint — do u, then v is allowed to happen.
Topological order: a linear list of all vertices such that
for every edge u -> v, u appears before v.
Reads: flatten the graph into a single line that never violates an arrow.
A valid topological order exists <=> the graph has no directed cycle.
Reads: the ordering is possible if and only if the graph is a true DAG. A cycle is a contradiction — a before b before a — and no line can satisfy it.
Kahn's method:
in-degree(v) = number of edges pointing INTO v
1. output every vertex whose in-degree is 0
2. delete it and its outgoing edges (which lowers other in-degrees)
3. repeat until the graph is empty
Reads: whatever has no unmet prerequisites is ready now; do it, cross it off, see what became ready.
Runtime: O(|V| + |E|)
Reads: you touch every vertex once and every edge once. Linear. It does not get cheaper, and for this problem it does not need to.
Where you meet it (2-4 concrete engineering situations, specific: bench, test stand, review board)
The build. Every make, every Bazel or CMake graph, every CI pipeline is a DAG. Object files depend on sources and headers; the linker depends on the objects. The build tool topologically sorts the dependency graph to decide the order, and — because independent branches have no edge between them — it hands the independent pieces to separate cores in parallel. When the build errors out with "circular dependency detected," a cycle-detection pass just found an arrow pointing the wrong way.
The test stand power-up sequence. A test setup has an order that is not negotiable: bus voltage before excitation, excitation before the DAQ arms, DAQ armed before the actuator command goes out. Write those constraints as edges and the safe startup script is a topological sort of them. Add a new sensor that needs the bench supply, drop in one edge, re-sort, and the sequence updates itself instead of you re-reading the whole procedure by hand.
Spreadsheet and signal-chain recalculation. A cell that references other cells is a vertex with incoming edges. When one input changes, the engine re-evaluates the dependents in topological order so every cell reads final values, never stale ones. The same logic runs a cascaded RF or instrumentation chain in a model: each stage's output feeds the next, and you evaluate them in dependency order.
The schedule review board. Lay a project's tasks out as a network — task A must finish before task B starts — and you have a DAG. Topological order gives you a legal sequence to work in; walking that order while summing durations gives you the critical path, the chain that sets the whole schedule's length. Slip anything on the critical path and the delivery date slips with it. This is exactly the problem PERT was invented to handle.
How it works (the real substance — behavior, gotchas, limits of validity, the mistake people make)
Start with the diamond: A -> B, A -> C, B -> D, C -> D. Four tasks, A first, D last, B and C in the middle with no arrow between them. Enumerate every ordering that respects the arrows and you get exactly two: A B C D and A C B D. That is the first thing to internalize — the topological order is usually not unique. B and C are independent; the sort is free to pick either first, or run them at the same time. A chain of four tasks in a strict line has exactly one order. Four tasks with no dependencies at all have 24. Most real graphs sit between those extremes, and every valid order is equally correct.
Kahn's method is the version that matches how a person actually thinks. Compute each vertex's in-degree — how many prerequisites it is still waiting on. Anything at zero is ready; output it, and decrement the in-degree of everything it fed. Some of those drop to zero and become ready in turn. Run the diamond through it and you get A, then B and C (both hit zero together), then D — a complete list of all four. The depth-first version does the same job from the other end: walk as deep as you can, and record each vertex only after all its descendants are recorded, which builds the order in reverse.
Here is the gotcha that makes the whole thing worth its keep. A topological sort is also the cleanest cycle detector you own. Add one bad edge to the diamond — D -> A, so now A waits on D which waits on A — and run Kahn's method again. Nothing has in-degree zero to begin with. The algorithm outputs zero vertices and halts with the graph non-empty. Whenever the sort finishes and the output count is less than the vertex count, the leftovers are exactly the tasks tangled in a cycle. That is your circular-dependency error, and it points straight at the offending loop.
The mistake people make is trusting a hand-built ordering and never checking for the cycle. Someone edits a build file, a startup script, or a schedule network, quietly introduces a back-edge, and the ordering they wrote down still looks plausible. It runs fine until the day the tool actually chases the loop and hangs, or the schedule tool refuses to calculate at all and throws a circular-logic error. The fix is not cleverness — it is running the sort and confirming it consumed every vertex. If it did not, you do not have a DAG, and no amount of reordering will save you until you delete an arrow.
Two limits worth stating plainly. First, "acyclic" is the entire load-bearing assumption; the instant a real cycle exists, no linear order is valid and the honest answer is to break the cycle, not to force an order. Second, topological order tells you a legal sequence, not the fastest one. To get the critical path you still have to weight the edges with durations and walk the sorted order accumulating time. The sort is the scaffold; the schedule math sits on top of it.
History (who derived it and when, told as a short story with inline [n] citations)
The problem showed up wearing a hard hat. In 1957 and 1958 the U.S. Navy's Special Projects Office, working with Booz Allen Hamilton, needed a way to schedule the thousands of interdependent tasks in the Polaris fleet ballistic missile program, and the answer was PERT — the Program Evaluation and Review Technique [4]. In that picture a project is a network: milestones are vertices, and the tasks between them are edges you cannot start until the prior milestone lands. Getting a legal task order out of that network, and from it the critical path that governs the delivery date, is precisely a topological sort. The algorithms for actually computing that order were first studied a few years later, in the early 1960s, in exactly that PERT scheduling context [1] — the work culminating in Kahn's 1962 paper below.
The clean, general statement of the algorithm came from Arthur B. Kahn in November 1962, in a paper titled "Topological sorting of large networks" in the Communications of the ACM [1][2]. Kahn's recipe is the in-degree method above: repeatedly pull out a vertex with nothing pointing into it, output it, remove its edges, repeat. Simple enough to do on paper, and it carries the cycle detector for free — if you ever run out of zero-in-degree vertices before the network is empty, the leftovers form a loop.
The other standard approach, the one built on depth-first search, seems to have first appeared in print later. It is generally credited to Robert Tarjan's 1976 paper "Edge-disjoint spanning trees and depth-first search" in Acta Informatica [1][3] — Tarjan being the same researcher whose depth-first-search machinery underlies a whole shelf of graph algorithms. The DFS version records each vertex after its descendants, yielding the reverse order. Both methods run in time linear in the vertices plus the edges, and both landed in the textbook canon; the topological-sort section of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein presents the depth-first form as the standard teaching version [1]. The engineering lesson is the tidy part: a scheduling headache from a late-1950s missile program turned into a two-line idea that now quietly orders every software build on the planet.