Dijkstra 图，每条边都有一个权重表

2021-12-24 00:00:00 dijkstra c++ boost boost-graph boost-property-map

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

图的每个边的值.

我一遍又一遍地阅读文档，但我无法清楚地了解我必须做什么.我肯定需要写这样的东西，但我不知道要开始:

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.

您可以随心所欲地将其复杂化1，因此您甚至可以在给定未知日期的情况下内插/外推一个权重2，但为了本演示的目的，让我们保持简单.

You can make this as complicated as you wish 1, so you could even interpolate/extrapolate a weight given an unknown date 2, 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.

正如我在链接的 一个图 BOOST 是否可以有多个边权重属性映射?，您可以拥有各种属性映射3，包括调用用户定义的函数.这是缺失的部分:

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 3, 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à: 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 {
"
        "  rankdir=LR
"
        "  size="6,4"
"
        "  ratio="fill"
"
        "  graph[label="shortest path on " + date + ""];
"
        "  edge[style="bold"]
" 
        "  node[shape="circle"]
";

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

}

输出，例如

1 只要您保留您正在调用的算法所需的不变量.特别是，在给定相同的边缘的情况下，您必须在执行期间始终如一地返回相同的权重.另外，有些算法不支持负权重等.

1 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.

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

2 I'd highly suggest using a Boost ICL interval_map in such a case but I digress

3 另见 地图集/获取请求到 C++ 类/结构更改

相关文章