Expand description
The dependency DAG — formulas, precedents, dependents, evaluation order.
The graph is two index maps over one source of truth:
- forward: formula cell → the cells its formula reads (precedents),
- reverse: cell → the formula cells that read it (dependents).
Both directions are maintained on every add
and remove, so the two queries are
always consistent by construction — a property the test suite checks on
random graphs.
§Determinism
Every derived quantity — topological_order,
dirty_subgraph,
has_circular — is a pure function of
the edge set: Kahn’s algorithm with a sorted ready set and Tarjan SCC
with ascending neighbor order. Same edges in, same order out, on every
machine, every run.
§Cycle policy
Cycles are represented, not rejected at insert: real workbooks contain
them, and an engine needs [has_circular] to report them while the rest
of the graph still evaluates. Cycle members are excluded from
[topological_order] (no valid position exists for them) and from
[dirty_subgraph] roots’ propagation only insofar as they cannot be
ordered — they still appear when the edit reaches them.
Structs§
- Dependency
Graph - The dependency graph of one worksheet’s formulas.