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

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-12 12:20:34

On Sat, 2002-01-12 at 10:32, Asger Alstrup Nielsen wrote:
> 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?
> 

For undirected graphs as in your example, I am not sure how you define
ancestor/descendant. 

For directed graphs, you may deduce your problem to find a
transitive_closure of your graph. (For transitive closure, the
constructed graph G'=(V,E') has the edge (i,j) \in E' iff there is a
directed path from i to j in G.) Do you have any algorithms which is
faster than transitive_closure? 

-- 
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