php - Algorithm to calculate referenced formulas only once -

i looking nice algorithm solve following problem.

i have following listing of variables , formulas (result of var sum of formulas):

var1, result=10   - 5+5=10  var2, result=15   - var1+5  var3, result=30   - var1+var2+5 

now looking nice way calculate references. if changing var1 , result 15 now, have calculate referenced var1. first came across var2 , recalc var2, if result of var2 changed have recalc referenced formulas var2. therefore recalc var3 twice (var2 changed, var1 changed)...

is there solution not calc var3 twice in scenario?

thx!

yes, can ensure recalculate each variable once (at most), using fact there no cyclic dependencies (no way variable x needs y in order calculated, , in same time y needs x).

this done modeling problem graph, variables vertices, , "needed" relation directed edge. (so, if variable x "needs" variable y calculated, there edge (y,x)).

now, since no-cyclic dependency, directed acyclic graph, can topological sort (this can done once in pre-processing). note possible in case, graph sorted, sine given chronological sequence of events, , chronological order topological sort.

do topological sort on graph (if needed), , whenever variables changed:

upon variable change: 1. mark changed variables 2. first variable last (according topological sort), each variable x:       2.1. if there dependency `(y,x)` on graph such `y` marked:            2.1.1. mark x            2.1.2. recalculate x 

it easy see each variable calculated @ once according approach.