After reading Dimitris Andreou's blog post on reachability, it seems that reachability can be reduced to order-maintenance. A solution to the order-maintenance problem has the following interface:
- Insert (X, Y ): Insert a new element Y immediately after element X in the total order.
- Delete (X): Remove an element X from the total order.
- Order (X, Y ): Determine whether X precedes Y in the total order.
The reachability problem is easily solved by just calling Order(X, Y) to check if Y is reachable from X, but I'm not sure how this works with non-tree DAGs. For example, what if you have a graph like this (from the Multiple inheritance diamond problem):
and you'd like to answer queries like: "Does D inherit from A?" (is A reachable from D). You'd have to call Insert(D, B), Insert(D, C), Insert(B, A), Insert(C, A), and then Order(D, A). However, AFAIK, the Insert(X, Y) method can only be called if Y does not already exist, so this wouldn't work with vertex A.
How can you solve reachability for non-tree DAGs using order-maintenance?
