Skip to main content

Module graph

Module graph 

Source
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§

DependencyGraph
The dependency graph of one worksheet’s formulas.