Jak zdefiniować niestandardową odległość w Boost Dijkstra?

Question

Obecnie szukam dokumentacji Boost Dijkstra - http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/dijkstra_shortest_paths.html; moim celem jest zmodyfikowanie łączenia odległości w celu uzyskania "maksimum", zamiast "plusa" przy obliczaniu odległości. Dokument mówi:

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 

Jaka jest składnia w celu zdefiniowania takiej funkcji łączenia? Próbowałem grzebać przy std :: max, ale mój kompilator nie wydaje się być z niego zadowolony.

Answer 1

Prawdopodobnie konieczności jej argumenty są szablony to może zrobić rzeczy trochę trudne ...

Try (gdzie T jest typem swoimi odległościach)

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

i przekazać grzebień.

Answer 2

Idę na leniwym sposób i po prostu dać trochę kodu, który pokazuje jak to zrobić :)

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