Consider a directed acyclic graph (DAG) of topics and links. Apart from the root topic, topics are situated under one or more parent topics, and links, as well, are situated under one or more parent topics. Now imagine that the DAG changes over time as users add, remove and update link and topic relationships and metadata (name, title, etc.).

Is there a data structure that can capture this dimension of changes to the DAG over time, readily reproducing a version of the DAG at a specific point in time? This would be analogous to resetting Git to a previous HEAD. Unlike Git, however, in which mutations are made to the file system in order to get to another point in time, ideally a single copy of our data structure could allow multiple viewers to access it, without one viewer affecting others' views of it (they could each have different pointers into it, though). Also unlike Git, we can make do with a linear sequence of versions instead of needing a tree of versions. Also unlike Git, we are recovering a DAG rather than a tree (i.e., the file system without hard links).

Perhaps, but not necessarily, the data structure would be a graph of some kind that incorporates the DAG at each point in time in a complex way, which in a sense would make it a super-DAG. Do people know of anything along these lines?

  • $\begingroup$ Is that 1 up to n parents? $\endgroup$
    – Pål GD
    Commented Mar 20, 2021 at 21:42
  • $\begingroup$ @PålGD yes — 1 to n parents; for example, 1, or 2, or 3 parents. (But not 0 parents.) $\endgroup$ Commented Mar 20, 2021 at 23:00
  • 1
    $\begingroup$ I suspect you are looking for a persistent data structure. It's not clear what operations you want to support, so I'm not sure what data structure would be appropriate. $\endgroup$
    – D.W.
    Commented Mar 21, 2021 at 2:28
  • $\begingroup$ @D.W. thank you for the helpful reference. I think I'm looking for a partially persistent form. The operations currently supported on the DAG are insertion of parents/children, deletion, querying of immediate children of a topic, updates of metadata data for links and topics, downset of a topic and intersections of downsets. For the partially persistent form, mutations would not be allowed on earlier versions. A mental model in my head for earlier versions is changing the branch in GitHub, which shows you the tree as seen on the branch (but in this case you wouldn't be able to modify it). $\endgroup$ Commented Mar 21, 2021 at 2:54
  • $\begingroup$ To make things concrete, this is the application I'm referring to: digraph.app/wiki/topics/6f65af62-0f0b-11e9-ab2f-4bae398cebae. $\endgroup$ Commented Mar 21, 2021 at 3:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.