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

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: http://www.boost.org  Send unsubscribe requests to: <mailto:boost-unsubscribe_at_[hidden]> 
> 
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
-- 
Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    [phone]
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage: http://www.osl.iu.edu/~llee