Performance vertex_descriptor of the Boost Graph Library

Question

I have a doubt concerning the vertex_descriptor used to access on a vertex in a graph. In a previous implementation of my own, I used pointers on vertices like a way to access directly on a vertex. I could implement a map if I want access an IDVertex by an integer or something else.

But in BGL, I don't understand why a vertex_descriptor is an integer ? I know it makes sens with a vector. But if I want to use a wide set of vertices like 10^6 and be able to remove any vertex of the set, I use a map. Plus, in my game, I want to be able to refering each node by the pointer integer which is more logical ?

How BGL works to link an integer with a vertex in a no_random_access_container like std::set ? The access method is always log(n) no ? Can you explain me if there is a mecanism to keep handle directly on a vertex without keeping a vertex_descirptor ?

Sorry for my bad english ;)

Answer 1

When vertex container policy is defined as vecS, setS or listS, the vertex_descriptor becomes ["value_type" pointed to by] iterator in corresponding container. The type vertex_iterator is usually an iterator type in this container.

It means access to a vertex is always O(1). Adding and removing a new vertex will cost O(logN) in case of setS and O(1) in case of listS or vecS. Removing a vertex will invalidate some other vertices in case of vecS but not listS or setS. For details see the section Iterator and Descriptor Stability/Invalidation at the adjacency graph page.

Regarding your other question. If you want to keep a (pointer) to a data directly on a vertex, you add it as a vertex property.

Quite often you need some kind of one-to-one mapping between your data and graph vertices. It can be convenient to keep direct map as, say, boost::unordered_set and inverse map as a property on each vertex.