astar_search and weights as Python objects

graph-tool
#1

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. :frowning: 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.search.astar_search)
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

#2

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?

#3

Hi Guillaume,

#4

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/file/n3880014/exemple.py
exemple.py

#5

Hi Gillaume,

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

exemple.py (4.39 KB)

#6

Thanks for your prompt fixup, it works perfectly well for me too!

Regards,

        Guillaume

#7

Great. Thanks for pointing out the bug and providing a self-contained
example! It helps a lot when this is done.

Cheers,
Tiago