A* (astar) algorithms depend on nodes being orderable. (migrated from Trac #562)

[networkx-trac]

Original ticket https://networkx.lanl.gov/trac/ticket/562 Reported 2011-05-30 by unknown, assigned to @hagberg.

The A* algorithms in networkx.algorithms.shortest_paths.astar raise an unhandled exception when the nodes in the graph are not orderable (i.e. do no define node_1.le(node_2).) This is a bug, because orderability is not in general a requirement of NetworkX nodes.

The algorithms use a heap from the python heapq library as a priority queue for the sake of speed. This priority queue is the open list, used to hold all nodes that have been reached but not explored. Nodes are stored in this queue in the format (priority, node, cost to reach, parent); where priority is n + h; cost to reach is n; n is the cost to reach the node from the start along a given path; and h is the value of the heuristic estimating the distance from that node to the end. (Clarification: I say "along a given path" because old entries are not removed from the open list when better paths are found to reach them, the priority queue just ensures that they are ignored.)

The underlying heap regularly compares its elements, which are in this case the above 4-tuples. If the priorities (n + h) for two nodes are ever the same, the heap will attempt to compare the nodes themselves. If the nodes cannot be compared, this results in an unhandled TypeError exception and crashes the program.

I talked about this with Aric on the mailing list (http://groups.google.com/group/networkx-discuss/browse_thread/thread/a47b2df75d23944d) and he gave me this useful link (http://docs.python.org/library/heapq.html#priority-queue-implementation-notes). Thanks Aric.

I suggest instead of storing the 4-tuple, we store a 5-tuple in the format (priority, hash(node), node, cost to reach, parent). No two nodes in the graph can have the same hash, else they would already have collided. The addition of this extra element in the tuple will break any ties in priority, without relying on the nodes being directly comparable.

This solution is slightly cleaner than using a counter as suggested in the heapq doc.s.

This bug is present in 1.5rc1, and in the latest version of astar.py from the mercurial repo. I built the attached diff against that latest file; hopefully its correctly formatted--I made it with git on windows. I attached a file containing a single unittest demonstrating the failure.

[networkx-trac]

Attachment in Trac by unknown, 2011-05-29: networkx_astar_node_orderability_dependency_testcase.py

[networkx-trac]

Attachment in Trac by unknown, 2011-05-29: networkx_astar_node_orderability_dependency_testcase.2.py

[networkx-trac]

Attachment in Trac by unknown, 2011-05-29: networkx_astar_node_orderablity_dependency_fix.diff

[networkx-trac]

Comment in Trac by Aric Hagberg <aric.hagberg, 2011-05-30

In [813e436c2c058e173acc3ba5d5af908824cfe1c5/networkx]: '''

!CommitTicketReference repository="networkx" revision="813e436c2c058e173acc3ba5d5af908824cfe1c5"

Handle unorderable nodes in A* algorithm. Fixes #562 '''

[networkx-trac]

Comment in Trac by @hagberg, 2011-05-30