6

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!

qdii
  • 12,505
  • 10
  • 59
  • 116
user1594138
  • 1,003
  • 3
  • 11
  • 20
  • Each cell has a list of the cells that immediately depend on it. Whenever a cell is changed manually, all the cells in that list are updated, and *their* dependent cells are processed recursively (just as if each of those cells had been manually changed). – j_random_hacker Oct 18 '12 at 18:23
  • Not sure why an `excel` tag was removed, but this has nothing to do with C++. – j_random_hacker Oct 18 '12 at 18:24
  • Yeah I just let it go and deleted my comment. I agree with the c++ part though. But thanks for the answer this is already helping! – user1594138 Oct 18 '12 at 18:24

1 Answers1

6

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.

Ankush
  • 2,454
  • 2
  • 21
  • 27
  • This might be it. Look at the answer in this thread: http://stackoverflow.com/questions/5731932/algorithm-for-finding-circular-references-in-a-spreadsheet - Thanks for the help! :) – user1594138 Oct 18 '12 at 18:34
  • I know this is an old answer, but I'm a little confused. Wouldn't a topological sort give the opposite order here? – qwerty Feb 21 '21 at 20:05