How do spreadsheets update cells correctly / know what to update?

Question

Spreadsheets are so beautiful! Cells can be linked on top of each other and if any formula / value / whatever changes in one of the cells everything updates correctly!

Does anyone know the general concept on how spreadsheets do this? What I'm talking about is if A1 = 1, A2 = 2 and A3 = A1+A2. Then I change A1 or A2 and A3 knows to update and does it correctly. Of course it can't update it wrong in this example but in more complicated examples it has to update "lower" cells first before updating things built on top of it.

When programming myself I am having such a hassle of updating everything correctly after the underlying data changes. Sometimes not everything has to be updated so I don't want to update everything. It's just a mess.

I hope my tags are correct, and that discussions like these are allowed. Thanks!

Answer 1

I don't know how spreadsheets do this in practice. But my idea here is inspired from topological sorting on graphs. Consider formula A3 = A1+A2. Cells will become nodes for graph. Formulas will govern the edge. Edge represent dependency. e.g. A3 depends on A1. Therefore we have two edges from A3 to A1 and A3 to A2. Now a topological sort of above graph will give you exact evaluation order. ie A1 A2 and A3.

Also note this graph needs to be Directed Acyclic Graph (DAG) if one uses this algorithm. ie it doesn't contain any cycles. As far as I know excel does detect circular dependency in it's formulas.

The underlying algorithm of topo-sort uses DFS (depth first search) which can detect cycles too. Hence one can report such cycles.