i am looking for a nice algorithm to solve the following problem.
I have the following listing of VARIABLES and FORMULAS (result of var is the sum of all formulas):
var1, result=10
- 5+5=10
var2, result=15
- var1+5
var3, result=30
- var1+var2+5
now i am looking for a nice way to calculate all references. if i am changing var1 and the result is 15 now, i have to calculate all referenced to var1. first i came across var2 and recalc var2, if the result of var2 changed i have to recalc all referenced formulas to var2. therefore i would recalc var3 twice (var2 changed, var1 changed)...
is there any solution to not calc var3 twice in this scenario?
thx!
Yes, you can ensure you recalculate each variable only once (at most), by using the fact that there are no cyclic dependencies (no way a variable x needs y in order to be calculated, and in the same time y also needs x).
This is done by modeling the problem as a graph, where all variables are vertices, and a "needed" relation is a directed edge. (So, if variable x "needs" variable y to be calculated, there is an edge (y,x)).
Now, since the No-Cyclic dependency, this is actually a Directed Acyclic Graph, which you can do topological sort (This can be done only once in pre-processing). Note that it is very possible that in your case, the graph is already sorted, sine it is given as a chronological sequence of events, and the chronological order is a topological sort.
Do a topological sort on the graph (if needed), and whenever variables are changed:
Upon variable change:
1. Mark all changed variables
2. From first variable to last (according to topological sort), for each variable x:
2.1. If there is some dependency `(y,x)` on the graph such that `y` is marked:
2.1.1. mark x
2.1.2. recalculate x
It is easy to see that each variable is calculated at most once according to this approach.
Keep a list of variables/formulas that needs to be recalculated. Using this list you can see whether all dependencies are up-to-date or not. If this is not the case, you should postpone updating the variable.
Going back to your example and lets say var1 changes.
First step is to put var in the list and check all depending variables/formulas. These are var2 and var3, so put them in the list as well.
Next check the depending variables/formulas of var2 (as you put it in the list as well), this is var3, it is already in the list, so leave it. Last check var3 (you added it as well), nothing is depending on var3 so you are done. (Note the recursive behavior!)
The second step is to update your values. So find a variable/formula that has all its dependencies. Only var1 has not dependencies, so pop it from the list and calculate its value.
Next find another variable/formula in the list, var3 is still depending on var2 (which is still/also in the list), so only var2 is suitable to process. Therefore pop var2 from the list and calculate its value.
Continue processing the list, until it is empty.
Assuming you do not have circular dependencies: Everything is calculated only once!