Карта веса как функция в алгоритме Boost Graph Dijkstra

Я использую библиотеки Boost Graph, и мне нужно использовать карту весов, которая не является постоянной, а является функцией параметра K (т.е. стоимость ребра зависит от K). На практике, учитывая следующий код:

#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>

struct Edge {
        Edge(float weight_) : weight(weight_) {}
        float weight;
        float getWeight(int K)
        {
            return K*weight;
        }
};



int main(int, char**){
        typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, boost::no_property, Edge > graph_t;
        typedef boost::graph_traits < graph_t >::vertex_descriptor vertex_t;
        graph_t g;
        vertex_t a = boost::add_vertex(g);
        vertex_t b = boost::add_vertex(g);
        vertex_t c = boost::add_vertex(g);
        vertex_t d = boost::add_vertex(g);
        boost::add_edge(a, b, Edge(3), g);
        boost::add_edge(b, c, Edge(3), g);
        boost::add_edge(a, d, Edge(1), g);
        boost::add_edge(d, c, Edge(4), g);

        std::vector<vertex_t> preds(4);

        // Traditional dijsktra (sum)
        boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)));

        return 0;
}

Я хотел бы назвать алгоритм Дейкстры следующим образом:

boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::getWeight(2),g)));

Но ошибка следующая

не может вызывать функцию-член ‘float Edge::getWeight(int)’ без объекта

Кто-нибудь знает, как это решить?


c++ boost dijkstra boost-graph boost-property-map
person user1403546    schedule 13.10.2015    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Существует несколько разновидностей карт свойств. В частности, здесь можно использовать transform_value_property_map.

Простой подход С++ 03

Предполагая С++ 03, вы бы написали:

Жить на Coliru

#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/bind.hpp>

// ...

boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(
            boost::make_transform_value_property_map(
                boost::bind(&Edge::getWeight ,_1, 2), 
                boost::get(boost::edge_bundle, g))
        ));

Очиститель С++ 11

Жить на Coliru

auto wmap = make_transform_value_property_map([](Edge& e) { return e.getWeight(2); }, get(boost::edge_bundle, g));
boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(wmap));

Вы можете отказаться от включения boost/bind.hpp.

Бонус: удалите функцию-член getWeight()

Жить на Coliru

Вам это на самом деле не нужно. Вы можете написать актера Феникса на месте:

#include <boost/phoenix.hpp>
using boost::phoenix::arg_names::arg1;

auto wmap = make_transform_value_property_map(2 * (&arg1->*&Edge::weight), get(boost::edge_bundle, g));

Или снова используйте С++ 11:

Жить на Coliru

auto wmap = make_transform_value_property_map([](Edge& e) { return e.weight * 2; }, get(boost::edge_bundle, g));
person sehe    schedule 13.10.2015
comment
Добавлено не менее 4-х живых сэмплов на Колиру :) - person sehe; 13.10.2015
comment
Большое спасибо! Еще один вопрос: поскольку я не использую С++ 11 и хотел бы вызвать алгоритм Дейкстры параллельно (openMPI?) для трех/четырех значений K, какая реализация кода для вас самая быстрая? - person user1403546; 13.10.2015
comment
Кратчайший путь должен оставаться неизменным независимо от константы K. Предполагая, что граф является логически и побитовым константой, вы можете просто выполнять запросы параллельно. - person sehe; 13.10.2015