
Boost : 
From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 20020112 10:32:46
> Consider this graph, where U is the source and W the sink:
>
> U
> / \
> V X
>  
>  Y
> \ /
> W
One corresponding depthfirsttree looks like this:
U
/ \
V X
 
W Y
and in this, X is not an ancestor to W.
Another corresponding depthfirsttree looks like this:
U
/ \
V X

Y

W
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 discoveryfinish 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 nearestcommonancestor algorithm. Does this
algorithm exist in BGL? I could not immediately find it.
Alternatively, maybe I can use Dijkstra shortestpath, and formulate the
problem as a path finding problem?
In the case of a DAG, I suppose a breadthfirstsearch 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
example?
Greets,
Asger Alstrup
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk