2012-12-16 78 views
6

我正在查看Boost Dijkstra的文檔 - http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/dijkstra_shortest_paths.html;我的目標是在計算距離時修改距離組合以獲得「最大值」而不是「加號」。該文檔說:如何在Boost Dijkstra中定義自定義距離?

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來摸索,但我的編譯器似乎並不滿意它。

回答

3

也許有它的參數是模板是可能使事情變得有點困難......

嘗試(其中T是你的距離的類型)

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

,並通過梳理。

+1

事實上,它的工作有更多的摸索一點。我定義了 'template T comb(T&a,T&b){return std :: max(a,b); }',並在我的Dijkstra中通過梳理。謝謝! – Balise

4

我要爲偷懶的方法,只是給一些代碼,演示瞭如何做到這一點:)

#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; 
} 
相關問題