如何复制boost::property_map?
How to copy boost::property_map?
我想从一个图中获得两个组最短路径(一对多),定义为adjacency_list
具有内部属性(相对于 bundle)
理论上我可以在两个参考节点 n1
和 n2
上 运行 dijkstra_shortest_paths
。如果我创建两个 property_maps
并将它们按顺序传递给 dijkstra_...
我会得到看起来像是同一地图的两个视图。两者都指向dijkstra_shortest_paths
的最后运行的结果,这样旧的结果就没有了。我应该怎么做才能达到预期的效果?
// Define some property maps
property_map<ugraph_t,edge_weight_t>::type Weight=get(edge_weight,G);
property_map<ugraph_t,vertex_distance_t>::type Dist1=get(vertex_distance,G);
// One line later, I expect this to be mapped to the SPs w.r.t n1
// Run SP on the first node
dijkstra_shortest_paths(G,n1,predecessor_map(Prev1).distance_map(Dist1).weight_map(Weight));
// New property maps
property_map<ugraph_t,vertex_distance_t>::type Dist2(Dist1); // And now to the second set
property_map<ugraph_t,vertex_predecessor_t>::type Prev2(Prev1); // But no two sets will result...
// Run SP on the second node
// This will run fine, but I will lose the first SP set (with or without a copy constructor above)
dijkstra_shortest_paths(G,n2,predecessor_map(Prev2).distance_map(Dist2).weight_map(Weight));
结论: 如果我没记错的话,property_map
可以被认为是带有迭代器的接口,因此复制 property_map
s 不会感觉。解决方案是传递一个动态构建的自定义容器。该解决方案在下面@sehe 的回答中有详细说明,非常感谢!
注意: 这仅在顶点容器类型为 vecS
时有效。使用 listS
必须 "manually" 逐个顶点复制。
距离图不应该是内部图 属性。
前身地图也是如此。
它们不是图的逻辑上属性。它们是查询的结果。因此,它们是 属性 查询参数的组合,包括图表、起始节点等。
如果您想保存内饰的价值 属性,只需按照通常的方式保存即可:
std::vector<double> saved_distances(num_vertices(G));
BGL_FORALL_VERTICES(v, G, ugraph_t)
saved_distances.push_back(Dist1[v]);
解决方法
复制地图的解决方法:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/iteration_macros.hpp>
using namespace boost;
using ugraph_traits = graph_traits<adjacency_list<vecS, vecS, directedS> >;
using ugraph_t = adjacency_list<
vecS, vecS, directedS,
property<vertex_distance_t, double,
property<vertex_predecessor_t, ugraph_traits::vertex_descriptor>
>,
property<edge_weight_t, double>
>;
int main() {
ugraph_t G(10);
ugraph_t::vertex_descriptor n1 = 0, n2 = 1, v;
(void) n1;
(void) n2;
// ...
property_map<ugraph_t, edge_weight_t>::type Weight = get(edge_weight,G);
property_map<ugraph_t, vertex_distance_t>::type Dist1 = get(vertex_distance,G);
property_map<ugraph_t, vertex_predecessor_t>::type Prev1 = get(vertex_predecessor,G);
dijkstra_shortest_paths(G, n1,
predecessor_map(Prev1)
.distance_map(Dist1)
.weight_map(Weight)
);
std::vector<double> saved_distances(num_vertices(G));
std::vector<ugraph_t::vertex_descriptor> saved_predecessors(num_vertices(G));
BGL_FORALL_VERTICES(v, G, ugraph_t) {
saved_distances.push_back(Dist1[v]);
saved_predecessors.push_back(Prev1[v]);
}
/*
* // C++11 style
* for(auto v : make_iterator_range(vertices(G)))
* saved_distances[v] = Dist1[v];
*/
// Run SP on the second node
dijkstra_shortest_paths(G,n2,predecessor_map(Prev1).distance_map(Dist1).weight_map(Weight));
}
建议
我建议将结果贴图分开容器,只留下边缘权重内部:
Better Yet: refactor to remove duplicated code
所以就变成了
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
using ugraph_t = adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, double> >;
using Vertex = ugraph_t::vertex_descriptor;
struct ShortestPaths {
ShortestPaths(size_t num_vertices);
std::vector<double> distances;
std::vector<Vertex> predecessors;
};
ShortestPaths GetShortestPaths(ugraph_t const& G, Vertex start);
int main() {
ugraph_t G(10);
Vertex n1 = 0, n2 = 1;
ShortestPaths sp1 = GetShortestPaths(G, n1);
ShortestPaths sp2 = GetShortestPaths(G, n2);
}
// some other cpp file...:
ShortestPaths::ShortestPaths(size_t num_vertices)
: distances(num_vertices), predecessors(num_vertices)
{ }
ShortestPaths GetShortestPaths(ugraph_t const& G, Vertex start) {
ShortestPaths result(num_vertices(G));
dijkstra_shortest_paths(G, start,
predecessor_map(make_container_vertex_map(result.predecessors, G))
.distance_map (make_container_vertex_map(result.distances, G))
.weight_map (get(edge_weight, G))
);
return result;
}
请注意,不再需要复制结果。事实上,您甚至不需要保留图形来保留查询结果。
我想从一个图中获得两个组最短路径(一对多),定义为adjacency_list
具有内部属性(相对于 bundle)
理论上我可以在两个参考节点 n1
和 n2
上 运行 dijkstra_shortest_paths
。如果我创建两个 property_maps
并将它们按顺序传递给 dijkstra_...
我会得到看起来像是同一地图的两个视图。两者都指向dijkstra_shortest_paths
的最后运行的结果,这样旧的结果就没有了。我应该怎么做才能达到预期的效果?
// Define some property maps
property_map<ugraph_t,edge_weight_t>::type Weight=get(edge_weight,G);
property_map<ugraph_t,vertex_distance_t>::type Dist1=get(vertex_distance,G);
// One line later, I expect this to be mapped to the SPs w.r.t n1
// Run SP on the first node
dijkstra_shortest_paths(G,n1,predecessor_map(Prev1).distance_map(Dist1).weight_map(Weight));
// New property maps
property_map<ugraph_t,vertex_distance_t>::type Dist2(Dist1); // And now to the second set
property_map<ugraph_t,vertex_predecessor_t>::type Prev2(Prev1); // But no two sets will result...
// Run SP on the second node
// This will run fine, but I will lose the first SP set (with or without a copy constructor above)
dijkstra_shortest_paths(G,n2,predecessor_map(Prev2).distance_map(Dist2).weight_map(Weight));
结论: 如果我没记错的话,property_map
可以被认为是带有迭代器的接口,因此复制 property_map
s 不会感觉。解决方案是传递一个动态构建的自定义容器。该解决方案在下面@sehe 的回答中有详细说明,非常感谢!
注意: 这仅在顶点容器类型为 vecS
时有效。使用 listS
必须 "manually" 逐个顶点复制。
距离图不应该是内部图 属性。 前身地图也是如此。
它们不是图的逻辑上属性。它们是查询的结果。因此,它们是 属性 查询参数的组合,包括图表、起始节点等。
如果您想保存内饰的价值 属性,只需按照通常的方式保存即可:
std::vector<double> saved_distances(num_vertices(G));
BGL_FORALL_VERTICES(v, G, ugraph_t)
saved_distances.push_back(Dist1[v]);
解决方法
复制地图的解决方法:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/iteration_macros.hpp>
using namespace boost;
using ugraph_traits = graph_traits<adjacency_list<vecS, vecS, directedS> >;
using ugraph_t = adjacency_list<
vecS, vecS, directedS,
property<vertex_distance_t, double,
property<vertex_predecessor_t, ugraph_traits::vertex_descriptor>
>,
property<edge_weight_t, double>
>;
int main() {
ugraph_t G(10);
ugraph_t::vertex_descriptor n1 = 0, n2 = 1, v;
(void) n1;
(void) n2;
// ...
property_map<ugraph_t, edge_weight_t>::type Weight = get(edge_weight,G);
property_map<ugraph_t, vertex_distance_t>::type Dist1 = get(vertex_distance,G);
property_map<ugraph_t, vertex_predecessor_t>::type Prev1 = get(vertex_predecessor,G);
dijkstra_shortest_paths(G, n1,
predecessor_map(Prev1)
.distance_map(Dist1)
.weight_map(Weight)
);
std::vector<double> saved_distances(num_vertices(G));
std::vector<ugraph_t::vertex_descriptor> saved_predecessors(num_vertices(G));
BGL_FORALL_VERTICES(v, G, ugraph_t) {
saved_distances.push_back(Dist1[v]);
saved_predecessors.push_back(Prev1[v]);
}
/*
* // C++11 style
* for(auto v : make_iterator_range(vertices(G)))
* saved_distances[v] = Dist1[v];
*/
// Run SP on the second node
dijkstra_shortest_paths(G,n2,predecessor_map(Prev1).distance_map(Dist1).weight_map(Weight));
}
建议
我建议将结果贴图分开容器,只留下边缘权重内部:
Better Yet: refactor to remove duplicated code
所以就变成了
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
using ugraph_t = adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, double> >;
using Vertex = ugraph_t::vertex_descriptor;
struct ShortestPaths {
ShortestPaths(size_t num_vertices);
std::vector<double> distances;
std::vector<Vertex> predecessors;
};
ShortestPaths GetShortestPaths(ugraph_t const& G, Vertex start);
int main() {
ugraph_t G(10);
Vertex n1 = 0, n2 = 1;
ShortestPaths sp1 = GetShortestPaths(G, n1);
ShortestPaths sp2 = GetShortestPaths(G, n2);
}
// some other cpp file...:
ShortestPaths::ShortestPaths(size_t num_vertices)
: distances(num_vertices), predecessors(num_vertices)
{ }
ShortestPaths GetShortestPaths(ugraph_t const& G, Vertex start) {
ShortestPaths result(num_vertices(G));
dijkstra_shortest_paths(G, start,
predecessor_map(make_container_vertex_map(result.predecessors, G))
.distance_map (make_container_vertex_map(result.distances, G))
.weight_map (get(edge_weight, G))
);
return result;
}
请注意,不再需要复制结果。事实上,您甚至不需要保留图形来保留查询结果。