Boost logo

Boost :

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-11 12:06:31

If the graph is a rooted tree, Start depth-first visit from the root
with discover time, finish time and parent recorded. After that, you can
get vertex u's parent and ask for its parent's parent ... to get a full
set of ancestors. To answer the second quesiton (is vertex A
an ancestor to vertex B), check the condition
 discover_time(A) <= discover_time(B) and
 finish_time(A) >= finish_time(B)

On the other hand, if you are talking about a general directed graph,
maybe a transitive closure-like algorithm is what you want?

On Fri, 2002-01-11 at 10:32, Asger Alstrup Nielsen wrote:
> Hi,
> What is the best way to get the full set of ancestors to a vertex in a
> directed graph?
> Alternatively, how can I answer the question:
> Is vertex A an ancestor to vertex B?
> Thanks,
> Asger Alstrup
> Info: Send unsubscribe requests to: <mailto:boost-unsubscribe_at_[hidden]>
> Your use of Yahoo! Groups is subject to

Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    1-812-855-3608
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage:

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