I0004 — Implement DAG validation and execution waves
Validate the dependency graph and derive topological execution waves, refusing every malformed graph with a named finding rather than a guess.
DONE wave 3 · p0 · deep-work profile · runs alone
Part of M000 — Milestone and DAG driven development.
Objective
Validate the dependency graph and derive topological execution waves, refusing every malformed graph with a named finding rather than a guess.
Why
A dependency list without validation is a suggestion. A cycle that nobody detects becomes a set of issues that can never be ready and nobody can explain why.
Current state
No graph existed.
Desired state
Unknown, self and duplicate dependencies, duplicate ids and cycles are each rejected by name, and waves are computed by Kahn layering.
Scope
- lib/project.awk
Out of scope
- Estimation or critical-path scheduling
Dependencies
What waits on this
- I0005DONE Implement the plan command surface
- I0006DONE Generate the Mermaid DAG from the graph
- I0010DONE Behavioural tests for schema, status, graph and command
Acceptance criteria
- A cycle is detected and the issues inside it are named
- A self-dependency and an unknown dependency are each a distinct finding
- Waves place an issue one layer past its deepest dependency
- Two issues sharing a wave and a scope path are reported as serialised
Validation
- bash test/run.sh 42_dag_waves
Evidence required
- dag_test
Evidence
| covers | type | command | result | at commit |
|---|---|---|---|---|
| dag_test | test | bash test/run.sh 42_dag_waves | 1 passed, 0 failed | 2dd5915 |
Risk
Low
Timeline
- started
- 2026-09-04T03:12:48Z
- verified
- 2026-09-04T03:12:48Z
- completed
- 2026-09-04T03:12:50Z
Those three fields, the evidence above and the state of the dependencies are all the status is made of. There is no status field to disagree with them.
Canonical record: .ai/repo/project/issues/I0004.yaml. Read it back with majordomus plan show I0004.