Example of Data
This is the data for one monkey. There are many similar but different monkeys.
X(Y,Z) means Y, Z are parent of X. A(D,E) If monkey see banna (D) and monkey is hungry (E), it squeaks (A). B(E,F) If monkey is hungry (E), and monkey see other monkey, it jumps(B). C(D,F) If monkey see banna (D), and it is not hungry (E), it walks away(C). 0(A,B) If monkey squeak(A) and jumps(B), it grabs the banna with priority 10 and reduce priority for doing other things (0). D, E, F are the source.
Notice that this is not a tree. A-C-D is a undirected cycle. Trees have no cycle (wikipedia). The priority and the words at right are not part of the data structure I am interested in (at this moment).
Is there a data structure that conserves memory and allow reasonably efficient recalculation of values for the following case?
The data structure is for the rete algorithm (https://en.wikipedia.org/wiki/Rete_algorithm).
[Description of the data]
- Each node (except the end points) has exactly two parents.
- Any two parents have at most one child.
- A node can be the parent of multiple nodes.
- Each node has value, which is a boolean. (Or an array of fixed number of boolean for sharing the nodes between different monkeys.)
- Value of child is logical and of values of its parents.
- Want to keep all values of the nodes to save recalculation time.
[Operations on the data structure]
- The structure of the graphs never changes. I don't mind taking a long time to construct the data structure.
- When value of a node changes, values of its children are recalculated. The values of the end points occasionally changes in every cycles of calculation.
- Want to know if the predefined interesting nodes (for example we know that node 0,3,and 5 are interesting.) change value.
- Don't need to query or look up for any particular values among the nodes. Also don't need to output values of all the nodes (that would take too much time.)
There are lots of nodes, and lots of parent-child relationships, because there are lots and lots of rules, and lots of slightly different monkeys.
(I have never taken any computer science class... I learned everything online. Sorry if I use the wrong terms.)