gt.astar_search 'zero' and 'infinity' parameter type interpretation is wrong
Documentation (http://projects.skewed.de/graph-tool/doc/search_module.html#graph_tool.searc...) 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? -- 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 07/23/2013 08:38 PM, Guillaume Lemaître wrote:
Documentation (http://projects.skewed.de/graph-tool/doc/search_module.html#graph_tool.searc...) 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 -- Tiago de Paula Peixoto <tiago@skewed.de>
test_graph_tool.py <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025093/test_graph_tool.py> 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. -- 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 07/24/2013 10:12 PM, Guillaume Lemaître wrote:
test_graph_tool.py <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025093/test_graph_tool.py>
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.
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
My scenario was a Python 2.x one. Your patch on it, and the fix on your code are the right ones ;) -- 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.
participants (2)
-
Guillaume Lemaître -
Tiago de Paula Peixoto