class propretyEdge { std::map<std::string,double> weights; // Date indexed } 我创建了一个包含这些属性的图形,然后用正确的值填充它.
现在的问题是我想在图上的特定权重集上启动Dijkstra算法：例如,一个函数可能是：
voID Dijkstra (string date,parameters ... )
那将使用
weights[date]
图的每个边的值.
我一遍又一遍地阅读文档,我无法清楚地知道自己要做什么.我当然需要写这样的东西,但我不知道要开始：
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));
谢谢您的帮助.
编辑
多亏了精彩的Answer of Sehe,我能够在MacOS和Ubuntu上做到我想要的.
但是当我们尝试在Visual Studio 2012上编译这段代码时,似乎VS并不是很擅长理解boost的指针功能.所以我们修改了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)); 其中有不使用指针功能的优点.
解决方法 由于显然不清楚这个问题 is answered in the other answer,我会解释.你真正需要的是一个自定义的weight_map参数,它是“有状态的”,可以为给定的日期选择一个特定的值.
你可以把它变得像你想要的那样复杂¹,所以你甚至可以在给定未知日期²的情况下插入/推断一个重量,但是为了这个演示的目的,让它保持简单.
让我们如上定义图表类型(大致)：
struct propretyEdge { std::map<std::string,double> weights; // Date indexed };using Graph = adjacency_List<vecS,vecS,directedS,no_property,propretyEdge>; 现在,让我们生成一个随机图,其中包含3个不同日期的随机权重：
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-03-01" }) { Dijkstra(date,g,0); }} 现在你如何实现Dijkstra(…)？从文档示例中收集,你会做类似的事情
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,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.
输入Boost Property Maps
正如我在链接的Is it possible to have several edge weight property maps for one graph BOOST?中所示,您可以拥有各种属性映射³,包括调用用户定义的函数.这是缺失的部分：
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à：完成了
我希望到现在为止,问题中的对应关系以及相关问题的答案是清楚的.剩下要做的就是将完整的实时样本和结果发布在漂亮的图片中：
Live On Coliru
#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,propretyEdge>;voID Dijkstra(std::string const& date,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,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,"2014-03-01" }) g[e].weights[date] = weight_dist(prng); for (std::string const& date : { "2014-01-01",0); }} 输出,例如
¹只要保留您正在调用的算法所需的不变量即可.特别是,在给定相同边缘的情况下,必须在执行期间始终如一地返回相同的权重.此外,一些算法不支持负权重等.
²我强烈建议在这种情况下使用Boost ICL interval_map但我离题了
³另见map set/get requests into C++ class/structure changes
总结以上是内存溢出为你收集整理的c – Dijkstra图表,每个边缘都有一个权重表全部内容，希望文章能够帮你解决c – Dijkstra图表,每个边缘都有一个权重表所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）