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

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-14 15:25:55

> For my immediate problem, where I only need the ancestor and descendant-sets
> for one given vertex, a faster algorithm is obviously possible, since I don't
> need the full transitive_closure. I would think O(V+E) is possible in this
> case.

Then, you can use depth-first visit starting from that given vertex, all
visited vertices are the descendants of that vertex. To find ancestors
of that vertex, use depth-first visit starting from that vertex  in the
reverse graph (there is a reverse graph adaptor is the BGL), right?
 

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