From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-01-15 10:13:29
Asger Alstrup Nielsen wrote:
> > > Does anybody have a version of transitive_closure that
> > > works for VC6?
> > I don't think this problem is related to transitive_closure
> > at all -- it's related to vector_as_graph, which is used in
> > the test but not in the algorithm.
> So, maybe the test should be moved out of transitive_closure.h?
I see what the problem is! transitive_closure.hpp includes
vector_as_graph.hpp without any reasons. It should work is the include is
commented out. To fix it permanentely, transitive_closure.w need to be fixed.
> > > 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
> > The algorithm described there is more elaborated than the one
> > in boost, and should be faster. Is there much interest in
> > replacing the current transitive_closure? (And, actually, I'm
> > not sure I have much time for that :-) ).
> I am interested, although for now I would be happy with the current
> version working on VC6.
Please try it without the wayward #include.
> At the moment, I solved my problem with two uses of depth_first_visit
> and one use of transpose_graph, and one linear search for the vertex in
> the reversed graph. (I could not get reverse_graph to work on VC6.)
It's really sad that compilers restrict BGL usage.
> From a different perspective, I think BGL does have the potential to
> compete with LEDA. Especially if the best algorithms were implemented,
> so from this perspective it would certainly be a great thing to have. In
> fact, the fastest dynamic transitive_closure would be the best, but...
Sure, nobody have time ;-)
> Is there support for dynamic algorithms in BGL at all?
All I know is "dynamic_components' somewhere in the docs.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk