
Boost : 
From: Andrew Sutton (asutton_at_[hidden])
Date: 20070615 12:30:28
All Interested,
For my Summer of Code proposal, I have been working on the usability
of the Boost.Graph library, basically adding a couple wrappers to
make it easier to work with undirected and directed graphs. One
aspect of these classes is that they do not use the typical vector
storage for vertices, edges, or the out edge list. In this case, list
storage provides more iterator and descriptor stability so we (mentor
Jeremy Siek and myself) decided go that direction.
This decision has some interesting fallout since almost every example
for Boost.Graph, including that in the documentation is written using
vecS for most of the storage facilities. This lead some interesting
discoveries like, for example, that num_vertices(g) is O(n) with
listS vertex storage under GCC  who knew?. also that most graphs
declared using `listS` will fail to run correctly with default
parameters on just about every algorithm. And finally, that most of
the examples given in the documentation and libs directory will also
fail if you stick this line of code just before a call to any core
algorithm:
remove_vertex(*vertices(g).first, g);
Except for the linear time num_vertices(g) call, these problems are
caused by indiscriminate use of vertex descriptors as indices  in
fact, that's exactly the reason that the above line of code will
cause most examples to fail.
I've written down a solution to this and added it to the
documentation I've been working for my project. It essentially
involves three functions that can be used to help manage vertex
indices. Essentially they are:
get_vertex_index(v, g)
max_vertex_index(g)
renumber_vertex_indidces(g)
Correct use of these functions will solve a number of problems. The
more complete proposal is in subversion at:
http://svn.boost.org/trac/boost/browser/sandbox/SOC/2007/graphs/libs/
graph/doc/quickbook/indexing.qbk
Part the related implementation is here:
http://svn.boost.org/trac/boost/browser/sandbox/SOC/2007/graphs/boost/
graph/undirected_graph.hpp
The three functions in question are the last in the file, although
they do call some member functions of the graph class itself.
I'd be grateful to some suggestions for improvement or other comments.
Andrew Sutton
asutton_at_[hidden]
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk