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@cs.kent.edu