Whats the best approach (Algorithim) to continually calculate cascading relationships between objects?

Question

For instance A+B=C C+D=E E+F=G as changes are made to each node the associated nodes are recalculated. The image below is a simplistic example of what I am trying to do.

Further clarification The structure for each object is identical. the inputs would be prices as each price changes it would have a cascading effect on the prices downstream. so in the example above A+B=C would become 5+6=11. etc. Any help would be appreciated.

Changes take place constantly (possibly every second), as each value is changed I would need to be notified (Event fired).

Thanks

![alt text][1]

Answer 1

As long as your graph isn't changing, only the values, you can do a topological sort of your graph. Then walk the graph in topological sort order starting at the value(s) which changed. If the changes are going to be a sparse part of the graph, assign each node an index in topological sort order and use a priority queue to decide which node to do next.

Answer 2

The simplest way would jsut be an event based method. Each node has an "onchanged" event and anything that uses that node can subscribe to that event. After a node has updated itself then it raises that event and lets anything else that needs to know.

If your dependancies are more complex then you may need to have something else managing the updates to optimise things. eg if A effects B and C and C also effects B (eg B=A+C and C=A+1) then a simple method might update a, then b, then C then B again. This works but is obviously one mroe update than is required. The exact way of optimising the updates will depend on how complex your dependancy tree is.