3
$\begingroup$

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:

  1. 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)
  2. 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?

Improve this question
$\endgroup$
3
  • $\begingroup$ The set of all paths containing a given edge can be exponentially large, so no data structure can explicitly store those paths in an efficient way. I suggest you list what operations you want to be able to perform on the data structure. $\endgroup$ Commented Aug 7, 2018 at 22:43
  • $\begingroup$ An exponential bound is not ideal, of course. However, algorithms of that complexity class might still be viable in constrained contexts. Does the current state of computer science research recommend any specific technique -- even despite less-than-customarily-desirable performance? Perhaps, for instance, some methods work reasonably well in practice, for most empirically encountered graphs (with common characteristics I myself wouldn't be able to identify or describe). Or perhaps theory advises use of particular heuristics. $\endgroup$ Commented Aug 8, 2018 at 0:01
  • $\begingroup$ In any case, I wonder whether my mentioning that my interest is not in an initial enumeration of all paths throughout a graph but in updating a preexisting tabulation of paths when a new edge is embedded in a graph might make my problem more tractable. Perhaps not, but as D.W. asked for the operations I need to support, that qualification may more clearly express my primary requirement for any data structure suggested. $\endgroup$ Commented Aug 8, 2018 at 0:01

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.