Boost graph custom indexes use Dijkstra

Question

I am trying to create a graph via Boost graph library, that has custom indexing (stable ones when vertexes are deleted),

I copied the sollution proposed here to create the graph which is working very well for me How to configure boost::graph to use my own (stable) index for vertices?

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


using namespace boost;

struct Vertex {
    int id;
};

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

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = int;
        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}; }
    };
};
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;


Graph g;

add_vertex(1, g);
add_vertex(2, g);
add_vertex(5, g);
add_vertex(6, g);
add_vertex(7, g);
add_edge(1, 5, 1, g);
add_edge(2, 6, 1, g);
add_edge(2, 7, 2, g);
add_edge(5, 2, 7, g);
add_edge(5, 6, 3, g);
add_edge(6, 7, 1, g);
add_edge(7, 1, 1, g);
add_edge(7, 2, 1, g);


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

But then the fun started when I tried to use Dijkstra on this graph. On a normal graph, I would use Dijkstra this way

std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));
vertex_descriptor source_idx = vertex(1, g);
dijkstra_shortest_paths(g, source_idx,
                        predecessor_map(boost::make_iterator_property_map(
                                            p.begin(), get(vertex_index, g)))
                            .distance_map(boost::make_iterator_property_map(
                                d.begin(), get(vertex_index, g))));

But now that I am changing the indexes, most of this wont work, mainly get(boost::vertex_index, g), that raises In template: cannot form a reference to 'void' and No matching function for call to 'get'

and I have no idea how I need to change that, tried using get(&Vertex::id, g) instead but I get this No matching function for call to 'dijkstra_shortest_paths'

Thanks in advance for your help!

Answer 1

It seems you're conflating 3 concepts here:

1. vertex names
2. vertex descriptors (and vertex iterators, their semantics group them with this bullet)
3. vertex index

ad 1. The names are what you achieved with the internal_vertex_name trait. They offer a convenience mapping from an application-domain identifier ("name", your Vertex::id in the example) to vertex descriptors. In database terms this can be thought of as a "lookup index" into the vertices, but it isn't what BGL refers to as vertex index.

ad 2. The descriptors have semantics that you can change by choosing a Vertex Container Selector. In your example you did indeed choose boost::listS which does make the descriptors and iterators stable across mutation (except for deleted vertices).

ad 3. The Vertex Index is a specific unique mapping of all vertex descriptors to the integral range [0, N) (N == num_vertices(g)) that some algorithms assume so they can be implemented efficiently regardless of the chosen graph model. Consider it "a consistent way of numbering vertices". For some VertexContainer selectors (i.e. boost::vecS) the index is trivial and Boost knows how to implicitly deduce the vertex_index_t property map to use in algorithms.

---

The Problem

In your code, the problem is that you do not have an implicit vertex_index_t property map, due to listS container selector.

By far the easiest "solution" here is to use vecS as your name property already allows you a stable identification [1]:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fmt/ranges.h>
#include <ranges>
using std::views::transform;

struct Vertex {
    int id;
};

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = int;
        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()(name_t const& id) const { return {id}; }
    };
};

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex,
                                    boost::property<boost::edge_weight_t, int>>;

int main() {
    using V = Graph::vertex_descriptor;
    Graph g;

    add_edge(100, 500, 1, g);
    add_edge(200, 600, 1, g);
    add_edge(200, 700, 2, g);
    add_edge(500, 200, 7, g);
    add_edge(500, 600, 3, g);
    add_edge(600, 700, 1, g);
    add_edge(700, 100, 1, g);
    add_edge(700, 200, 1, g);
    assert(num_vertices(g) == 5);

    auto name = get(&Vertex::id, g);
    print_graph(g, name);

    std::vector<V>   p(num_vertices(g));
    std::vector<int> d(num_vertices(g));
    V                source_idx = vertex(1, g);
    dijkstra_shortest_paths(g, source_idx,                   //
                            boost::predecessor_map(p.data()) //
                                .distance_map(d.data()));

    fmt::print("predecessors {} distances {}\n", //
               p | transform([name](V v) { return name[v]; }), d);
}

Which prints Live On Coliru:

g++ -std=c++20 -O2 -Wall -pedantic -pthread main.cpp -lfmt && ./a.out    
500 --> 200 600     
100 --> 500     
600 --> 700     
200 --> 600 700     
700 --> 100 200     
predecessors [100, 100, 500, 700, 600] distances [1, 0, 4, 6, 5]

NOTE How the graph creation is significantly simplified. source_idx is a misnomer (it's not an index, but a descriptor). Also, instead of magically selecting a vertex by some ordinal into the sequence of vertices internally stored, consider addressing by your name property:

V source = find_vertex(500, g).value();
dijkstra_shortest_paths(g, source,                       //
                        boost::predecessor_map(p.data()) //
                            .distance_map(d.data()));

Manual vertex_index_t index

If you really need to store descriptors that stay valid across mutations, you need to supply an artificial external mapping:

std::map<V, int> manual_index;
for (auto v : boost::make_iterator_range(vertices(g)))
    manual_index.emplace(v, manual_index.size());

Which you can then supply using a named parameter:

.vertex_index_map(boost::make_assoc_property_map(manual_index)) 

However, since vertices are not ordinal, your predecessor/distance maps also need indirection:

V source = find_vertex(500, g).value();

auto vidx = boost::make_assoc_property_map(manual_index);
dijkstra_shortest_paths( //
    g, source,
    boost::predecessor_map(make_safe_iterator_property_map(p.data(), p.size(), vidx))
        .distance_map(make_safe_iterator_property_map(d.data(), d.size(), vidx))
        .vertex_index_map(vidx));

Interpreting the predecessor map now requires interpreting the index of the predecessors vector by reverse lookup into manual_index... Perhaps at this rate it's way easier to make actual associative property maps all the way:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fmt/ranges.h>
#include <ranges>
using std::views::transform;

struct Vertex {
    int id;
};

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = int;
        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()(name_t const& id) const { return {id}; }
    };
};

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

int main() {
    using V = Graph::vertex_descriptor;
    Graph g;

    add_edge(100, 500, 1, g);
    add_edge(200, 600, 1, g);
    add_edge(200, 700, 2, g);
    add_edge(500, 200, 7, g);
    add_edge(500, 600, 3, g);
    add_edge(600, 700, 1, g);
    add_edge(700, 100, 1, g);
    add_edge(700, 200, 1, g);
    assert(num_vertices(g) == 5);

    auto name = get(&Vertex::id, g);
    print_graph(g, name);

    std::map<V, int> manual_index;
    std::map<V, V>   p;
    std::map<V, int> d;
    for (auto v : boost::make_iterator_range(vertices(g)))
        manual_index.emplace(v, manual_index.size());

    V source = find_vertex(500, g).value();

    dijkstra_shortest_paths( //
        g, source,
        boost::predecessor_map(boost::make_assoc_property_map(p))
            .distance_map(boost::make_assoc_property_map(d))
            .vertex_index_map(boost::make_assoc_property_map(manual_index)));

    fmt::print("predecessors {}\ndistances {}\n", //
               p | transform([name](auto p) { return std::pair(name[p.first], name[p.second]); }),
               d | transform([name](auto p) { return std::pair(name[p.first], p.second); }));
}

Printing

500 --> 200 600 
100 --> 500 
600 --> 700 
200 --> 600 700 
700 --> 100 200 
predecessors [(500, 500), (100, 700), (600, 500), (200, 700), (700, 600)]
distances [(500, 0), (100, 5), (600, 3), (200, 5), (700, 4)]

[1] with O(log n) lookup