BGL: Immutable vertex/edge descriptors?

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-06-19 11:33:42

If I use vecS for EdgeList and/or VertexList, whenever I remove a
edge/vertex this also affects any vertex/edge with a higher numbered
descriptor, i.e. removing vertex 0 results in subtracting 1 from every
other vertex descriptor.

I'm making a graphical editor for a structure that is represented as a
graph, and to quickly determine which vertex/edge is selected and should
be edited in any way I figure the best way is to keep a copy of the
edge/vertex descriptor with the graphical object that is supposed to
represent just that edge/vertex. If I use vecS this soon becomes a real
pain if I have to update edge/vertex descriptors everywhere whenever I
remove some part of the graph. I could of course add my own immutable
descriptors as properties in the graph, but that just reverses the
problem - I'll have to map these back to the 'real' descriptors when I
want to modify/access the graph.

I assume I can use listS to store both edges and vertices to solve this
problem in that the descriptors become pointers which are not disturbed
when I remove a vertex/edge? What about setS?

If I go with listS I end up with another concern regarding the
performance benchmarks on traversal in the BGL book. Is the code used to
create those benchmarks available anywhere so that I can do a
re-evaluation with later compiler versions?

I hope someone can shed some light here.

Thanks,
--
Tarjei