问题描述
是否可以使用字符串值代替双精度属性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 propertiestypedef 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))));
错误:
推荐答案
是的,您可以拥有字符串属性.
Yes you can have a string property.
否,dijkstra需要
No, dijkstra requires
因此,权重必须为数字.当然,如果您可以对属性类型实现算术运算和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:
#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琴弦边缘的重量的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!