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