5
$\begingroup$

Is there an incremental directed graph data structure that has the following properties:

  • Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-structures)
  • The accessible DAG is kept as a transitive reduction (notwithstanding other helper data-structures)
  • It should be optimized for a sparse graph (adjacency lists)
  • It should condense cycles as they are introduced, keeps a mapping between equivalent vertices that are all replaced with one "representative" vertex
  • Ability to quickly answer quickly ancestor/descendant/transitive/relationship queries (in $\mathcal{O}(1)$ or $\sim\mathcal{O}\left(\log \left|V\right|\right)$ time)
  • Should support vertex, edge insertion, deletion would be nice too
  • Mutable operations (such as insertion) should be as output-sensitive as possible; in other words, the complexity should depend as much as possible on how much the operation must change the graph
  • Ability to record changes over an operation, if requested. Obviously this might necessarily increase the complexity, but the increase should be output-sensitive. Examples:
    • set of deleted vertices (due to condensation)
    • set of deleted edges (due to reduction)
    • set of new decendent relationships from $u$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(u,t)\in G'\wedge path(u,t)\not\in G\right\}$ )
    • set of new ancestor relationships from $v$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(t,v)\in G'\wedge path(t,v)\not\in G\right\}$ )

The closest I can find is here, implementation. I think you can build on this to do have most of the properties I list, but I am wondering if there is anything better/well known, or perhaps if there is a name for this problem.

EDIT:

Related:

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ What is the purpose of the requirement "The accessible DAG is kept as a transitive reduction"? This seems like a pointless requirement (and one that could potentially increase the workload). Have you thought carefully about whether that is truly necessary / well-motivated by your application? What bad thing would happen if you simply omitted that requirement? $\endgroup$
    – D.W. ♦
    Oct 4, 2013 at 5:06
  • $\begingroup$ What does "record changes over an operation" mean? Can you make that more precise? Precisely what sort of changes do you require must be recorded? $\endgroup$
    – D.W. ♦
    Oct 4, 2013 at 5:07
  • $\begingroup$ @D.W. The accessible DAG allows for a natural listing of ancestors or descendants of a vertex via a graph traversal algorithm. Possibly it has other uses: it is slightly more general than a $descendants(G,u) \rightarrow \left\{ v ~ | ~ path(u,v) \in G\right\}$ function would be in its stead. Feel free to give insights that relax the requirements, and have trade-offs. $\endgroup$
    – Realz Slaw
    Oct 4, 2013 at 5:11
  • 1
    $\begingroup$ Got it. So it sounds like the real requirement is that, given a node $v$, we must be able to enumerate all reachable nodes from $v$ (or all nodes that can reach $v$) efficiently. Thanks for the explanation. P.S. Regarding the name for this data structure: the standard name in the literature is "fully dynamic transitive closure". There are many such schemes, with a range of tradeoffs regarding the time to do an update, the time to do a query, and the space cost. $\endgroup$
    – D.W. ♦
    Oct 4, 2013 at 5:15
  • $\begingroup$ @D.W. "record changes over an operation" - It means that sometimes it is useful to get output-sensitive changes to the graph. For example, a new relationship might incur many new relationships, do to the transitivity. These new relationships might be interesting to the user of the data-structure. Also, the insertion-condensation might make several vertices equivalent to each-other, this information might be interesting to the user. $\endgroup$
    – Realz Slaw
    Oct 4, 2013 at 5:17

1 Answer 1

Reset to default
5
$\begingroup$

Some keywords to help you search for related work: dynamic transitive closure, dynamic reachability problem, dynamic cycle detection. Because you want to allow both insertions and deletions, this is known as fully dynamic transitive closure.

Alternatively, you might want to consider whether there could be some structure in the particular graphs that arise in your setting that might help you build schemes that are faster than the general case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sorry I wasn't clear; "keeps the graph as a transitive reduction" wasn't meant to be "must be stored [only] as a transitive reduction", just that there must be a DAG, that is accessible (first bullet point), and this DAG should be a transitive reduction (second bullet point). Edited now to be more clear. $\endgroup$
    – Realz Slaw
    Oct 4, 2013 at 2:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.