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

score 2 · Accepted Answer · answered Dec 20 '17 at 11:40

Short answer: yes.

Notes:

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)
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);
```
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

Thanks for the quick answer! The helper function was a residue from other code. Is sad that I must pretty much double the space of the program for it to work properly. One would expect a way to overload the vertices ids :( — Fynn, Dec 20 '17 at 12:24
Ideas: You don't have to keep the external index around at all times. You can also use a vector for more effective allocation. See also these answers touching on using intrusive containers: https://stackoverflow.com/questions/32296206/bgl-indexing-a-vertex-by-keys and https://stackoverflow.com/questions/45845469/make-a-boost-filtered-graph-by-vertex-label-property/45850742#45850742 — sehe, Dec 20 '17 at 15:49

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

1 Answers1