How to configure boost::graph to use my own (stable) index for vertices?

Question

The simplest boost::adjacency_list uses std::size_t as the underlying vertex_descriptor (index).

boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    boost::no_property,
    boost::no_property
>  graph;

Once I know the vertex descriptor, I can quickly access the desired vertex.

auto vertex = graph[idx]; // idx is the veretx descriptor

However, when the graph is mutated, there is no guarantee that the vertex_decriptor will be stable.

auto v0 = boost::add_vertex(graph);
auto v1 = boost::add_vertex(graph);
auto v2 = boost::add_vertex(graph);

boost::remove_vertex(v0, graph); // v1 and v2 are no longer valid

I would like to be able to find a specific vertex quickly - meaning I wish to avoid traversing the graph structure in search of a vertex I know exists.

My thinking is that I can somehow tweak boost::adjacency_list with a different selector to the VertexListS template parameter, that will allow me to use my own provided vertex_descripor (index).

I explored the possibility of using an associative container selector such as the builtin boost::hash_mapS but it seems I can't control the exact id it returns when calling add_vertex. I would like to be able to use my own id (vertex_descriptor) for each vertex.

I'll try to be a bit more clear, with the code I wish would work:

// the following type will serve as the vertex_descriptor:
using my_id_type = std::size_t;

struct MyVertex
{
    my_id_type id;
    // some other fields
}

// add vertices with unique identifiers that will also serve as the vertex_descriptors
boost::add_vertex(MyVertex{1111}, graph); // I expect this to return 1111
boost::add_vertex(MyVertex{2222}, graph);
boost::add_vertex(MyVertex{1234}, graph);


boost::remove_vertex(1111, graph); // I expect this to remove the first vertex

// access a specific vertex using its unique, stable descriptor:
auto vertex = graph[1234];

Can this be achieved using boost::graph?

Answer 1

Can this be achieved using boost::graph?

The answer is nearly always "yes" with BGL. It's one of the most profoundly generic library designs in existence.

---

To my surprise, something new appeared in the type-hierarchy for adjacency_list. Apparently these days there's a named_graph mixin (actually maybe_name_graph) which uses traits on the vertex bundle to detect an "internal name".

This means you can get close. Though the vertex descriptor will not become your id, you can have O(1) lookup. And the interface has some conveniences, so you can write:

add_edge(1111, 2222, g);
add_edge(2222, 1111, g);

Notes:

• the lookup is amortized O(1) because the name-vertex lookup is based on an unordered (hash) index
• you run into problems (e.g. ambiguous overloads for add_edge) if you make the id type accidentally the same as the vertex_descriptor type (or if your argument have equally "far" conversions to either).
• as far as I can tell, the internal name property is not automatically picked up as the vertex_index_t nor vertex_name_t property.

Step #1: The Graph

struct Vertex {
    size_t      id;
    std::string other = "default-constructed";
};

using Graph =
    boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;

So far no surprises. I

• opted to add a second member other just to show when/how it gets default constructed
• opted listS because it
  • a. offers reference/descriptor stability (except for removed vertices)
  • b. leads to opaque vertex_descriptor (void*) which does not conflict with the id type (size_t) in overload resolution

Step #2: Name Traits

Next we teach BGL about our Internal Vertex Name.

This is purely parameterized by Vertex bundle, so keep in mind that different graphs using the same bundle would use the same name traits.

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = size_t;
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
      private:
        using extract_name_type = typename internal_vertex_name<Vertex>::type;

        using vertex_name_type = typename remove_cv<typename remove_reference<
            typename extract_name_type::result_type>::type>::type;

      public:
        using argument_type = vertex_name_type;
        using result_type = Vertex;

        result_type operator()(const vertex_name_type& id) const {
            return {id};
        }
    };
};

Note

• We could of course hard-code the knowns in the second specialization:

   template <> struct boost::graph::internal_vertex_constructor<Vertex> {
       struct type {
           Vertex operator()(size_t id) const { return {id}; }
       };
   };
  

• It is very important to return the id by reference. Failing to do so leads to UB with no diagnostics from the library/compiler

Step #3 Adding/Finding Vertices

Now you can add vertices. Either by "name" (your id):

auto x = add_vertex(1111, g);                // by id

Or the old-fashioned way you anticipated in the question:

add_vertex(Vertex{2222, "twotwotwotwo"}, g); // or with full bundle

Duplicate additions have no effect:

assert(add_vertex(1111, g) == x);

Different lookups exist. The vertex_by_property returns a optional<vertex_descriptor> given a vertex bundle.

assert(x == *g.vertex_by_property(g[x]));

It does so by extracting the "internal name" from the bundle passed, so there is no need for the bundle to contain any other state outside the id:

assert(x == *g.vertex_by_property(Vertex{1111}));

Although it feels like an implementation detail, the actual multi_index_container implementing the name -> descriptor index is also exposed:

assert(x == *g.named_vertices.find(1111));

Step #4 Adding Edges

add_edge(1111, 2222, g);
add_edge(2222, 1111, g);

That borrows a page from your previous question :)

Obviously, you can still add edges by vertex descriptors.

Step #5 Other Operations

Borrowing more pages from that previous answer:

print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

std::cout << "---\n";
for (auto *v : boost::make_iterator_range(vertices(g))) {
    auto const& [id, other] = g[v];
    std::cout << id << " " << std::quoted(other) << "\n";
}

if (auto v = g.vertex_by_property({1111})) {
    std::cout << "==== removing " << g[*v].id << "\n";
    clear_vertex(*v, g);  // clear edges
    remove_vertex(*v, g); // remove the vertex
}

print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

Full Demo

Live On Coliru

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

struct Vertex {
    size_t      id;
    std::string other = "default-constructed";
};

using Graph =
    boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = size_t;
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
      private:
        using extractor = typename internal_vertex_name<Vertex>::type;
        using name_t    = std::decay_t<typename extractor::result_type>;

      public:
        using argument_type = name_t;
        using result_type = Vertex;

        result_type operator()(const name_t& id) const { return {id}; }
    };
};

int main() {
    Graph g;

    {
        auto x = add_vertex(1111, g);                // by id
        add_vertex(Vertex{2222, "twotwotwotwo"}, g); // or with full bundle

        // duplicate additions have no effect
        assert(add_vertex(1111, g) == x);

        // different lookups exist
        assert(x == *g.named_vertices.find(1111));
        assert(x == *g.vertex_by_property(Vertex{1111}));
        assert(x == *g.vertex_by_property(g[x]));
    }

    add_edge(1111, 2222, g);
    add_edge(2222, 1111, g);

    print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
    print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

    std::cout << "---\n";
    for (auto *v : boost::make_iterator_range(vertices(g))) {
        auto const& [id, other] = g[v];
        std::cout << id << " " << std::quoted(other) << "\n";
    }

    if (auto v = g.vertex_by_property({1111})) {
        std::cout << "==== removing " << g[*v].id << "\n";
        clear_vertex(*v, g);  // clear edges
        remove_vertex(*v, g); // remove the vertex
    }

    print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
    print_graph(g, get(&Vertex::other, g), std::cout << "---\n");
}

Prints

---
1111 --> 2222 
2222 --> 1111 
---
default-constructed --> twotwotwotwo 
twotwotwotwo --> default-constructed 
---
1111 "default-constructed"
2222 "twotwotwotwo"
==== removing 1111
---
2222 --> 
---
twotwotwotwo --> 

Sidenote:

• you cannot use an associative container selector for vertices. Specifying hash_mapS leads to unordered_set<void*, hash<void*>, equal_to<void*>, allocator<void*>> as the m_vertices type.