It strikes to me now that the matter is not so subtle at all, since add_vertex() with vecS is very likely to invalidate vertex_iterators (clearly contrary to the documentation). In my case the issue was a bit obscured since it is not perfectly clear that source(edge_descriptor) and target(edge_descriptor) use vertex_iterators. I had expected that edge_descriptor stores two vertex_descriptors. The problem is not with edge_descriptor it is in the operator++() of the edge_iterator class.
I think that edge_iterators are not directly affected, and its still save to use them to access, e.g., edge properties. Its also save to use operator++(). The problem is that calling source(...) on an edge descriptor dereferences a vertex_iterator, and THAT one may have been invalidated. Is that right?
Well, you can try to remove source() and target() calls from your example and to see if the problem is still reproducible.
The problem is with the documentation - not the code. The edge_iterator IS invalidated after add_vertex() because the edge_iterator retains a pair ouf out_edge_iterators that refer to the current out edge being visited of the current vertex. The add_vertex() call may not invalidate vertex descriptors but it will invalidate out_edge_iterators since the memory they pointed to no longer exsts (i.e., copied and deleted). The cascading effect is that it will also invalidate the edge_iterator. Hence, the failure of g[*i]. Andrew Sutton andrew.n.sutton@gmail.com