Network of dependent values ​​- how to count them only once?

Question

I hope one of you guys can figure it out.

I have an array containing many objects. Each object in the array contains two things:

• The value is subject to change.
• A list of zero or more other objects in my array that, if their values ​​change, then this object must recalculate its value. This can be cascaded many times from object to object, but there are no dependency cycles.

I believe this is called a network (like a tree, but with multiple parents). In particular, it is an acyclic schedule with direct access.

What I'm doing right now is: when I change the value of an object, I check every object in the array to see if it depends on the object I just changed. If this happens, I will tell this child to count. Then the child tells the children in the same way, etc.

This works (values ​​are updated correctly), but very slowly when a change occurs that cascades broadly and deeply. This is due to the fact that if an object has many parents that change, it recounts for each of them, and also indicates that the children are counted every time, so they receive several messages from only one parent. These are fast snowballs, until many objects are counted dozens of times.

What is the best way to only recount each object once, after all its parents have counted?

Thank you for your help.

Answer 1

It looks like you want Topological sorting of acyclic graph with binding . See for example http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/DAG/

If your schedule does not change constantly, you just have to sort it once and from now on you can perform your updates in the order from left to right, knowing that at each step there are a set of nodes that you will add to the list to be calculated, all to the right of the current position. There you can optimize this a bit, perhaps save them in a simple heap, select the leftmost value each time, recount it and add back any nodes it refers to, or as someone suggested, if the full dependency graph is small enough , just save it on each node in the order in which it should be calculated (as found using topological sorting).

Answer 2

Create an acyclic digraph with the vertices given by the nodes in your array, and the edge i --> j whenever a change in i requires recalc j (i.e. i is on the list for object j ). The graph is acyclic if your process is finite.

Now that i changed, do the first width search to recalculate the dependent nodes. First go through, collect all nodes j such that i --> j . Count those j . On the second pass, take every j that changed and got its dependents j --> k . Then recount those k immediately. Keep on taking all the k dependents who have changed , and so on, until only the leaves are left.

This requires that you keep a list of neighbors, which is the inverse of the information you have. Therefore, you need to do one pass to get directed edges (fill the array so that the record i has an array of all j for which i --> j ).

Answer 3

When the value is updated, create a list of other elements whose values ​​still need to be recalculated. Before recalculating the value of an item in this list, make sure that none of the other items on which it depends is also in the list. This ensures that the item will only be recounted once. Since there are no cyclic dependencies, there will always be at least one element in the list of elements to be recalculated that has already listed all its dependent elements.

Pseudocode:

 Create a set S Add initially updated element to S while S is not empty remove an element X from S whose value does not depend on any other elements in E do not exist in S recalculate X value and add any elements that depend on X value to S