Dijkstra 图在每条边上具有 table 个权重

Question

我有一个提升图，每条边都有多个权重（想象一下一天中每小时有一组权重）。这些权重值中的每一个都存储在 propretyEdge class :

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)
);

感谢您的帮助。

编辑

感谢出色的，我能够在 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));

它的优点是不使用指针函数。

Answer 1

因为这个问题显然不是很清楚is answered in the other answer，我会解释一下。

您真正需要的只是一个自定义 weight_map 参数，它是 "stateful" 并且可以 select 给定日期的特定值。

您可以根据需要将其复杂化 ¹，因此您甚至可以 interpolate/extrapolate 给定未知日期的重量 ²，但为了演示的目的，让我们保持简单。

让我们像上面那样（粗略地）定义图形类型：

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-02-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, 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。

输入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);

瞧：完成

我希望到现在为止，问题中的对应关系以及链接问题的答案已经清楚了。剩下要做的就是 post 完整的现场样本和精美图片中的结果：

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, 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);
    }

}

输出，例如

¹ 只要您保留所调用算法所需的不变量。特别是，您必须 return 在执行期间始终如一地使用相同的权重，给定相同的边缘。另外，有些算法不支持负权重等

² 在这种情况下，我强烈建议使用 Boost ICL interval_map，但我离题了

³ 另见 map set/get requests into C++ class/structure changes

Dijkstra 图在每条边上具有 table 个权重

Dijkstra graph with a table of weights on each edge

c++

boost

dijkstra

boost-graph

boost-property-map

输入Boost Property Maps

瞧：完成