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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk