I am sure there must be some existing graph algorithm for what I am trying to do but I just don't know the right search terms.
The algorithm would perform what I am going to call "graph evaluation." I have a graph that is a DAG, and with each node I have an associated boolean function. Broadly:
- We always evaluate the root node's function first.
- When a node has at least one direct parent return true, it must run.
- If a node has no direct parents return true, it must not run.
- However, each node should run at most once (so if two parents of the same child return true, the child still only runs once).
- Also a node should only run after all of its parents have run, or after we are sure any remaining parents will never run during this graph evaluation.
Note that when we say a function must run, we mean it, because the functions are stateful, so previous graph evaluations affect later ones.
The question is, what is the most efficient algorithm to implement this, that minimizes how much book keeping work we need to do as we evaluate in order to satisfy the constraints?
If it helps to make the problem more concrete, you can think of this DAG as representing work that needs to be done using inputs computed by parents -- returning true means a new output was computed and returning false means keep using the last saved value. You don't want to start working until you're sure you know all of your inputs, you want to avoid work all together if your inputs don't change, you don't want to do the same work twice, and you want to avoid work that won't get used (if you recompute as soon as one input changes, it will get thrown away if it turns out your other input changed as well during the same graph evaluation so now you need to recompute again).
Consider the attached example graph below:
- 4 should only evaluate once, even if 2 and 3 both return true.
- Ideally we would only check if we need to run 4 once, instead of once after running 2 and once after running 3.
- If 2 and 3 both return false, ideally we would somehow skip right to evaluating 7, since 4, 5, and 6 all became unreachable at once.
In general we have all the time in the world to analyze the graph and build auxiliary structures, the goal is to make repeated evaluation of the same graph many times as fast as possible.
Approaches that I have thought of that I suspect are not the most efficient:
- Prepare a topologically sorted array of the nodes. We could iterate the entire array every time. We have a parallel bit set where 1 means "should evaluate" (root starts with it at 1, all other nodes 0). When we execute a node if it returns true we set the bit to 1 for each of its children. This also requires us to store for every node what its children are.
- Start evaluating the root. Each time a node is run, if it is true set a bit in the child, and then regardless of true/false decrement a counter associated with each child. As we are iterating the children and decrementing, if a counter reaches 0 check the child's bit, and if true evaluate the child, then regardless of true/false start recursively decrementing its children. This has the downside that if a child has 9999 parents, we will do 9999 decrements and checks against 0 instead of doing only one check after all the parents are evaluated. It seems like we should be able to analyze the graph prior to graph evaluation and come up with a way to avoid this.
