the documentation of adjacency_list states, that a call to add_vertex() does not invalidate any iterators nor descriptors. However, following code segfaults, because retrieving vertex descriptors from an edge_iterator via source() and target() does not work (example should compile as is):

#include <iostream>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

typedef adjacency_list<listS, vecS, directedS > Graph;

int main() {
Graph g(3);

add_edge( 0, 1, g );
add_edge( 1, 2, g );
add_edge( 2, 0, g );

Graph::edge_iterator ei, ei_end;

for( tie( ei, ei_end ) = edges( g ); ei != ei_end; ++ei )
{
std::cout << source( *ei, g ) << " " << target( *ei, g ) << "\n";
add_vertex( g ); // <- in my real application, vertex gets some
// properties that depend on source(...) and
// target(...) above
}
}

Is it the case that an edge_iterator does not store vertex_descriptors (that should survive reallocation of the vertex storage), but iterators to the vertex storage?

What is the proper way to accomplish something like this? My present workaround is to postpone all add_vertex() calls after the loop, but this costs some storage, and with my graph scaling bigger and bigger, that begins to hurt.

Any help and explanation is really appreciated!

This is a nice, subtle problem that you've found :) Remember that an adjacency list stores a list of incident edges for each vertex. Adding a vertex (with VertexSet == vecS) can cause a reallocation of the underlying buffer, causing all of those incident edge lists to be reallocated and copied. The edge iterator stores actually stores a pair of iterators into the out-edge list of some vertex... The unfortunate side-effect seems to be that adding a vertex *can* in fact invalidate an edge iterator. I guess the documentation is wrong.

Note that this probably won't be the case with VertexSet != vecS since additions don't cause re-allocations.

I don't see any possible way to work around this other than deferring all of your vertex additions til after the loop.