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
    Mar 20 '21 at 21:42
  • $\begingroup$ @PålGD yes — 1 to n parents; for example, 1, or 2, or 3 parents. (But not 0 parents.) $\endgroup$ Mar 20 '21 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.
    Mar 21 '21 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$ Mar 21 '21 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$ Mar 21 '21 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.