权重图作为Boost Graph Dijkstra算法的函数 [英] Weight map as function in Boost Graph Dijkstra algorithm

问题描述

我正在使用Boost Graph库，需要使用一个权重图，该权重图不是常数，而是参数K的函数(即边成本取决于K).实际上，给出以下代码:

I'm using Boost Graph Libraries and need to use a weightmap which is not constant, but which is a function of a parameter K (i.e. the edge costs depend on K). In practice, given the following code:

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

我想按以下方式调用Dijkstra算法:

I'd like to call Dijkstra algorithm as follows:

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

但是错误如下

在没有以下情况的情况下无法调用成员函数"float Edge :: getWeight(int)" 对象

cannot call member function ‘float Edge::getWeight(int)’ without object

有人知道如何解决吗?

推荐答案

有许多属性映射样式.特别是一个transform_value_property_map可以在这里使用.

There are a number of property map flavours. In particular one is the transform_value_property_map can be used here.

假设您要编写的是c ++ 03:

Assuming c++03 you'd write:

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

更清洁的C ++ 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包含.

在Coliru上直播

您实际上并不需要它.您可以就地编写Phoenix演员:

You don't actually need it. You could write a Phoenix actor in-place:

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

或再次使用c ++ 11:

Or use c++11 again:

在Coliru上直播

auto wmap = make_transform_value_property_map([](Edge& e) { return e.weight * 2; }, get(boost::edge_bundle, g));

这篇关于权重图作为Boost Graph Dijkstra算法的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！