You 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

You 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.