4 ms·
Side question: How do you make DAGs immutable? Unlike trees where changing a node only requires a path copy of all ancestors, changing a node in a DAG has the p
by fyp 7y ago
Side question: How do you make DAGs immutable? Unlike trees where changing a node only requires a path copy of all ancestors, changing a node in a DAG has the potential to affect all other nodes. There are techniques such as using fat nodes[1] but I don't know of anyone using them in the real world.
[1] https://en.wikipedia.org/wiki/Persistent_data_structure#Fat_node https://en.wikipedia.org/wiki/Persistent_data_structure#Fat_...
- raphlinus 7y agoYou do need to trace all predecessors in this case, but in practice I don't think it's a serious problem. The kinds of graphs you'll get in UI are probably best thought of as trees with the possibility of shared resources (for example, all buttons of the same size might share the same background). On something like a theme change, I'd just rebuild the tree, although in theory you could be smarter and apply changes incrementally at a fine grain.