Dijkstra图，每条边都有权重表 [英] Dijkstra graph with a table of weights on each edge
问题描述
我有一个提升图，其中每个边的权重为倍数(想象一天中每小时的一组权重).这些权重值中的每一个都存储在一个propretyEdge类中:
I have a boost graph with multiples weights for each edges (imagine one set of weights per hour of the day). Every one of those weights values is stored in a propretyEdge class :
class propretyEdge {
std::map<std::string,double> weights; // Date indexed
}
我用这些属性创建了一个图形，然后用正确的值填充了它. 现在的问题是，我想对图形上的一组特定权重启动Dijkstra算法:例如，一个可能是的函数:
I created a graph with those properties, and then filled it with the right values. The problem is now that I want to launch the Dijkstra algorithm over a particular set of weight on the graph : for example a function that could be :
void Dijkstra (string date, parameters ... )
那将使用
weights[date]
图的每个Edge的
值.
value for each Edge of the graph.
我一遍又一遍地阅读了文档，但我对所要做的事情一无所知.我当然需要写这样的东西，但是我不知道要开始:
I read over and over the documentation, and I couldn't have a clear picture of what I have to do. I surely need to write something like this, but I have no idea were to start :
boost::dijkstra_shortest_paths (
(*graph_m),
vertex_origin_num_l,
// weight_map (get (edge_weight, (*graph_m)))
// predecessor_map(boost::make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, (*graph_m)))).
// distance_map(boost::make_iterator_property_map(distances.begin (), get(vertex_index,(*graph_m) )))
predecessor_map(predecessorMap).
distance_map(distanceMap)
);
谢谢您的帮助.
修改
感谢精彩的 Sehe的答案，我能够在MacOS和Ubuntu上完全实现自己想要的功能.
Thanks to the wonderful Answer of Sehe, I was able to do exactly what I wanted on MacOS and on Ubuntu.
但是，当我们尝试在Visual Studio 2012上编译这段代码时，似乎VS不太善于理解boost的指针功能.所以我们修改了Sehe的部分:
But when we tried to compile this piece of code on Visual Studio 2012, it appeared that VS wasn't very good at understanding pointer function of boost. So we modified the part of Sehe :
auto dated_weight_f = [&](Graph::edge_descriptor ed) {
return g[ed].weights.at(date);
};
auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);
作者:
class dated_weight_f {
public:
dated_weight_f(Graph* graph_p,std::string date_p){
graph_m=graph_p;
date_m=date_p;
}
typedef double result_type;
result_type operator()(Edge edge_p) const{
return (*graph_m)[edge_p].weights.at(date_m);
}
private:
Graph* graph_m;
std::string date_m;
};
const auto dated_weight_map = make_function_property_map<Edge>(dated_weight_f(graph_m,date_l));
具有不使用指针功能的优点.
Which had the advantage of not using a pointer function.
推荐答案
Since it's apparently not immediately clear that this question is answered in the other answer, I'll explain.
您真正需要的只是一个自定义的weight_map参数，该参数是有状态的"，可以为给定的日期选择一个特定的值.
All you really need is a custom weight_map parameter that is "stateful" and can select a certain value for a given date.
您可以根据需要将其复杂化¹，因此甚至可以在给定未知日期的情况下内插/外推权重²，但是为了演示起见，让我们保持简单.
You can make this as complicated as you wish ¹, so you could even interpolate/extrapolate a weight given an unknown date ², but let's for the purpose of this demonstration keep it simple.
让我们大致地定义图形类型:
Let's define the graph type (roughly) as above:
struct propretyEdge {
std::map<std::string, double> weights; // Date indexed
};
using Graph = adjacency_list<vecS, vecS, directedS, no_property, propretyEdge>;
现在，让我们生成一个随机图，它具有3个不同日期的随机权重:
Now, let's generate a random graph, with random weights for 3 different dates:
int main() {
Graph g;
std::mt19937 prng { std::random_device{}() };
generate_random_graph(g, 8, 12, prng);
uniform_real<double> weight_dist(10,42);
for (auto e : make_iterator_range(edges(g)))
for (auto&& date : { "2014-01-01", "2014-02-01", "2014-03-01" })
g[e].weights[date] = weight_dist(prng);
然后，跳到目标:
for (std::string const& date : { "2014-01-01", "2014-02-01", "2014-03-01" }) {
Dijkstra(date, g, 0);
}
}
现在如何实现Dijkstra(...)?从文档样本中收集信息，您会做类似的事情
Now how do you implement Dijkstra(...)? Gleaning from the documentation sample, you'd do something like
void Dijkstra(std::string const& date, Graph const& g, int vertex_origin_num_l = 0) {
// magic postponed ...
std::vector<Graph::vertex_descriptor> p(num_vertices(g));
std::vector<double> d(num_vertices(g));
std::vector<default_color_type> color_map(num_vertices(g));
boost::typed_identity_property_map<Graph::vertex_descriptor> vid; // T* property maps were deprecated
dijkstra_shortest_paths(g, vertex_origin_num_l,
weight_map(dated_weight_map).
predecessor_map(make_iterator_property_map(p.data(), vid)).
distance_map(make_iterator_property_map(d.data(), vid)).
color_map(make_iterator_property_map(color_map.data(), vid))
);
现在，这里唯一不清楚的位应该是dated_weight_map.
Now the only unclear bit here should be dated_weight_map.
As I showed in the linked Is it possible to have several edge weight property maps for one graph BOOST?, you can have all kinds of property maps ³, including invocation of user-defined functions. This is the missing piece:
auto dated_weight_f = [&](Graph::edge_descriptor ed) {
return g[ed].weights.at(date);
};
auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);
Voilà:完成
我希望到现在为止，问题中的对应关系以及链接问题的答案是清楚的.剩下要做的就是将完整的实时样本和结果张贴在一张漂亮的图片中:
Voilà: done
I hope that by now, the correspondence in the question as well as the answer of the linked question is clear. All that's left to do is post the full live sample and the outcome in a pretty picture:
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/property_map_iterator.hpp>
#include <random>
#include <boost/graph/random.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <fstream>
using namespace boost;
struct propretyEdge {
std::map<std::string, double> weights; // Date indexed
};
using Graph = adjacency_list<vecS, vecS, directedS, no_property, propretyEdge>;
void Dijkstra(std::string const& date, Graph const& g, int vertex_origin_num_l = 0) {
auto dated_weight_f = [&](Graph::edge_descriptor ed) {
return g[ed].weights.at(date);
};
auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);
std::vector<Graph::vertex_descriptor> p(num_vertices(g));
std::vector<double> d(num_vertices(g));
std::vector<default_color_type> color_map(num_vertices(g));
boost::typed_identity_property_map<Graph::vertex_descriptor> vid; // T* property maps were deprecated
dijkstra_shortest_paths(g, vertex_origin_num_l,
weight_map(dated_weight_map).
predecessor_map(make_iterator_property_map(p.data(), vid)).
distance_map(make_iterator_property_map(d.data(), vid)).
color_map(make_iterator_property_map(color_map.data(), vid))
);
std::cout << "distances and parents for '" + date + "':" << std::endl;
for (auto vd : make_iterator_range(vertices(g)))
{
std::cout << "distance(" << vd << ") = " << d[vd] << ", ";
std::cout << "parent(" << vd << ") = " << p[vd] << std::endl;
}
std::cout << std::endl;
std::ofstream dot_file("dijkstra-eg-" + date + ".dot");
dot_file << "digraph D {\n"
" rankdir=LR\n"
" size=\"6,4\"\n"
" ratio=\"fill\"\n"
" graph[label=\"shortest path on " + date + "\"];\n"
" edge[style=\"bold\"]\n"
" node[shape=\"circle\"]\n";
for (auto ed : make_iterator_range(edges(g))) {
auto u = source(ed, g),
v = target(ed, g);
dot_file
<< u << " -> " << v << "[label=\"" << get(dated_weight_map, ed) << "\""
<< (p[v] == u?", color=\"black\"" : ", color=\"grey\"")
<< "]";
}
dot_file << "}";
}
int main() {
Graph g;
std::mt19937 prng { std::random_device{}() };
generate_random_graph(g, 8, 12, prng);
uniform_real<double> weight_dist(10,42);
for (auto e : make_iterator_range(edges(g)))
for (auto&& date : { "2014-01-01", "2014-02-01", "2014-03-01" })
g[e].weights[date] = weight_dist(prng);
for (std::string const& date : { "2014-01-01", "2014-02-01", "2014-03-01" }) {
Dijkstra(date, g, 0);
}
}
输出，例如
¹只要保持调用算法所需的不变式即可.特别是，在给定相同边的情况下，必须在执行过程中始终返回相同的权重.另外，某些算法不支持负权重等.
¹ As long as you keep the invariants required by the algorithm you're invoking. In particular, you must return the same weight consistently during the execution, given the same edge. Also, some algorithms don't support negative weight etc.
²我强烈建议在这种情况下使用Boost ICL interval_map，但我离题了
² I'd highly suggest using a Boost ICL interval_map in such a case but I digress
³另请参见地图设置/获取C ++类/结构更改的请求
这篇关于Dijkstra图，每条边都有权重表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
