Boost dijkstra string edge weight

Question

можно использовать строковое значение вместо двойных свойств typedef adjacency_list < vecS, vecS, directedS, property<vertex_name_t, string>, property < edge_weight_t, string> > Graph; Моя цель - использовать алгоритм dijkstra. PS: Я уже пытался заменить двойную строку, и она генерирует ошибку в алгоритме.

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

Ошибка:

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

Answer 1

Да, вы можете иметь свойство строки.

Нет, Дейкстра требует

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

Таким образом, вес должен быть цифровым. Конечно, если вы можете реализовать арифметические операции и std::numeric_limit<> для вашего типа собственности, это может быть хорошо (но вам действительно нужно почесать голову, прежде чем делать это).

ОБНОВЛЕНИЕ _Вообще-то, эта документация упрощает бит, и вы можете фактически переопределить нуль, сравнение и комбинирование для вашего типа веса. См. linked sample в комментариях (HT @cv_and_he) _

Итак, я ненавижу быть тем парнем, но: почему.

Поскольку весы - это суммы в любом устройстве, так или иначе, какая цель хранит их как строки? Возможно, у вас есть другой вопрос, который мешает вам правильно хранить весы?

---

Тем не менее, вот так:

Использование transform_value_property_map вы можете преобразовать строки в парном разряде на лету:

Live On 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; 
} 

Выходы граф случайно сгенерированный, например .:

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

Который визуализируется как