Priority Queue with Tuples and Dicts

Question

Problem Statement

Currently I am implementing an A* search algorithm (heavily modified for a particular problem) in Python. As a component of the problem, I need a fast access to the smallest heuristic value in LIFO order. Python's priority queue looked best. My data structure was already a list of dictionaries with parent relations, so it'd be nice to be able to sort those. However, I seem to be having difficulties doing so. For example, I have an example newly dictionary:

queue = PriorityQueue() # Could be instantiated based on an existing list of dicts
exampleDict = {"x": 10, "y": 20, "f": 123, "parent":{}}

I would like to be able to insert this dictionary into the priority queue via a tuple or some like-form

queue.put((exampleDict["f"], exampleDict))

Please note that I cannot try an external library, so I'm looking for a more native-to-py3 solution.

Whats Happening

I've tried every solution that was obvious to me. Reading the docs, I found that Python allows a tuple in which the second item in the tuple was the dictionary, and the first was the priority:

parent = {'x': 0, 'y': 0, 'parent': False, 'f': 0, 'g': 50, 'wallPassed': 0}
something = (1, {'h': 9, 'x': 0, 'y': 1, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 0})
somethingElse = (1, {'h': 9, 'x': 1, 'y': 0, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 1})
test = PriorityQueue()
test.put(something)
test.put(somethingElse)

It works when inserting one value, but the minute I insert another it fails

Traceback (most recent call last):
  File "test.py", line 8, in <module>
    test.put(somethingElse)
  File "C:\Users\champloo11\AppData\Local\Programs\Python\Python35-32\lib\queue.py", line 143, in put
    self._put(item)
  File "C:\Users\champloo11\AppData\Local\Programs\Python\Python35-32\lib\queue.py", line 227, in _put
    heappush(self.queue, item)
TypeError: unorderable types: dict() < dict()

Is there anything that can be done about this? There doesn't seem to bemuch in the way of documentation regarding the problem, or solving it without frozendict.

Solution 1

The problem is that dictionaries are unorderable types in Python. That is, if you try to run something like:

>>> {'alpha': 1} < {'beta': 2}
----> 1 {'alpha': 1} < {'beta': 2}

TypeError: unorderable types: dict() < dict()

you'll get a TypeError. The trick you're trying to employ is to wrap the dictionary up into a tuple whose first element is orderable -- something like a number. Then we can compare them:

>>> (1, {'alpha': 1}) < (2, {'beta': 2})
True

Now it pays to look at how Python compares tuples. First, Python compares the first entries of each tuple. In this case, 1 < 2, and Python returns True. But if the first entries are not ordered -- say they are the same -- Python then goes to comparing the second entries. For instance

>>> (1, 42) < (2, 7)
True
>>> (1, 42) < (1, 88)  # 42 < 88
True
>>> (1, 42) < (1, 7)   # 42 >= 7
False

So what happens in your example above is that you have two tuples with the same first entry, and the second entry of each is a dictionary. Hence Python compares the first two entries, can't determine an order from them, and then attempts to compare the second entries, which are dictionaries and can't be ordered. In an example,

>>> (1, {'alpha': 1}) < (2, {'beta': 2})
True

works just fine, as we saw above. But changing the first entry of the tuple on the right gives an error:

>>> (1, {'alpha': 1}) < (1, {'beta': 2})
----> 1 (1, {'alpha': 1}) < (1, {'beta': 2})
TypeError: unorderable types: dict() < dict()

---

So what is the right solution? If you have a way of assigning a unique priority to each dictionary, then the tuple approach will work. But the first entry of each tuple must be unique! Otherwise Python will resort to comparing the second entries, which are dictionaries, and you'll have the same issue again.

If that isn't possible or desirable, then we have to give Python a way of comparing these two dictionaries. One way of doing this is to create a PriorityEntry class and define its __lt__ method. To create an instance of this class, you give a priority, which can be ordered, and data, which need not be orderable. Then __lt__ orders two instances of the class by their priorities only, and not by their data. That is:

class PriorityEntry(object):

    def __init__(self, priority, data):
        self.data = data
        self.priority = priority

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

and so

>>> PriorityEntry(1, {'alpha': 1}) < PriorityEntry(1, {'beta': 2})
False
>>> PriorityEntry(1, {'alpha': 1}) < PriorityEntry(2, {'beta': 2})
True

or, using your data:

parent = {'x': 0, 'y': 0, 'parent': False, 'f': 0, 'g': 50, 'wallPassed': 0}
something = PriorityEntry(1, {'h': 9, 'x': 0, 'y': 1, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 0})
somethingElse = PriorityEntry(1, {'h': 9, 'x': 1, 'y': 0, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 1})
test = PriorityQueue()
test.put(something)
test.put(somethingElse)

which will now run without raising the error.

Solution 2

A common solution to unorderable data in a priority queue is to add an extra value to the tuple which will never be equal in two different entries. It will break the "tie" between two items with identical priorities without the data needing to be orderable. A steadily-increasing integer is an easy way to do it:

import heapq
import itertools

unorderable_data = {"foo": "bar"}

heap = []
counter = itertools.count()

entry1 = (2, next(counter), unorderable_data)
entry2 = (1, next(counter), unorderable_data)
entry3 = (2, next(counter), unorderable_data)

heapq.heappush(heap, entry1)
heapq.heappush(heap, entry2)
heapq.heappush(heap, entry3)

priority, tie_breaker, data = heapq.heappop(heap)

print(priority, data) # prints 1, {"foo": "bar"}

In addition to showing how to add a tie-breaker item to the tuples, I'm also demonstrating here the use of the heapq module for implementing a priority queue in a list, rather creating an instance of the queue.PriorityQueue class. The whole queue module is designed to make serialized communication possible in multithreaded programs, and as such its classes will all have a bunch of lock-related overhead you don't need if you're creating a single threaded application. The PriorityQueue class uses the heapq module under the covers, which I suggest using directly instead.

Solution 3

As things stand, you're trying to compare tuples, and this indirectly tries to compare dicts (which are incomparable). Bypassing this is easy. Say you write the following class

class use_only_first(object):
    def __init__(self, first, second):
        self._first, self._second = first, second

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

and use instances of this class in heapq or queue. It will ignore the second parameter. Note that this only uses modules from the standard library.

P.S. You should be using queue.PriorityQueue if you're interested in the concurrency aspects. Otherwise heapq will be more efficient.