From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-01-15 10:01:53
> > 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?
> > 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.
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.) So
for each vertex, I transverse the graph 3 times, and touch the vertices
at least 6 times.
I collect the ancestors and descendents in a set, so this gives an
O(E*V*log V) algorithm, with a pretty high constant factor.
It would be nice to remove this kludge with the much more elegant and
faster transitive_closure, but other than that, I don't really need more
speed at the moment.
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...
Is there support for dynamic algorithms in BGL at all?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk