should I keep track of vertex descriptors in boost graph library?

Question

I have a graph instantiated with the following:

typedef boost::property<boost::edge_weight_t, uint32_t> EdgeWeightProperty;
typedef boost::property<boost::vertex_index_t, uint32_t> VertexProperty;
typedef boost::adjacency_list<boost::vecS, boost::setS,
                              boost::undirectedS, VertexProperty,
                              EdgeWeightProperty, boost::setS> Graph;

I need to update this graph, e.g. add or remove edges. Since I'm using a set to store the vertices, I can't use their index, but I can keep a map:

unordered_map<uint32_t, Vertex_Descriptor>

That maps my indexes to vertices descriptors, so I can then later access directly in BGL, this approach works but adds this map overhead.

Can I somehow specify a custom index or what to compare when getting/putting vertices in the BGL? Or keeping vertices descriptors in a map is the best approach?

Full example at coliru

Answer 1

Short answer: yes.

Notes:

1. Consider the rather underdocumented labeled_graph<> adaptor. I believe it's used in the library samples and also I have a number of answers using it on this site (Disclaimer: I also found a number of bugs in it, so YMMV)

2. Your own global add_vertex helper isn't being used, even if you did write:

   const auto vd = add_vertex(i, g);
   

   Beware of ADL! You named the function add_vertex and unless you wrote (add_vertex)(i, g) ADL would find the overload in boost because adjacency_list<> is from that namespace (among other related types).

   So, you can drop your helper function and still write it like that using the boost add_vertex overload taking a property: MutablePropertyGraph concept, under "Valid Expressions":

   for (int i = 0; i < 10; ++i)
        id_vertex[i] = add_vertex(i, g);
   

3. Also replacing the loop to print the graph you can use print_graph

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

typedef boost::property<boost::vertex_index_t, uint32_t> VertexProperty;
typedef boost::property<boost::edge_weight_t, uint32_t> EdgeWeightProperty;
typedef boost::adjacency_list<boost::vecS, boost::setS, boost::undirectedS, VertexProperty, EdgeWeightProperty,
                              boost::setS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::vertex_iterator vertex_it;

int main() {
    Graph g;
    std::unordered_map<uint32_t, Vertex> id_vertex;

    for (int i = 0; i < 10; ++i)
        id_vertex[i] = add_vertex(i, g);

    std::pair<vertex_it, vertex_it> vp;
    for (int i = 0; i < 9; ++i)
        add_edge(id_vertex[i], id_vertex[i + 1], g);

    clear_vertex(id_vertex[2], g);
    remove_vertex(id_vertex[2], g);

    print_graph(g);
}

Prints

0 <--> 1 
1 <--> 0 
3 <--> 4 
4 <--> 3 5 
5 <--> 4 6 
6 <--> 5 7 
7 <--> 6 8 
8 <--> 7 9 
9 <--> 8