Re: [Boost-users] [BGL] Having a cost function as weight map

18 Dec 2009

      On Fri, 18 Dec 2009, Maxime van Noppen wrote:
...
Hi,
I can't find how to do this pretty basic thing : having a function
instead of a field to compute the cost of edges for various path finding
algorithms. I couldn't find the answer in the documentation and Google
was of no help. Did I miss something obvious ?
Example :
-------------------
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
struct my_edge
{
 double cost() const { return cost_ * 2; }
 double cost_;
};
struct my_node
{
};
int main()
{
 typedef boost::adjacency_list< boost::vecS, boost::vecS,
                                boost::directedS, my_node, my_edge >
         graph_t;
 typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;
graph_t graph;
vertex_t v /*=  ... */;
using boost::weight_map;
// Works :
 boost::dijkstra_shortest_paths(graph, v,
     weight_map(boost::get(&my_edge::cost_, graph)));
// Doesn't compile :
 //boost::dijkstra_shortest_paths(graph, v,
 //    weight_map(boost::get(&my_edge::cost, graph)));
}
-------------------
Thanks !
It looks like there is no property map that does what you want, although 
there should be.  Try something like this (not tested); it assumes that 
your functors are lightweight to copy, have a const operator()(), and do 
not have any internal state:

#include <boost/property_map/property_map.hpp>
#include <boost/utility.hpp>

template <typename Functor, typename Arg>
struct function_property_map {
   private:
   Functor f;

   public:
   explicit function_property_map(const Functor& f): f(f) {}

   friend value_type get(const function_property_map& pm, const Arg& x) {
     return pm.f(x);
   }
};

namespace boost {
   template <typename Functor, typename Arg>
   struct property_traits<function_property_map<Functor, Arg> > {
     typedef typename boost::result_of<Functor(Arg)>::type value_type;
     typedef value_type reference;
     typedef Arg key_type;
     typedef boost::readable_property_map_tag category;
   };
}

template <typename Arg, typename Functor>
function_property_map<Functor, Arg>
make_function_property_map(const Functor& f) {
   return function_property_map<Functor, Arg>(f);
}

The write a function object (get_weight, say) that takes an edge 
descriptor and returns your weight, make sure it has a member typedef 
called "result_type" that gives the result of operator()(), and use 
"make_function_property_map<edge_descriptor>(get_weight)" as the property 
map.  Please tell me if there are any problems, as I have not tested this.

-- Jeremiah Willcock