CODEWITHSUNDEEP
c++boostboost-graphadjacency-list
lucidbrot
lucidbrot

Reputation: 6156

Why does a boost adjacency_list using vecS as OutEdgeList template parameter invalidate edges on traversal?

I'm reading the documentation about adjacency_list and the impact choosing the graph type has on memory consumption, big-O runtime, and descriptor stability.

Quoting the first link:

The following table summarizes which operations cause descriptors and iterators to become invalid. In the table, EL is an abbreviation for OutEdgeList and VL means VertexList. The Adj Iter category includes the out_edge_iterator, in_edge_iterator, and adjacency_iterator types.
A more detailed description of descriptor and iterator invalidation is given in the documentation for each operation.
Table: Summary of Descriptor and Iterator Invalidation

I understand that if one uses vecS for the VertexList that on remove_vertex() all vertex descriptors will be adjusted so that they are still continuous.

I do not understand why, apparently, using vecS causes the edge iteration to invalidate edge descriptors.

Do I understand the table correctly in that it is saying "If you use vecS for the Edge List type on an adjacency_list graph that is directedS then you can not stably iterate over the edges because iterating over them will invalidate the edge iterators and edge descriptors"?

If I do understand this correctly, please explain why this is the case. If I misunderstand, please clarify the actual effect using vecS for the Edge List has.
Thank you.

Upvotes: 1

Views: 148

Answers (1)

sehe
sehe

Reputation: 392911

You’re misreading it, as you suspected.

The confusion is that the columns “Edge Iter”, “Vertex Iter” and “Adj Iter” are abbreviating for “Iterator”, not “iteration”.

The mere act of iteration never changes the adjacency_list, so cannot invalidate descriptors nor iterators.

There are graph models where the descriptors are more stable than the iterators (the iterators. That’s actually the key reason for the descriptor concepts. Any container selector with reference stability (i.e. node-based containers) will naturally have iterator stability (only invalidating iterators to erased nodes).

The table is useful because for performance on “immutable” (or change rarely, query-often) graphs can be greatly enhanced by choosing contiguous storage (like vecS) and they will naturally impose more restricting invalidation rules (e.g. vectors may reallocate, which invalidates all iterators, but the descriptor might remain stable up to the index of modification/insertion).

Tip

To get a raw compile-time check on basic invalidation issues, consider taking your graph by const reference. That will eliminate the off-chance of unintended modifications. Of course, in some cases you really want to walk the edge (for performance) where you want to performa modifications to the graph and you’ll have to per-use the documentation to see exactly what invalidation rules apply to that modification.

Upvotes: 1

Related Questions