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

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