Re: [boost] BGL: How do I find ancestors to a node?

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:
>
>    U
>   / \
>  V   X
>  |   |
>  |   Y
>   \ /
>    W

One corresponding depth-first-tree looks like this:

  U
 / \
V   X
|   |
W   Y

and in this, X is not an ancestor to W.

Another corresponding depth-first-tree 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 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
example?

Greets,

Asger Alstrup