python3 TypeError: '<' not supported error when try to implement A* algo use python heapq

Question

I am trying to implement A* algorithm using pri_que by leveraging python library heapq. In general, all the state of will be stored as a Node instance

class Node:
   def __init__(self, state, parent, action, depth):
        self.path_cost = 0
        self.state = state
        self.parent = parent
        self.action = action
        self.depth = depth

The code is too long to paste here, but the error locates in the following block.

    def astar_insert(self, node):
        hq.heappush(self.pri_que, (node.path_cost, node))
        self.visited_pri.add(str(node.state))
    
 
    def astar_pop(self):
        
        node = hq.heappop(self.pri_que)[1] # <-------------------- this line

        self.visited_pri.discard(str(node.state))
        return node

The full error is:

TypeError: '<' not supported between instances of 'Node' and 'Node'

I am very confused. I try to run the code and print the solution. It seems like the code works for a well before failing.

Can you provide the full definition of Node? How do you expect two Node instances to be compared? — Brian61354270
– Brian61354270, Commented Sep 10, 2023 at 19:37
@Brian61354270 Just revise the post. The Node is defined above. I honestly didn't make any comparison between two nodes. Which is why I am so confused. — Rieder
– Rieder, Commented Sep 10, 2023 at 19:40
For example, in my code, I only use node.state without making any operations such as <, ==, or > — Rieder
– Rieder, Commented Sep 10, 2023 at 19:41
You make comparisons between Nodes by putting them into a heap queue. That's how the heap algorithm works. If you can't compare Nodes, they can't be used in a heap — Brian61354270
– Brian61354270, Commented Sep 10, 2023 at 19:44
@Brian61354270: They can be used in a heap if you guarantee that the comparison of the tuples will never fall back to comparing the Node instances. But comparing on costs alone is highly unlikely to achieve that (and clearly didn't, in the OP's case). — ShadowRanger
– ShadowRanger, Commented Sep 10, 2023 at 19:45

Dharman · Accepted Answer · 2023-10-28 20:25:38Z

2

The crux of your problem is:

Your path_costs aren't unique (meaning entries in the heap must fall back to comparing the Nodes themselves), and
Your Node class doesn't define a comparison for less-than (causing the TypeError for incomparable types).

There are two possible solutions:

Push stuff on the heap with a guaranteed unique comparable value between the cost and the node itself. A good source of such guaranteed unique comparable values would be an instance of itertools.count(). Once you've made one, you'd call hq.heappush(self.pri_que, (node.path_cost, next(counter), node)) for the insertion, ensuring the node instance would never be compared.
Make your Nodes comparable by defining __lt__ on the class with some meaningful comparison. You'd also want to define __eq__ and use the @functools.total_ordering decorator to ensure it's comparable for all purposes (not just the __lt__ that Python uses for ordering comparisons in the built-ins, but for other purposes where > or <= or >= are used).

edited Oct 28, 2023 at 20:25

Dharman♦

33.9k27 gold badges105 silver badges157 bronze badges

answered Sep 10, 2023 at 19:41

ShadowRanger

158k12 gold badges221 silver badges314 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Rieder Over a year ago

I find the issue. Turns out you guys are right. ```__lt__`` solve the problem

Rieder Over a year ago

I think what heappush does is if the first element in the tuple is the same, it will compare the second element

ShadowRanger Over a year ago

@Rieder: It's not heappush doing it at all. That's how all tuple comparisons work. It's called lexicographic ordering; the heap utilities are type-agnostic, they just ask whether the "instance" (in this case, a 2-tuple) is less than the other instance. tuple itself is checking left-to-right until it finds an unequal element, then basing the overall result on the result of comparing the unequal elements. That's why solution #1 works; even when costs are tied, by ensuring the second comparison is always unequal, the tuple comparison never compares the (non-comparable) third elements.

Collectives™ on Stack Overflow

python3 TypeError: '<' not supported error when try to implement A* algo use python heapq

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related