What's the difference between vertex descriptor and index in Boost Graph Library?

Question

In Boost graph library, when should one use vertex descriptor and when index? Since the implementation of vertex_descriptor is actually unsigned integer, do the two things have the same value?

Answer 1

The vertex_descriptor is only an index when you are using a vector (or similar) as the underlying data structure for your vertices (i.e. boost::vecS). If you use a different underlying data structure, then the vertex descriptors will not necessarily be an index. An example of this would be if you use an std::list/boost::listS - lists do not use an index-based accessing method. Instead, each vertex_descriptor will instead be a pointer to the list item.

Thus, every time you want to refer to a vertex in your graph, you should use vertex_descriptor. That way if you later decide to use a different data structure, you won't have to change your code.

For more information about the different EdgeList and VertexList data types and the pros/cons of each, see the Using Adjacency List page.