What is a planning graph (DAG)?
A planning graph is a directed acyclic graph (DAG) that represents a plan: each node is a unit of work (a task, or a group of tasks), and each directed edge records a dependency, meaning the work it points from must finish before the work it points to can start. "Acyclic" means the arrows can never form a loop, because no piece of work can transitively depend on its own completion.
That is the whole definition. The rest is consequences, and they are substantial.
The three parts, precisely#
| Term | Meaning in a plan |
|---|---|
| Directed | Every dependency has a direction: A enables B, not the reverse |
| Acyclic | No dependency loops; there is always something you can start |
| Graph | Tasks connect in a web, not a line: real plans branch and merge |
The acyclicity is the load-bearing property. Because a DAG has no cycles, it always admits a topological order: a sequence of tasks that respects every dependency. That single guarantee is what makes a plan executable at all, and it is the algorithm Topolog is named after (topological sort).
Why represent plans this way#
Most planning artefacts store conclusions: a Gantt chart stores dates, a to-do list stores an order. A planning graph stores the reasons (the dependencies), and every conclusion is then computed from it:
- Sort the graph topologically and you get the to-do list.
- Partition nodes by status, with "blocked" computed from unfinished predecessors, and you get the Kanban board.
- Project the graph onto a calendar through people's availability and you get the Gantt chart.
Because all three are projections of one object, they cannot disagree with each other, which is the argument made at length in the one-DAG article. The graph also enables analysis no flat list supports: finding the critical path, simulating completion dates, and showing the ripple effect of a single slipped task.
What a planning graph is not#
It is not a flowchart (flowcharts model control flow with loops and decisions for a machine; planning graphs model work for people and must stay acyclic). It is not a mind map (mind maps record associations, not dependencies, and have no execution semantics). And repeated work ("revise until approved") does not break the no-loops rule: it is modelled as a bounded iteration node containing the repetition, rather than a backwards edge (how loops fit in a DAG).
In practice#
In Topolog, every plan is a planning graph written in a small declarative language, edited either visually on a canvas or as text, and validated structurally before it can drive execution (cycles are rejected with the offending loop named). The dependency-graph docs show the canvas; the deeper essays linked below cover what the representation buys you.