alt Hacker NewsHow do you consistently update a DAG, like you describe in your medium article, if the functions corresponding to the nodes in the graph are free to create new dependencies willy-nilly? It seems like this would have to be pretty restricted and/or performance killing, because you'd have to evaluate the graph under the assumption that any node could depend on any other node (unless that dependency creates a cycle, presumably). This overhead may not matter if the node functions are expensive relative to the cost of managing the graph, though.
In the article it is assumed that the object of the node owns a vector of it's dependencies locally. We don't need to access the entire edges set all at once. The evaluation process is recursive. Once the node's function re-evaluate, the vector is being updated. Though, the re-evaluation is not happening for every node every time due to the caching system based on the node's value hash comparison and the two-layer monotonic versioning in case of present algorithm. Other incremental computation algorithm have different approaches in verifying on whether the node's function needs to be re-evaluated. Each approach have pros and cons.
You are right, it is assumed that in general the average node function evaluation is more expensive than the cost of graph management. It's not too expensive, but if by chance node's function is notably cheaper, this approach could be suboptimal in certain cases.
The key insight here is that it is assumed the end user don't need to actualize the entire graph each time any random input is being changed. The user observes only a small portion of the graph nodes in real time, and the incremental computation system ensures to minimize required evaluations. If this local observability is not a goal the system is not incremental by definition. For example, in case of Spreadsheets the entire table could be 10000x10000 cells, however the end user typically sees only a small portion of the table on the screen. On a general note the incremental computation systems are closely tied to the GUI-related tasks.