在 BGL 介绍性示例，
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;
}
顶点被称为整数索引
enum {a,B,C,D,E,N}在类似的场景中，没有捆绑顶点属性（完整代码在最后）：
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);
VertexDescriptor v我的IDE追踪到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;
}
为了填充图表，我发现使用 VertexDescriptor
for(auto const &e:edges)
{
boost::add_edge(boost::vertex(e.source,graph),boost::vertex(e.target,graph),e,graph);
}
或整数
for(auto const &e:edges)
{
boost::add_edge(e.source,e.target,e,graph);
}
两者都可以填充图表。
dijkstra_shortest_paths()输出：前驱_map(PredecessorMap p_map)
前驱图记录了最短路径树中的边，该树是通过图的遍历计算出来的。算法完成后，V 中所有 u 的边 (p[u],u) 都在树中。图中从顶点 s 到每个顶点 v 的最短路径由顶点 v、p[v]、p[p[v]] 组成，依此类推，直到到达 s（按相反顺序）。不保证该树是最小生成树。如果 p[u] = u，则 u 是源顶点或无法从源到达的顶点。 PredecessorMap 类型必须是读/写属性映射，其键和值类型与图的顶点描述符类型相同。
它表示“PredecessorMap 类型必须是读/写属性映射，其键和值类型与图的顶点描述符类型相同。”
但是，如果我使用
std::vector<VertexDescriptor>std::vector<int>完整代码：
#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;
}
只是想澄清一下 vertex_descriptor 的用法。看来我仍然对某些事情感到困惑...它是否可以与具有整数类型的 graph_traits::vertex_descripitor 互换，至少对于 vecS 选择器来说？好像是又不是...
您将
vertex_descriptorvertex_iterator这基本上就是全部内容了。
无论如何，还有简化的空间，主要是删除未使用的东西：
#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当然，通过索引图进行间接访问对于某些图模型可能很重要：
#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(); }
您可能也对顶点名称感兴趣：Boost 图自定义索引使用 Dijkstra