Re: [boost] BGL limitations (?) and possible solutions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-14 13:15:55

----- Original Message -----
From: "Jeremy Siek" <jsiek_at_[hidden]>

> I'm certainly willing to look at new approaches to writing generic graph
> searches. Some of the "obvious optimizations" you mentioned were not
> obvious to me, and therefore were not considered in the initial design.

Sorry, I didn't mean to sound condescending.

> david.> for example, the requirement that you can get the source
> david.> vertex for any edge is an unneccessary imposition which
> david.> imposes the cost of an extra vertex descriptor in each
> david.> edge.
>
> This is not as bad a requirement as you think. You don't have to store the
> source vertex to provide access to it. You can carry along the source
> vertex inside the iterator. That's the way I do it in adjacency_list. See
> the out_edge_iter_policies class in detail/adjacency_list.hpp.

Yes, I actually did that, but it's expensive unless you're using KCC. And
it's complicated. And the extra levels of template instantiation when I
introduce an iterator_adaptor for this purpose stress my compilers (compiler
stress is proving to be a major obstacle here - compiling with gcc is slow
and compiling with MSVC doesn't work at the moment). The point is that
hardly any algorithms need the source vertex, so there should be a separate
concept for graphs that can report it.

-Dave