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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-01-14 13:10:31

On Mon, 14 Jan 2002, David Abrahams wrote:
david.>
david.> Rich points out that I will still deal with everything left in the queue.
david.> It's easy enough to clear the queue on finish_vertex (except that the stupid
david.> queue interface doesn't include clear()).
david.>
david.> At this point I've lost track of exactly what I was doing
david.> when I wrote this, so please don't waste any of your time
david.> trying to solve these problems for me. My only point was
david.> that there are a number of obvious optimizations and
david.> simplifications which are available to hand-written graph
david.> algorithms, which I can't take advantage of with BGL. Just

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.

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.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------