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

Subject: Re: [Boost-users] [BGL] Having a cost function as weight map
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-12-18 12:21:11

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