Boost logo

Boost :

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:

 / \
| |

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


Asger Alstrup

Boost list run by bdawes at, gregod at, cpdaniel at, john at