[boost] [graph] managed vertex indexing

From: Andrew Sutton (asutton_at_[hidden])
Date: 2007-06-15 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]