Finding predecessors in DAGs without traversal or search. Is it possible?

[Mountain]

Background:
In trees, there are a two or three ways (maybe more) to find out if
Node A is an ancestor of Node B without traversing the tree.

Preprossing is OK, and one of the solutions I am aware of is here:

"Use [depth first search] pre- and post-order numbers. Na is an
ancestor of Nb iff
pre(Na) < pre(Nb) and post(Na) > post(Nb)."
See
http://groups.google.com/group/comp....coring=d&hl=en

My question:
-------------------
What if, instead of a tree, we have a DAG (i.e., a directed graph with
no directed cycles)? Is it possible to find out if Node A is
predecessor of Node B (in the topological order) without searching or
traversing the graph? Assuming it might be possible, what specific
methods could we use to find out about the predecessorship in this way?
Preprocessing is OK, just as it was in the case of the trees.
P.S.
-------
In case anyone wants to know, I'm asking this in the context of some
RBAC (role-based access control) code I'm designing. The design is not
finished, but the role hierarchy may allow a node to have multiple
parents and it may also allow inheritance of permissions (rights) to be
directed either upward or downward, as proposed here:

Crampton, J. 2003. On permissions, inheritance and role hierarchies. In
Proceedings of the 10th ACM Conference on Computer and Communications
Security (Washington D.C., USA, October 27 - 30, 2003). CCS '03. ACM
Press, New York, NY, 85-92. DOI=
http://doi.acm.org/10.1145/948109.948123

If I end up using something remotely similar to that, I first want to
determine whether I could make it as performant as the solution using
rooted trees (i.e., no roles with multiple parents and all inheritance
of permissions in the upward direction).

[Gene]

Mountain wrote:

Background:
In trees, there are a two or three ways (maybe more) to find out if
Node A is an ancestor of Node B without traversing the tree.

Preprossing is OK, and one of the solutions I am aware of is here:

"Use [depth first search] pre- and post-order numbers. Na is an
ancestor of Nb iff
pre(Na) < pre(Nb) and post(Na) > post(Nb)."
See
http://groups.google.com/group/comp....coring=d&hl=en

My question:
-------------------
What if, instead of a tree, we have a DAG (i.e., a directed graph with
no directed cycles)? Is it possible to find out if Node A is
predecessor of Node B (in the topological order) without searching or
traversing the graph? Assuming it might be possible, what specific
methods could we use to find out about the predecessorship in this way?
Preprocessing is OK, just as it was in the case of the trees.

In a preprocessing pass, compute the transitive closure of the DAG.
There are several well-known efficient algorrithms for this. Perhaps
the best-known is Warshall's Algorithm.

[Chris Uppal]

Mountain wrote:

What if, instead of a tree, we have a DAG (i.e., a directed graph with
no directed cycles)? Is it possible to find out if Node A is
predecessor of Node B (in the topological order) without searching or
traversing the graph? Assuming it might be possible, what specific
methods could we use to find out about the predecessorship in this
way? Preprocessing is OK, just as it was in the case of the trees.

This sounds like the same problem as sub-type checking in the presence
of multiple inheritance (as in Java interfaces). I recommend (again)
that you to Google for:

fast subtype checking

Ware patents!

-- chris

[Mountain]

Chris Uppal wrote:

This sounds like the same problem as sub-type checking in the presence
of multiple inheritance (as in Java interfaces). I recommend (again)
that you to Google for:

fast subtype checking

I should have done that the first time. That proved very fruitful.
Thanks.

[Mountain]

Mountain wrote:

My question:
-------------------
What if, instead of a tree, we have a DAG (i.e., a directed graph with
no directed cycles)? Is it possible to find out if Node A is
predecessor of Node B (in the topological order) without searching or
traversing the graph? Assuming it might be possible, what specific
methods could we use to find out about the predecessorship in this way?
Preprocessing is OK, just as it was in the case of the trees.

I think I'm on the right track, and I appreciate the help from the
group! However, work deadlines are such that a few more quick answers
would be really, really helpful.

Given an hierarchy such as in multiple subtyping (or a DAG as I
proposed above), I see that there are several ways to perform efficient
tests for subtypes (type inclusion tests /predecessor tests).

Are there variations on this that will find the least common ancestor
of two types in constant time using techniques like the binary matrix
encoding? (I actually don't care which techiques are used, but I am
primarily after runtime efficiency.)