Dependency Graph and Recalculation

A workbook is more than cells and values; it is also a graph.

• Nodes are cells (and sometimes named entities).
• Edges point from a dependent formula cell to its precedents.
• Recalc order is derived from graph topology.

Practical behavior

• Editing an input cell marks downstream dependents dirty.
• Recalculation visits dirty subgraphs instead of the entire workbook.
• Cycles are detected and surfaced as errors with location context.

Short example

A1 = 1
B1 = A1 + 1
C1 = B1 * 2

Edit A1 -> 5
Dirty set: B1, C1
Recalc order: B1 then C1

Design implications

• Graph correctness is required for deterministic results.
• Batch operations can reduce repeated invalidation work.
• Stable traversal order helps produce reproducible tests.

Related

• Parse -> AST -> Evaluate -> Workbook
• Workbook Edits and Batching
• Deterministic Testing

Cycle handling

Cycles are detected during graph construction. When a circular dependency is found, the anchor cell receives a #CIRC! error. The dependency graph uses topological sorting; if sorting fails (cycle detected), the involved cells are marked with the circular reference error. Downstream dependents of a cycle cell also receive errors.

Partial recalculation

For a 10,000-row sheet where only one input cell changes, the engine marks only the dependent subgraph dirty. If only 50 cells depend on that input (directly or transitively), only those 50 are re-evaluated rather than all 10,000 rows. The evaluate_cells API allows targeting specific cells for even more precise control.