In the Boost Graph Library, why does adding an edge invalidate Edge iterators (and other questions)?

Question

A few questions about the chart in the BGL documentation labeled "Summary of Descriptor and Iterator Invalidation":

1. Why does adding an edge invalidate the edge and adjacency iterators; why isn't every column of the add_edge() row "OK"? Wouldn't the in/out edge lists simply be appended?
2. Why does removing an edge only invalidate an edge iterator if the graph is directed; why is the second to last column in the second row not simply "EL=vecS"? In the undirected graph case wouldn't removing an edge remove it from two edge lists (one for the source and one for the target vertex) which would invalidate iterators in both those lists?

Thanks!

Answer 1

All of these effects follow from the usual Iterator invalidation rules

1. Why does adding an edge invalidate the edge and adjacency iterators; why isn't every column of the add_edge() row "OK"? Wouldn't the in/out edge lists simply be appended?

Yes they would be appended. And, seeing that they might reallocate doing so, they invalidate iterators.

2. Why does removing an edge only invalidate an edge iterator if the graph is directed

The notation in the matrix is more than a little confusing.

Docs: "This operation causes any outstanding edge descriptors or iterators that point to edge (u,v) to become invalid. In addition, if the OutEdgeList selector is vecS then this operation will invalidate any iterators that point into the edge-list for vertex u and also for vertex v in the undirected and bidirectional case. Also, for directed graphs this invalidates any edge_iterator."

So you misread: it doesn't only invalidate "if the graph is directed". It also invalidates any iterators that point into the edge-list for the target vertex (v) in the undirected and bidirectional case. This makes sense if you realize how the back-edged are stored.