Boost logo

Boost :

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