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:

  1. Insert (X, Y ): Insert a new element Y immediately after element X in the total order.
  2. Delete (X): Remove an element X from the total order.
  3. 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?



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.