A DAG is a directed graph with no cycles: following the arrows, you can never return to where you started. Unlike a tree, a node can have several parents. That's exactly the shape of anything with dependencies: a step that can start only after two others have finished.
Because there are no cycles, the nodes can always be lined up in a topological order: an order where every node comes after everything it depends on. That order is the plan of execution. Steps with no path between them, like 'Manager OK' and 'Budget check' in the figure, can run in parallel.
In real life
An invoice can be paid only after the manager approves it and the budget check passes, and both of those need the invoice to be submitted first. Build systems (compile before link), spreadsheet formulas, and data pipelines in tools like Airflow are all DAGs.
Check yourself
In a DAG, the step 'Pay' has two incoming edges: from 'Manager OK' and from 'Budget check'. What does that mean?
Topological order and cycle detection
To compute a topological order, count each node's incoming edges (its in-degree). Start with the nodes at zero: they depend on nothing. Take one, add it to the order, and remove its outgoing edges; any node whose count drops to zero is now ready. Repeat. This is Kahn's algorithm, O(nodes + edges).
It also detects cycles for free. If the queue empties before every node is placed, the remaining nodes are in a loop or wait on one, and none can ever start. In a workflow that's a deadlock; in a build it's a circular dependency; in a spreadsheet it's a circular reference error.
In real life
Build tools order their steps this way; cargo, for example, refuses to build when two crates depend on each other. Excel shows 'circular reference' for the same reason.
In code: Python · Rust
from graphlib import TopologicalSorter, CycleError # standard library, 3.9+
steps = {
"Manager OK": {"Submit"}, # step: the steps it waits for
"Budget check": {"Submit"},
"Pay": {"Manager OK", "Budget check"},
}
print(list(TopologicalSorter(steps).static_order()))
# ['Submit', 'Manager OK', 'Budget check', 'Pay'] (the middle two in either order)
try:
list(TopologicalSorter({"A": {"B"}, "B": {"A"}}).static_order())
except CycleError:
print("deadlock: A and B wait for each other")
use std::collections::{HashMap, VecDeque};
// edges: (from, to) means `to` waits for `from`
fn topo<'a>(nodes: &[&'a str], edges: &[(&'a str, &'a str)]) -> Option<Vec<&'a str>> {
let mut indeg: HashMap<&str, usize> = nodes.iter().map(|&n| (n, 0)).collect();
for &(_, to) in edges { *indeg.get_mut(to).unwrap() += 1; }
let mut q: VecDeque<&str> = nodes.iter().copied().filter(|n| indeg[n] == 0).collect();
let mut order = vec![];
while let Some(n) = q.pop_front() {
order.push(n);
for &(from, to) in edges {
if from == n {
let d = indeg.get_mut(to).unwrap();
*d -= 1;
if *d == 0 { q.push_back(to); }
}
}
}
if order.len() == nodes.len() { Some(order) } else { None } // None: a cycle
}
Python ships graphlib.TopologicalSorter; it raises CycleError on a loop.
The Rust version scans all edges per node to stay short; store an adjacency list to make it O(nodes + edges).
Check yourself
Kahn's algorithm stops with three steps never placed in the order. What does that tell you?
