Are there any standard persistent data structures that facilitate the following?
- tabulating, for each arc in a rooted, oriented, acyclic multigraph, the set of root-emanating paths containing the arc
- keeping accurate tallies of path collections as arcs are added to and removed from the graph
My research to this point suggests two broad possibilities:
- a comonad-like Erwig-style graph decomposition where each edge (or node instead perhaps) points to its collection of coincident root-emanating paths (or some decomposition thereof)
- a radix-tree-like data structure, with root-emanating paths as its keys
However, although the first idea as a roughly conceived strategy seems interesting, I'm not sure whether such an approach is even possible. And the second strategy seems to require an accompanying method for identifying all paths/keys that contain any arc marked for deletion, and so its usefulness may be limited by the efficiency of this secondary indexing scheme.
Might either of the two ideas above suggest a practical means to use some persistent data structure for tabulating a graph's paths? Or if not, are there any unrelated, yet canonical data structures for this purpose?