From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-01-12 10:32:46
> Consider this graph, where U is the source and W the sink:
> / \
> V X
> | |
> | Y
> \ /
One corresponding depth-first-tree looks like this:
and in this, X is not an ancestor to W.
Another corresponding depth-first-tree looks like this:
and in this, X is an ancestor to W.
So, you are correct that the Parenthesis Theorem says that vertex U is an
ancestor to V *in the depth first tree* iff the discovery-finish interval of U
is contained in the interval of V.
However, since the depth first tree is not uniquely defined in a DAG or
general graph, this theorem can not be used to determine if a vertex is an
ancestor to another -- except in a tree or a forest.
Instead, I suppose I could use a nearest-common-ancestor algorithm. Does this
algorithm exist in BGL? I could not immediately find it.
Alternatively, maybe I can use Dijkstra shortest-path, and formulate the
problem as a path finding problem?
In the case of a DAG, I suppose a breadth-first-search would suffice, since
the problem could be formulated as finding the shortest path from vertex U to
V, with unit cost on all edges...
I think finding ancestor and descendant is a common problem. Maybe it would be
useful to have them in the graph library as a separate algorithm or in an
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk