[BGL] Having a cost function as weight map
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 ! -- Maxime
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
Jeremiah Willcock wrote:
Please tell me if there are any problems, as I have not tested this.
It seems to work. I had to do a little fix to your code though. In the function_property_map you use 'value_type' which isn't defined and which is, I believe : typedef typename boost::property_traits< function_property_map<Functor, Arg> >::value_type value_type; I also changed the functor type from 'Functor' to 'const Functor&'. It seems to work. What was the rationale for copying it ? My functor needs to have a pointer/reference to the graph to be able to get the my_edge object from the edge_descriptor passed to the operator(). Thanks a lot! -- Maxime
On Fri, 18 Dec 2009, Maxime van Noppen wrote:
Jeremiah Willcock wrote:
Please tell me if there are any problems, as I have not tested this.
It seems to work. I had to do a little fix to your code though. In the function_property_map you use 'value_type' which isn't defined and which is, I believe :
typedef typename boost::property_traits< function_property_map<Functor, Arg> >::value_type value_type;
OK. It actually should be "typename boost::result_of<Functor(Arg)>::type" like what is in the specialization of property_traits.
I also changed the functor type from 'Functor' to 'const Functor&'. It seems to work. What was the rationale for copying it ?
In case your operator()() in the functor is non-const (even though I said I was assuming it was const); switching to a reference is fine.
My functor needs to have a pointer/reference to the graph to be able to get the my_edge object from the edge_descriptor passed to the operator().
OK. Did it work otherwise? -- Jeremiah Willcock
Jeremiah Willcock wrote:
OK. It actually should be "typename boost::result_of<Functor(Arg)>::type" like what is in the specialization of property_traits.
Ok fixed it.
In case your operator()() in the functor is non-const (even though I said I was assuming it was const); switching to a reference is fine.
And to a const reference ? My operator() is const.
OK. Did it work otherwise?
I didn't test it on a real world test case yet but I added a std::cout in my functor's operator() and it is called, so I'd say yes. -- Maxime
On Fri, 18 Dec 2009, Maxime van Noppen wrote:
Jeremiah Willcock wrote:
OK. It actually should be "typename boost::result_of<Functor(Arg)>::type" like what is in the specialization of property_traits.
Ok fixed it.
In case your operator()() in the functor is non-const (even though I said I was assuming it was const); switching to a reference is fine.
And to a const reference ? My operator() is const.
That's what I meant.
OK. Did it work otherwise?
I didn't test it on a real world test case yet but I added a std::cout in my functor's operator() and it is called, so I'd say yes.
OK. I just wanted to make sure there weren't any other obvious errors in the code. -- Jeremiah Willcock
I'd like to add, as a future reference, that this approach works well when the bundled property is a pointer. An example could be when you have many graphs with the same underlying vertex set and different edges, so you might want to use pointers to VertexProperty objects as bundled properties. In particular, VertexProperty could contain a field to be used as the vertex index. See, for example http://pastebin.com/6zpwCb4X for such an object (in the example we don't use pointers, though). In this case we can still use algorithms such as r_c_shortest_paths that expect an index map by adding value_type operator[](const Arg& arg) const { return f(arg); } to function_property_map as posted by Jeremiah and edited by Maxime. -- View this message in context: http://boost.2283326.n4.nabble.com/BGL-Having-a-cost-function-as-weight-map-... Sent from the Boost - Users mailing list archive at Nabble.com.
On Thu, 5 Sep 2013, potato_research wrote:
I'd like to add, as a future reference, that this approach works well when the bundled property is a pointer. An example could be when you have many graphs with the same underlying vertex set and different edges, so you might want to use pointers to VertexProperty objects as bundled properties.
In particular, VertexProperty could contain a field to be used as the vertex index. See, for example http://pastebin.com/6zpwCb4X for such an object (in the example we don't use pointers, though). In this case we can still use algorithms such as r_c_shortest_paths that expect an index map by adding
value_type operator[](const Arg& arg) const { return f(arg); }
to function_property_map as posted by Jeremiah and edited by Maxime.
Is that something that should be changed in Boost itself? -- Jeremiah Willcock
It just wanted to be a note for someone who, like me, will stumble upon this thread with the same problem. Nothing to change in Boost! :) -- View this message in context: http://boost.2283326.n4.nabble.com/BGL-Having-a-cost-function-as-weight-map-... Sent from the Boost - Users mailing list archive at Nabble.com.
participants (4)
-
Jeremiah Willcock -
Jeremiah Willcock -
Maxime van Noppen -
potato_research