提升dijkstra琴弦边缘的重量 [英] Boost dijkstra string edge weight

问题描述

是否可以使用字符串值代替双精度属性 typedef adjacency_list < vecS, vecS, directedS, property<vertex_name_t, string>, property < edge_weight_t, string> > Graph; 我的目标是使用dijkstra算法. PS:我已经尝试将double替换为string，并且在算法内产生错误.

is it possible to use string value instead of double properties typedef adjacency_list < vecS, vecS, directedS, property<vertex_name_t, string>, property < edge_weight_t, string> > Graph; My goal is to use the dijkstra algorithm. PS: I already tried replacing the double with string and it generates an error within the algorithm.

std::vector<vertexd> P(num_vertices(g));
std::vector<string> d(num_vertices(g));
vertexd s = vertex(0, g);

dijkstra_shortest_paths(g, s,
    predecessor_map(boost::make_iterator_property_map(P.begin(), get(boost::vertex_index, g))).
    distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, g))));

错误:

错误13错误C2664:'D boost :: closed_plus :: operator()(const T&，const T&)const':无法从'const std :: basic_string，std :: allocator>转换参数2 '改为'const D&' C:\ boost_1_58_0 \ boost \ graph \ dijkstra_shortest_paths.hpp 190

Error 13 error C2664: 'D boost::closed_plus::operator ()(const T &,const T &) const' : cannot convert argument 2 from 'const std::basic_string,std::allocator>' to 'const D &' C:\boost_1_58_0\boost\graph\dijkstra_shortest_paths.hpp 190

推荐答案

是的，您可以拥有字符串属性.

Yes you can have a string property.

否，dijkstra需要

No, dijkstra requires

所有边缘权重均为非负的情况下的加权，有向或无向图

a weighted, directed or undirected graph for the case where all edge weights are nonnegative

因此，权重必须为数字.当然，如果您可以对属性类型实现算术运算和std::numeric_limit<>，那可能很好(但是在执行此操作之前，您确实必须抓紧时间).

So the weight is required to be numerical. Of course, if you can implement arithmetic operations and std::numeric_limit<> for your property type it might be fine (but you really have to scratch your head before doing that).

更新 _实际上，事实证明，此文档简化了一点，您实际上可以针对体重类型覆盖零，进行比较和组合.请参见注释中的链接的示例(HT @cv_and_he)_

UPDATE _Actually, it turns out this documentation simplifies a bit, and you can actually override zero, comparison and combining for your weight type. See the linked sample in the comments (HT @cv_and_he)_

所以，我不想成为那个人，但是:为什么.

So, I hate to be that guy, but: why.

由于权重无论如何都是单位数量，将权重存储为字符串的目标是什么?您是否正在遇到一个不同的问题，使您无法正确存储权重?

Since the weights are amounts in any unit anyways, what is the goal storing them as strings? Are you, perhaps having a different issue that prevents you from storing the weights properly?

也就是说，这是一种方法:

That said, here's a way:

使用transform_value_property_map，您可以动态地将字符串转换为双精度:

Using transform_value_property_map you can transform strings to doubles on the fly:

在Coliru上直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/lexical_cast.hpp>
#include <iostream>

using Weight = std::string;
//using Weight = double;

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
        boost::property<boost::vertex_name_t, std::string>,
        boost::property<boost::edge_weight_t, Weight>
    > Graph;

using vertexd = Graph::vertex_descriptor;

Graph generate();

int main() {
    using namespace boost;

    Graph g = generate();
    std::vector<vertexd> P(num_vertices(g));
    std::vector<double>  d(num_vertices(g));
    vertexd s = vertex(0, g);

    auto to_double = [](Weight const& v) { return lexical_cast<double>(v); };

    dijkstra_shortest_paths(
        g, s, 
         weight_map  (make_transform_value_property_map(to_double, get(edge_weight, g)))
        .predecessor_map(make_container_vertex_map(P))
        .distance_map(make_container_vertex_map(d))
    );

    boost::dynamic_properties dp;
    dp.property("node_id", get(vertex_name, g));
    dp.property("label",  get(edge_weight, g));
    write_graphviz_dp(std::cout, g, dp);
}

#include <boost/graph/random.hpp>
#include <boost/range/iterator_range.hpp>
#include <random>

Graph generate() {
    using namespace boost;

    std::mt19937 prng { std::random_device {} () };
    Graph g;
    generate_random_graph(g, 10, 20, prng);

    for (auto v : make_iterator_range(vertices(g)))
        put(vertex_name, g, v, "vertex" + std::to_string(v));

#if 0
    // in case `Weight` is double
    auto gen_weight = [&, dist=std::uniform_real_distribution<Weight>(0,1)] () mutable -> Weight {
        return dist(prng);
    };
#else
    // in case `Weight` is std::string
    auto randchar = [&, dist=std::uniform_int_distribution<>('0','9')] () mutable -> char { return dist(prng); };

    auto gen_weight = [&] () {
        Weight tmp(3, ' ');
        std::generate(tmp.begin(), tmp.end(), randchar);
        return tmp;
    };
#endif

    for (auto e : make_iterator_range(edges(g)))
        put(edge_weight, g, e, gen_weight());

    return g;
}

输出随机生成的图形，例如:

Outputs the graph randomly generated, e.g.:

digraph G {
    vertex0->vertex5  [label=503];
    vertex0->vertex8  [label=653];
    vertex0->vertex8  [label=931];
    vertex1->vertex6  [label=022];
    vertex1->vertex8  [label=536];
    vertex1->vertex5  [label=400];
    vertex1->vertex4  [label=056];
    vertex3->vertex8  [label=555];
    vertex4->vertex7  [label=052];
    vertex4->vertex6  [label=542];
    vertex4->vertex3  [label=024];
    vertex5->vertex7  [label=595];
    vertex5->vertex8  [label=850];
    vertex7->vertex4  [label=464];
    vertex7->vertex9  [label=484];
    vertex8->vertex0  [label=274];
    vertex8->vertex1  [label=131];
    vertex8->vertex6  [label=529];
    vertex9->vertex1  [label=239];
    vertex9->vertex3  [label=362];
}

哪个呈现为

这篇关于提升dijkstra琴弦边缘的重量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！