Dijkstra图，每条边都有权重表

本文介绍了Dijkstra图，每条边都有权重表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有一个提升图，其中每个边的权重为倍数(想象一天中每小时的一组权重).这些权重值中的每一个都存储在一个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.

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:

在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, 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图，每条边都有权重表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

Dijkstra图