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?
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:
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).vertex_index_t nor vertex_name_t property.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
other just to show when/how it gets default constructedlistS because it
vertex_descriptor (void*) which does not conflict with the id type (size_t) in overload resolutionNext we teach BGL about our Internal Vertex Name.
This is purely parameterized by
Vertexbundle, 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
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));
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.
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");
#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 -->
hash_mapS leads to unordered_set<void*, hash<void*>, equal_to<void*>, allocator<void*>> as the m_vertices type.