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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk