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

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. 
Jeremy?

> > > 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.

- Volodya