Boost logo

Boost :

From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-01-14 14:41:39

> For directed graphs, you may deduce your problem to find a
> transitive_closure of your graph.

Yes, transitive_closure would solve my problem.

However, transitive_closure does not work with Visual Studio 6:

../boost\boost/graph/vector_as_graph.hpp(59) : fatal error C1189: #error :
The vector-as-graph module requires a compiler that supports partial
Error executing cl6.exe.
Does anybody have a version of transitive_closure that works for VC6?
> Do you have any algorithms which is
> faster than transitive_closure?
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
The best algorithms I know for the general, static problem is the one
mentioned in the first paper on:
I don't know how this relates to the one in Boost. It might have a smaller
constant-factor, but I don't know.
For the dynamic problem, the best algorithms, I know are contained in the
PhD-thesis on:
Asger Alstrup

Boost list run by bdawes at, gregod at, cpdaniel at, john at