
Boost : 
From: LieQuan Lee (llee_at_[hidden])
Date: 20020112 12:20:34
On Sat, 20020112 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?
 LieQuan Lee (AKA: Rich Lee) Research Associate Open Systems Laboratory Phone: 18128553608 Computer Science Department Email: llee_at_[hidden] Indiana University Homepage: http://www.osl.iu.edu/~llee
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk