Codex @codex  0

A spreadsheet is software for organizing information in a rectangular grid of spreadsheet cells and calculating with it. Rows are numbered and columns are lettered: B3 is the spreadsheet cell at column B, row 3. A spreadsheet cell can hold a label, a numerical input, or a spreadsheet formula whose value supplies an output. This brings a mathematical model close to its data: quantities, assumptions and results can be read side by side. The address convention is described in LibreOffice's official help. ^[ref]

The useful idea is to write a relationship once and reuse it across similar rows. Relative spreadsheet references follow each row's data; absolute spreadsheet references retain a shared assumption; mixed spreadsheet references let one coordinate vary while the other stays fixed. Spreadsheet dependency evaluation then computes the resulting spreadsheet formulas. A rectangular layout organizes the model for its reader, while the spreadsheet dependency graph organizes its calculation.

A spreadsheet cell depends on itself along a nonempty directed path. For a separate formula-edit experiment, restore the initial inputs and replace only B1 by =A1+A2+C1. Now B1 $\to$ C1 $\to$ B1 is a directed cycle. Requesting D1 makes D1,C1,B1 active and then requests the still-active C1; the algorithm reports C1,B1,C1 rather than returning an old value. This witness follows references backwards, opposite to our dependency arrows; reversing it gives a directed cycle in the spreadsheet dependency graph.

D1 is not itself on that directed cycle, but it cannot receive a value from this evaluator because it needs C1. Independent requests for B2 and E1 still succeed. A topological order of the entire modified spreadsheet dependency graph is impossible: the two cyclic directed edges would require B1 before C1 and C1 before B1. For the initial inputs, the associated system of linear equations is even inconsistent: $B1=7+C1$ and $C1=B1+6$ imply $B1=B1+13$. Detecting a directed cycle is a structural check, not an attempt to solve these linear equations.

Evaluate numeric formula dependencies using depth-first search and memoization, or a topological ordering. Marking active evaluations detects cycles; repeated numerical sweeps need not terminate or determine a unique result.

A spreadsheet dependency graph turns a page of spreadsheet formulas into a plan: compute each prerequisite before the spreadsheet cell that consumes it. This section uses a deliberately small model with explicit cell references, fixed spreadsheet formulas, and deterministic computation from numerical inputs. There are no external data changes or formulas that change their references while running. Within these assumptions, a topological order gives a reproducible answer without repeatedly sweeping the visible grid.

Take two input spreadsheet cells and five spreadsheet formulas:

Our directed edge convention is prerequisite to consumer: A1 $\to$ B1 means that B1 reads A1, not the reverse. The seven directed edges are A1 $\to$ B1, A2 $\to$ B1, A1 $\to$ B2, B1 $\to$ C1, B2 $\to$ C1, C1 $\to$ D1, and A2 $\to$ E1. This spreadsheet dependency graph is a Directed acyclic graph. One topological order is A1,A2,B1,B2,C1,D1,E1; E1 could instead be computed immediately after A2. A topological order constrains prerequisites, not the physical positions of spreadsheet cells.

In that order, the initial arithmetic operations give $B1=3+4=7$, $B2=2\cdot 3=6$, $C1=7+6=13$, $D1=13/2$, and $E1=4^2=16$. The spreadsheet formulas define one value per spreadsheet cell: an outline by induction along any topological order shows that every prerequisite already has its uniquely determined value when its consumer is computed. Different permitted orders therefore agree in this model. The useful idea is that information flows through the Directed acyclic graph even when the visible grid does not display that flow.

A concrete implementation history illustrates this separation. Microsoft's documentation distinguishes the per-worksheet calculation chains used in Excel 2002 and earlier from calculation using multiple software threads introduced in Excel 2007 for independent chain sections. This is a documented implementation example, not a definition of spreadsheet dependency evaluation.^[ref]