I am trying to create a graph via Boost graph library, that has custom indexing (stable ones when vertexes are deleted),
I copied the solution 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 <catch2/catch.hpp>
#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!
It seems you're conflating 3 concepts here:
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.
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()));
vertex_index_t indexIf 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:
#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