In BGL introductory example,
using namespace boost;
int main(int,char*[])
{
// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
// Make convenient labels for the vertices
enum { A, B, C, D, E, N };
const int num_vertices = N;
const char* name = "ABCDE";
// writing out the edges in the graph
typedef std::pair<int, int> Edge;
Edge edge_array[] =
{ Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
Edge(C,E), Edge(B,D), Edge(D,E) };
const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
// declare a graph object
Graph g(num_vertices);
// add the edges to the graph object
for (int i = 0; i < num_edges; ++i)
add_edge(edge_array[i].first, edge_array[i].second, g);
...
return 0;
}
The vertices are referred as integer indices enum {a,B,C,D,E,N}.
In a similar scenario, without bundled vertex property (full code at the end):
struct Edge
{
int source;
int target;
float weight;
};
using Graph=boost::adjacency_list<boost::vecS,boost::vecS,boost::undirectedS,boost::no_property,Edge>;
using GraphTraits=boost::graph_traits<Graph>;
using VertexDescriptor=GraphTraits::vertex_iterator;
Graph graph(5); // 5 vertices
VertexDescriptor v=boost::vertex(1,graph);
The definition of VertexDescriptor v fails to compile.
My IDE traced to the definition in adjacency_list.hpp:
template < class Graph, class Config, class Base >
inline typename Config::vertex_descriptor vertex(
typename Config::vertices_size_type n,
const vec_adj_list_impl< Graph, Config, Base >&)
{
return n;
}
To populate the graph, I found that using VertexDescriptor
for(auto const &e:edges)
{
boost::add_edge(boost::vertex(e.source,graph),boost::vertex(e.target,graph),e,graph);
}
or int
for(auto const &e:edges)
{
boost::add_edge(e.source,e.target,e,graph);
}
both can populate the graph.
From dijkstra_shortest_paths() doc
OUT: predecessor_map(PredecessorMap p_map)
The predecessor map records the edges in the shortest path tree, the tree computed by the traversal of the graph. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the tree. The shortest path from vertex s to each vertex v in the graph consists of the vertices v, p[v], p[p[v]], and so on until s is reached, in reverse order. The tree is not guaranteed to be a minimum spanning tree. If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source. The PredecessorMap type must be a Read/Write Property Map whose key and value types are the same as the vertex descriptor type of the graph.
It said "The PredecessorMap type must be a Read/Write Property Map whose key and value types are the same as the vertex descriptor type of the graph."
However, if I construct PredecessorMap using std::vector<VertexDescriptor>, the code failed to compile. I have to use std::vector<int> to construct it instead.
Full code:
#include<iostream>
#include<random>
#include<format>
#include<map>
#include<deque>
#include<memory>
#include<functional>
#include<cassert>
#include<boost/graph/adjacency_list.hpp>
#include<boost/graph/breadth_first_search.hpp>
#include<boost/graph/depth_first_search.hpp>
#include<boost/graph/properties.hpp>
#include<boost/graph/graph_utility.hpp>
#include<boost/graph/dijkstra_shortest_paths.hpp>
#include<boost/property_map/property_map.hpp>
//#include<boost/property_map/transform_value_property_map.hpp>
#include<boost/pending/queue.hpp>
#include<boost/heap/priority_queue.hpp>
#include<boost/heap/fibonacci_heap.hpp>
#include <boost/range/adaptors.hpp>
void test003()
{
std::cout << "test003: " << std::endl;
struct Edge
{
int source;
int target;
float weight;
};
using Graph=boost::adjacency_list<boost::vecS,boost::vecS,boost::undirectedS,boost::no_property,Edge>;
using GraphTraits=boost::graph_traits<Graph>;
using VertexDescriptor=GraphTraits::vertex_iterator;
using EdgeDescriptor=GraphTraits::edge_descriptor;
Graph graph(5); // 5 vertices
std::vector<Edge> edges{{.source=0,.target=1,.weight=10.0},
{.source=1,.target=2,.weight=1.1},
{.source=2,.target=3,.weight=3.4},
{.source=3,.target=0,.weight=8.0},
{.source=2,.target=2,.weight=0.5},
{.source=1,.target=3,.weight=3.3},
{.source=0,.target=0,.weight=2.2},
{.source=3,.target=2,.weight=0.7},
{.source=2,.target=0,.weight=5.2}};
// different type! won't compile.
//VertexDescriptor v=boost::vertex(1,graph);
for(auto const &e:edges)
{
//boost::add_edge(boost::vertex(e.source,graph),boost::vertex(e.target,graph),e,graph);
boost::add_edge(e.source,e.target,e,graph);
}
auto weightMap=boost::get(&Edge::weight,graph);
auto vertexIndexMap=boost::get(boost::vertex_index,graph);
std::vector<float> distances(boost::num_vertices(graph));
// won't compile if use VertexDescriptor.
//std::vector<VertexDescriptor> predecessors(boost::num_vertices(graph));
std::vector<int> predecessors(boost::num_vertices(graph));
auto distanceMap=boost::make_iterator_property_map(distances.begin(),vertexIndexMap);
auto predecessorMap=boost::predecessor_map(boost::make_iterator_property_map(predecessors.begin(),vertexIndexMap));
//VertexDescriptor startingVertex=boost::vertex(1,graph);
int startingVertex=1;
boost::dijkstra_shortest_paths(graph,
boost::vertex(startingVertex,graph),
boost::weight_map(get(&Edge::weight,graph))
.distance_map(make_iterator_property_map(distances.begin(),get(boost::vertex_index, graph)))
.predecessor_map(make_iterator_property_map(predecessors.begin(),get(boost::vertex_index,graph))));
std::cout<<"The shortest paths:"<<std::endl;
for(int i=0;i<boost::num_vertices(graph);++i)
{
if(i==startingVertex)
continue;
std::cout<<"From "<<startingVertex<<" to "<<i<<" is "<<distances[i]<<": ";
if(i==predecessors[i])
{
std::cout<<"No route."<<std::endl;
}
else
{
std::cout<<i<<" -> ";
for(auto p=predecessors[i];p<predecessors.size() && p!=predecessors[p] && p!=startingVertex;p=predecessors[p])
{
std::cout<<p<<" -> ";
}
std::cout<<startingVertex<<std::endl;
}
}
std::cout << "test003: done." << std::endl;
}
int main()
{
test003();
return 0;
}
Just would like to have it clarified the usage of vertex_descriptor. It seems I still confused with something... Is it interchangeable with graph_traits::vertex_descripitor with integral types, at least for vecS selector? It seems yes and no...
You mistyped vertex_descriptor as vertex_iterator.
That's basically all there was to it.
Regardless, there's room for simplifications, mostly by removal of unused things:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
void test003() {
std::cout << "test003: " << std::endl;
using Weight = float;
struct Edge { Weight weight; };
using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, Edge>;
using V = G::vertex_descriptor;
G graph(5); // 5 vertices
[[maybe_unused]] V v = boost::vertex(1, graph);
for (auto const& [source, target, weight] : //
{std::tuple{0u, 1u, 10.0f}, {1, 2, 1.1}, {2, 3, 3.4}, {3, 0, 8.0},
{2, 2, 0.5}, {1, 3, 3.3}, {0, 0, 2.2}, {3, 2, 0.7}, {2, 0, 5.2}})
{
add_edge(source, target, {weight}, graph);
}
std::vector<Weight> distances(num_vertices(graph));
std::vector<V> predecessors(num_vertices(graph));
V start = vertex(1, graph);
dijkstra_shortest_paths(graph, start,
weight_map(get(&Edge::weight, graph))
.distance_map(distances.data())
.predecessor_map(predecessors.data()));
std::cout << "The shortest paths:" << std::endl;
for (auto v : boost::make_iterator_range(vertices(graph))) {
if (v == start)
continue;
std::cout << "From " << start << " to " << v << " is " << distances[v] << ": ";
if (v == predecessors[v]) {
std::cout << "No route." << std::endl;
} else {
std::cout << v << " -> ";
for (auto p = predecessors[v]; //
p < predecessors.size() && p != predecessors[p] && p != start; //
p = predecessors[p])
std::cout << p << " -> ";
std::cout << start << std::endl;
}
}
std::cout << "test003: done." << std::endl;
}
int main() { test003(); }
vecS vertex storageOf course, indirection through an index map could be important for some graph models:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
using Weight = float;
struct Edge {
Weight weight;
};
template <typename Graph, typename V = Graph::vertex_descriptor>
void do_the_thing(Graph const& graph, V start) {
auto const N = num_vertices(graph);
std::map<V, unsigned> temp_map;
for (auto v : boost::make_iterator_range(vertices(graph)))
temp_map[v] = temp_map.size();
std::vector<Weight> distances(N);
std::vector<V> predecessors(N);
auto vidx = boost::make_assoc_property_map(temp_map);
auto wmap = get(&Edge::weight, graph);
auto dmap = make_safe_iterator_property_map(distances.begin(), distances.size(), vidx, Weight{});
auto pmap =
make_safe_iterator_property_map(predecessors.begin(), distances.size(), vidx, graph.null_vertex());
dijkstra_shortest_paths( //
graph, start, weight_map(wmap).distance_map(dmap).predecessor_map(pmap).vertex_index_map(vidx));
std::cout << "The shortest paths:" << std::endl;
for (auto v : boost::make_iterator_range(vertices(graph))) {
if (v == start)
continue;
auto i = vidx[v];
std::cout << "From " << vidx[start] << " to " << i << " is " << distances[i] << ": ";
if (v == predecessors[i]) {
std::cout << "No route." << std::endl;
} else {
std::cout << vidx[v] << " -> ";
for (V cur = v, p = predecessors[i]; cur != p && p != start;) {
std::cout << vidx[cur] << " -> ";
cur = p;
p = predecessors[vidx[cur]];
}
std::cout << vidx[start] << std::endl;
}
}
}
void test003() {
std::cout << "test003: " << std::endl;
using G = boost::adjacency_list<boost::vecS, boost::listS /*NOTE*/, //
boost::undirectedS, boost::no_property, Edge>;
G graph;
std::array<G::vertex_descriptor, 5> vmap = {};
for (auto i = 0u; i < 5; ++i)
vmap[i] = add_vertex(graph);
for (auto const& [source, target, weight] : //
{std::tuple{0u, 1u, 10.0f}, {1, 2, 1.1}, {2, 3, 3.4}, {3, 0, 8.0},
{2, 2, 0.5}, {1, 3, 3.3}, {0, 0, 2.2}, {3, 2, 0.7}, {2, 0, 5.2}})
add_edge(vmap[source], vmap[target], {weight}, graph);
do_the_thing(graph, vertex(1, graph));
std::cout << "test003: done." << std::endl;
}
int main() { test003(); }
You might be interested in vertex names as well: Boost graph custom indexes use Dijkstra