An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

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:

• 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? – D.W. Oct 4 '13 at 5:06
• 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? – D.W. Oct 4 '13 at 5:07
• @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. – Realz Slaw Oct 4 '13 at 5:11
• 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. – D.W. Oct 4 '13 at 5:15
• @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. – Realz Slaw Oct 4 '13 at 5:17