Come definire una distanza personalizzata in Boost Dijkstra?

Question

Attualmente sto esaminando la documentazione di Boost Dijkstra - http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/dijkstra_shortest_paths.html; il mio obiettivo è modificare la distanza combinando per ottenere un "massimo" invece di un "più" quando calcolando le mie distanze. Il documento dice questo:

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 

Qual è la sintassi per definire tale funzione Combina? Ho cercato di armeggiare con std :: max, ma il mio compilatore non sembra essere soddisfatto.

Answer 1

Probabilmente avendo i suoi argomenti siano modelli è potrebbe rendere le cose un po 'difficile ...

Try (dove T è il tipo di distanze)

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

e passare pettine.

Answer 2

Vado a fare il modo pigro e solo dare un po 'di codice che mostra come farlo :)

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