#include <boost/graph/adjacency_list.hpp>
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
boost::no_property,
boost::property<boost::edge_weight_t, double>>
DiGraph;
typedef boost::graph_traits<DiGraph>::vertex_descriptor vertex_descriptor;
int main () {
std::vector<std::size_t> vertices = { 1, 5, 10};
std::vector<std::pair<std::size_t, std::size_t>> edges = {std::make_pair(1, 5),
std::make_pair(5, 10)};
std::vector<double> weights = {2., 2.};
DiGraph di_graph (edges.begin(), edges.end(), weights.begin(), vertices.size());
DiGraph::vertex_descriptor v_start = boost::vertex(1, di_graph);
std::vector<vertex_descriptor> parents(boost::num_vertices(di_graph));
boost::dijkstra_shortest_paths(di_graph, v_start,
boost::predecessor_map(boost::make_iterator_property_map(parents.begin(), boost::get(boost::vertex_index, di_graph))));
}
这将分配一个大小为11的vector父对象，因为boost使用连续的顶点索引。我想要不连续的顶点(1,5,10…)，但不希望向量父结点占用不必要的内存空间。我如何从我的顶点索引映射到顶点索引1,2,3，并将其传递给boost::dijkstra_shortest_paths?
最重要的是，在结构体parent中接收dijkstra的结果，并使用我的索引访问元素的前身，例如
，会更方便。parents[10]
但是没有长度为11的向量或者只有一个简单的转换函数如果我可以使用
parents[f(10)]
我确实看了一下boost graph的文档，并认为IndexMap可以使这成为可能，但我不理解这个概念，不能使它工作。
与boost::vecS顶点容器的选择、顶点索引是隐式的,叫
DiGraph di_graph(
edges.begin(), edges.end(), weights.begin(), vertices.size());
是一个谎言:你告诉它有三个顶点,然后你索引越界(5、10(0,1,2)外)。
还要注意
V v_start = boost::vertex(1, di_graph);
选择第二个顶点，而不是顶点1。
内部名称我可能会建议最近增加一个:内部顶点名称。如果我们添加一个顶点属性包，就像int:
using DiGraph = boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::directedS,
int,
boost::property<boost::edge_weight_t, double>>;
然后告诉BGL我们可以用它作为顶点的内部名称:
template<> struct boost::graph::internal_vertex_name<int> {
struct type : std::identity {
using result_type = int;
};
};
现在创建等价图很简单:
DiGraph g;
add_edge(1, 5, 2., g);
add_edge(5, 10, 2., g);
。您可以看到它创建了带有隐式索引的顶点作为描述符:
for (auto e : make_iterator_range(edges(g))) {
std::cout << "edge: " << e << "n";
}
打印:
edge: (0,2)
edge: (1,0)
要获取名称，使用如下的属性映射:
for (auto v : make_iterator_range(vertices(g))) {
std::cout << "vertex at index " << v << " named " << g[v] << "n";
}
打印
vertex at index 0 named 5
vertex at index 1 named 1
vertex at index 2 named 10
使用内部顶点名称，您可以通过属性束查询顶点:
boost::optional<V> v_start = g.vertex_by_property(1);
dijkstra_shortest_paths(
g,
v_start.value(),
boost::predecessor_map(boost::make_safe_iterator_property_map(
parents.begin(), parents.size(), get(boost::vertex_index, g))));
for (size_t i = 0; i < parents.size(); ++i) {
std::cout << "Parent for '" << g[i] << "' is '" << g[parents[i]] << "'n";
}
现场演示
Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
template<> struct boost::graph::internal_vertex_name<int> {
struct type : std::identity {
using result_type = int;
};
};
using DiGraph = boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::directedS,
int,
boost::property<boost::edge_weight_t, double>>;
using V = DiGraph::vertex_descriptor;
using boost::make_iterator_range;
int main()
{
DiGraph g;
add_edge(1, 5, 2., g);
add_edge(5, 10, 2., g);
for(auto e : make_iterator_range(edges(g)))
std::cout << "edge: " << e << "n";
for(auto v : make_iterator_range(vertices(g)))
std::cout << "vertex at index " << v << " named " << g[v] << "n";
boost::optional<V> v_start = g.vertex_by_property(1);
std::vector<V> parents(num_vertices(g));
dijkstra_shortest_paths(
g,
v_start.value(),
boost::predecessor_map(boost::make_safe_iterator_property_map(
parents.begin(), parents.size(), get(boost::vertex_index, g))));
for (size_t i = 0; i < parents.size(); ++i) {
std::cout << "Parent for '" << g[i] << "' is '" << g[parents[i]] << "'n";
}
}
打印
edge: (0,2)
edge: (1,0)
vertex at index 0 named 5
vertex at index 1 named 1
vertex at index 2 named 10
Parent for '5' is '1'
Parent for '1' is '1'
Parent for '10' is '5'
第一步:查看捆绑属性https://www.boost.org/doc/libs/1_79_0/libs/graph/doc/bundles.html
第二:
非相邻顶点的(1、5、10 . .)";这些应该被视为顶点的属性。如"1";是顶点0的一个属性
第三:创建一个顶点类1,5,10…作为公共属性
四:创建一个boost图形使用你的顶点类，设置和获得1,5,10 ..如捆绑属性页所述。