astar_search and weights as Python objects
Hi, I'm trying to use the astar_search algorithm for my own problem, and I get the following error: ====> File "/usr/lib64/python2.7/site-packages/graph_tool/search/__init__.py", line 125, in wrap ret = func(*args, **kwargs) File "/usr/lib64/python2.7/site-packages/graph_tool/search/__init__.py", line 1528, in astar_search compare, combine, zero, infinity, h) RuntimeError: No static implementation was found for the desired routine. This is a graph_tool bug. :-( Please follow but report instructions at http://graph-tool.skewed.de. What follows is debug information. Graph view: boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::property<boost::edge_index_t, unsigned long, boost::no_property>, boost::no_property, boost::listS>* Action: boost::_bi::bind_t<void, do_astar_search, boost::_bi::list9<boost::arg<1>, boost::_bi::value<unsigned long>, boost::arg<2>, boost::_bi::value<std::pair<boost::any, boost::any> >, boost::arg<3>, boost::_bi::value<graph_tool::AStarVisitorWrapper>, boost::_bi::value<std::pair<graph_tool::AStarCmp, graph_tool::AStarCmb>
, boost::_bi::value<std::pair<boost::python::api::object, boost::python::api::object> >, boost::_bi::value<std::pair<boost::python::api::object, boost::python::api::object> > > >
Arg 1: boost::checked_vector_property_map<boost::python::api::object, boost::vec_adj_list_vertex_id_map<boost��perty, unsigned long> > Arg 2: boost::checked_vector_property_map<boost::python::api::object, boost::adj_list_edge_property_map<boost::bidirectional_tag, unsigned long, unsigned long&, unsigned long, boost::property<boost::edge_index_t, unsigned long, boost::no_property>, boost::edge_index_t> > <==== Please note this is not always the same error message. How did I got this ? I' ve defined a own cost type for edge weights and distances: class Cost(object): nb_turns = 0 distance = 0 def __add__(self, other): """so that astar_search.combine may work""" ... def __cmp__(self, other): """so that astar_search.compare may work""" ... def __hash__(self, other): """so that Cost equality is done by value""" ... This could have been a tuple, but I thought it was more elegant to define a named type after it (even if less efficient?) I also defined an INFINITE_COST:
INFINITE_COST = Cost() INFINITE_COST.nb_turns = float("inf") INFINITE_COST.distance = float("inf")
I inspired myself from the HammingVisitor example (http://projects.skewed.de/graph-tool/doc/search_module.html#graph_tool.searc...) to build up the graph during its exploration for my own problem. Compared to this example, I thought that I have to call the astar_search procedure with zero and infinity attributes defined, respectively with zero = Cost() infinity = INFINITE_COST I *suppose* this could be the main reason for such an error message to rise up. Alternatively, the HammingVisitor example works perfectly well (after replacing 'array' by 'list') on my computer. How could I tackle down the real issue? Maybe using classes for weights instead of predefined types is not recommended? Regards, Guillaume -- Si les dauphins étaient si malins, ils ne vivraient pas dans des igloos.
Furthermore, if I tweak the HammingVisitor example in order to use my own Cost class for weigth, dist and cost property maps, I get a Runtime Error. This tends to indicate that using Python objects for distances is a bad idea. But then, what are the purpose of compare, combine, zero and infinity astar_search arguments? -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
Hi Guillaume, On 04/02/2012 11:01 PM, Guillaume Lemaître wrote:
Furthermore, if I tweak the HammingVisitor example in order to use my own Cost class for weigth, dist and cost property maps, I get a Runtime Error. This tends to indicate that using Python objects for distances is a bad idea. But then, what are the purpose of compare, combine, zero and infinity astar_search arguments?
This is indeed a bug. It should be perfectly valid to use arbitrary python types for distance and cost properties. I'll provide a fix for this soon. Best regards, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Hi Tiago, Thanks for your prompt reply. Should I open a ticket? I attach here the HammingVisitor example modified to use my own Cost class. Regards, Guillaume http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... exemple.py -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
Hi Gillaume, On 04/03/2012 07:22 AM, Guillaume Lemaître wrote:
Thanks for your prompt reply. Should I open a ticket? I attach here the HammingVisitor example modified to use my own Cost class.
I have fixed this problem in the development version available in the git repository. Attached I'm sending you a slightly modified version of your example (I added an initialization of the distance of the source vertex to Cost(), otherwise it would have been None, and imported the copy module), which works for me without a problem. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Thanks for your prompt fixup, it works perfectly well for me too! Regards, Guillaume -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 04/04/2012 11:30 PM, Guillaume Lemaître wrote:
Thanks for your prompt fixup, it works perfectly well for me too!
Great. Thanks for pointing out the bug and providing a self-contained example! It helps a lot when this is done. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
Guillaume Lemaître -
Tiago de Paula Peixoto