Boost Graph identifying vertices

Question

I need to map vertices in a Boost Graph to an unsigned integer. I learned from related posts on this site (1, 2) that the proper way to do this is to create a custom vertex class.

struct Vertex { uint32_t index; };
typedef boost::adjacency_list<boost::vecS, boost::vecS,
    boost::directedS, Vertex> BoostGraphType;    

typedef BoostGraphType::vertex_descriptor vertex_desc;

// now i can use
BoostGraphType g; 

vertex_desc vd = boost::add_vertex(g);
g[vd].index = magic;

However, according to the documentation (Iterator and Descriptor Stability/Invalidation), the vertex descriptors can become invalid, which means that I should not store them to map the vertices.

Since I have my custom vertex class + .index, this should not be a problem.

But: How do I retrieve the vertex_descriptor for a specific index at a later time? And how can I do that without linear search?

Or is there a better way to keep a persistent id for each vertex than such a custom vertex class?

Answer 1

When your graph is adjacency_list<boost::vecS, boost::vecS, ... then vertex descriptors are integers. Some vertex descriptors can become invalid when you remove a vertex; similarly, some edge descriptors become invalid when you remove an edge. If you never remove graph elements then these integer descriptors remain valid.

As BGL documentation states it, "if you want your vertex and edge descriptors to be stable (never invalidated) then use listS or setS for the VertexList and OutEdgeList template parameters of adjacency_list.".

Beware that if you use adjacency_list<boost::listS,... you would likely need to make extra efforts to generate and update a property named vertex_index. Many algorithms will not work without it. See more details here https://stackoverflow.com/a/19758844/2876861