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

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:

--
ZOrderAlgorithms.cpp
../boost\boost/graph/vector_as_graph.hpp(59) : fatal error C1189: #error :
The vector-as-graph module requires a compiler that supports partial
specialization
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
case.
The best algorithms I know for the general, static problem is the one
mentioned in the first paper on:
http://www.cs.hut.fi/~enu/tc.html
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:
http://www.dis.uniroma1.it/~demetres/
Greets,
Asger Alstrup