How do I define a custom distance in Boost Dijkstr

问题:

I'm currently looking at the documentation of Boost Dijkstra - http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/dijkstra_shortest_paths.html; my objective is to modify the distance combining to get a "max" instead of a "plus" when computing my distances. The doc says this:

IN: distance_combine(CombineFunction cmb)
This function is used to combine distances to compute the distance of a path. The
CombineFunction type must be a model of Binary Function. The first argument typ
of the binary function must match the value type of the DistanceMap property map
and the second argument type must match the value type of the WeightMap property
map. The result type must be the same type as the distance value type.
Default: closed_plus<D> with D=typename property_traits<DistanceMap>::value_type

What's the syntax to define such a Combine function? I've tried fumbling around with std::max, but my compiler doesn't seem to be happy with it.

回答1:

Probably having its arguments be templates is might make things a bit difficult...

Try (where T is the type of your distances)

T comb(T& a, T& b) { return std::max(a, b); }

and pass comb.

回答2:

I'm going for the lazy way and just give some code that shows how to do it :)

#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>

struct Edge {
        Edge(float weight_) : weight(weight_) {}
        float weight;
};

// simple function
float combine(float a, float b){
        return std::max(a, b);
}

// functor
struct Combine{
        // Some internal state

        float operator()(float a, float b) const {
                return std::max(a, b);
        }
};

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)));
        assert(preds[c] == d);
        assert(preds[d] == a);

        // Dijkstra with custom combine as a function
        boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)).distance_combine(&combine));
        assert(preds[c] == b);
        assert(preds[b] == a);

        // Dijkstra with custom combine as a functior
        boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)).distance_combine(Combine()));
        // Dijkstra with custom combine as a lambda
        boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)).distance_combine([](float a, float b){return std::max(a,b);}));

        return 0;
}