One edit casts a bounded shadow

File A feeds library B; B and independent library C feed application D. Editing A can affect A, B, and D, but not C. Rebuild-everything is sound and wasteful; rebuild-only-A is fast and stale.

The graph carrier contains nodes and dependency edges. An edit seeds a worklist. Recompute an affected node only after changed prerequisites settle; enqueue its dependents only when its observable output actually changes. Stop when the worklist is empty—a fixed point where another propagation step changes nothing.

A directed acyclic graph admits topological scheduling. Cycles require a different contract: reject them, collapse a deliberately recursive component, or iterate a monotone computation to a bounded fixed point. “Keep trying” is not a termination proof.

Where the model stops

Reachability is conservative: a reachable node may still produce the same output. Exact change detection belongs inside recomputation. Hidden inputs such as clocks or undeclared files make the graph dishonest; no scheduler can invalidate an edge it was never told exists.

Lessons

• Dependency reachability bounds possible impact.
• Output equality can stop propagation early.
• DAGs schedule directly; cycles need an explicit semantic policy.
• Hidden inputs defeat incremental correctness.

Practice

1. Compute the affected cone for a five-node graph from memory.
2. Distinguish invalidated from observably changed.
3. Transfer the model to spreadsheet cells or derived UI state.

Repeated traversal can still be costly. The next chapter stores summaries whose combination law makes local repair possible.

References

1. “G. Ramalingam and Thomas Reps, “An Incremental Algorithm for a Generalization of the Shortest-Path Problem”.” — principled incremental graph computation.
2. “Bazel documentation, “Dependencies”.” — declared dependency graphs in a production build system.