Как определить пользовательское расстояние в Boost Dijkstra?
В настоящее время я смотрю на документацию Boost Dijkstra — http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/dijkstra_shortest_paths.html; моя цель состоит в том, чтобы изменить объединение расстояний, чтобы получить «максимум» вместо «плюс» при вычислении моих расстояний. Док говорит это:
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
Какой синтаксис для определения такой функции Combine? Я пробовал возиться с std :: max, но мой компилятор, похоже, не доволен этим.
Решение
Вероятно, наличие аргументов в качестве шаблонов может усложнить ситуацию …
Попробуйте (где T — тип ваших расстояний)
T comb(T& a, T& b) { return std::max(a, b); }
и передать гребень
Другие решения
Я иду ленивым путем и просто дать код, который показывает, как это сделать 🙂
#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;
}