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).
