gt.astar_search 'zero' and 'infinity' parameter type interpretation is wrong

graph-tool
1

Documentation
(http://projects.skewed.de/graph-tool/doc/search_module.html#graph_tool.search.astar_search)
says that both 'zero' and 'infinity' parameters type should be int or float.
To me this is wrong, their type should be the one used to represent costs.

A confirmation of that is that I used to work with 2.2.17 version. While
moving to 2.2.24, I encounter a bug that has been introduced in 2.2.18
version (commit 016d8244a24b3dba812ce2bb305e2e1f09e85154)

In my application, 'cost_map' and 'dist_map' are both created with

   graph.new_vertex_property("object")

'zero' and 'infinity' are two specific Cost() instances, which is a type
with a __init__ function that don't take any other argument than the regular
'self' one). The call to astart_search is like this:

  gt.astar_search (g=MyGraph, source=MyGraph.vertex(0), weight =
MyGraph.new_edge_property("object"),
                          visitor=MyVisitor, dist_map =
MyGraph.new_vertex_property("object"),
                          cost_map = MyGraph.new_vertex_property("object"),
pred_map = MyGraph.new_vertex_property("int"),
                         zero = CostZero, infinity = CostInfinity, implicit
= true)

While it used to work with 2.2.17, now my application crashes in
search/__init__.py, at the beginning of the astart_function, more precisely
the instruction in the following "try" section:

    try:
        zero = _python_type(dist_map.value_type())(zero)
    except OverflowError:
        zero = (weight.a.max() + 1) * g.num_vertices()
        zero = _python_type(dist_map.value_type())(zero)

I don't get why we try here to convert 'zero' (and right after this,
'infinity') whereas it already has the correct type. What did I miss?

2

Documentation
(http://projects.skewed.de/graph-tool/doc/search_module.html#graph_tool.search.astar_search)
says that both 'zero' and 'infinity' parameters type should be int or float.
To me this is wrong, their type should be the one used to represent costs.

You are right... I'll change this.

A confirmation of that is that I used to work with 2.2.17 version. While
moving to 2.2.24, I encounter a bug that has been introduced in 2.2.18
version (commit 016d8244a24b3dba812ce2bb305e2e1f09e85154)

In my application, 'cost_map' and 'dist_map' are both created with

   graph.new_vertex_property("object")

'zero' and 'infinity' are two specific Cost() instances, which is a type
with a __init__ function that don't take any other argument than the regular
'self' one). The call to astart_search is like this:

  gt.astar_search (g=MyGraph, source=MyGraph.vertex(0), weight =
MyGraph.new_edge_property("object"),
                          visitor=MyVisitor, dist_map =
MyGraph.new_vertex_property("object"),
                          cost_map = MyGraph.new_vertex_property("object"),
pred_map = MyGraph.new_vertex_property("int"),
                         zero = CostZero, infinity = CostInfinity, implicit
= true)

While it used to work with 2.2.17, now my application crashes in
search/__init__.py, at the beginning of the astart_function, more precisely
the instruction in the following "try" section:

    try:
        zero = _python_type(dist_map.value_type())(zero)
    except OverflowError:
        zero = (weight.a.max() + 1) * g.num_vertices()
        zero = _python_type(dist_map.value_type())(zero)

I don't get why we try here to convert 'zero' (and right after this,
'infinity') whereas it already has the correct type. What did I miss?

I think I see what the problem is, but I don't see why it should
crash. Could you send a minimal test case so I can fix this more
easily?

Cheers,
Tiago

3

test_graph_tool.py
<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025093/test_graph_tool.py&gt;

I think this should show you the discrepancy. I currently have no other
version than 2.2.17 available, but I am pretty sure this example is
demonstrative enough.

4

Thanks for the example. I've fixed this in the git version (commit
d2b60b9985).

Note that I had to change your Distance2D class to contain the less than
operator:

     def __lt__(self, other):
        return self.euclidian_distance() < other.euclidian_distance()

The default comparison function of astar_search() is 'a < b'. Optionally
you could have overridden the comparison as well. The output I got was:

    Minimal distance : 3.41 meters
    (2, 2) <- (2, 1) <- (1, 1) <- (0, 0)

Which I assume is correct.

Cheers,
Tiago

5

My scenario was a Python 2.x one. Your patch on it, and the fix on your code
are the right ones :wink: