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?
Greets,
Asger Alstrup