Python: Heapify a list of tuples (Dijkstra's Algo)

Question

Here is my code for Dijkstra's Algorithm. I have declared a "Vertex" class and a "Graph" class. I am using heapq module and heapifying the list "unvisitedQueue" of tuples. But even then an error shows up saying " TypeError: '<' not supported between instances of 'Vertex' and 'Vertex' " even when "v.getDistance()" returns either 0 or float('inf').

import heapq

class Vertex:
    def __init__(self, node):
        self.id = node
        self.adjacent = {}
        self.previous = None
        self.distance = float('inf')
    
    def addNeighbor(self, neighbor, weight = 0):
        self.adjacent[neighbor] = weight
    
    def getConnections(self):
        return self.adjacent.keys()
    
    def getVertex_ID(self):
        return self.id
    
    def getWeight(self, neighbor):
        return self.adjacent[neighbor]

    def setDistance(self, dist):
        self.distance = dist

    def getDistance(self):
        return self.distance

    def setPrevious(self, prev):
        self.previous = prev

    def __str__(self):
        return str(self.id) + "adjacent : " + str([x.id for x in self.adjacent])
    
class Graph:
    def __init__(self):
        self.vertDictionary = {}
        self.numVertices = 0
    
    def __iter__(self):
        return iter(self.vertDictionary.values())
    
    def addVertex(self, node):
        self.numVertices += 1
        newVertex = Vertex(node)
        self.vertDictionary[node] = newVertex
        return newVertex
    
    def getVertex(self, node):
        if node in self.vertDictionary:
            return self.vertDictionary[node]
        else:
            return None
    
    def addEdge(self, frm, to, cost = 0):
        if frm not in self.vertDictionary:
            self.addVertex(frm)
        if to not in self.vertDictionary:
            self.addVertex(to)
        self.vertDictionary[frm].addNeighbor(self.vertDictionary[to], cost)
        
        self.vertDictionary[to].addNeighbor(self.vertDictionary[frm], cost)
    
    def getVertices(self):
        return self.vertDictionary.keys()
    
    def setPrevious(self, current):
        self.previous = current
    
    def getPrevious(self):
        return self.previous
    
    def getEdges(self):
        edges = []
        for v in G:
            for w in v.getConnections():
                v_id = v.getVertex_ID()
                w_id = w.getVertex_ID()
                edges.append((v_id, w_id, v.getWeight(w)))
        return edges
def Dijkstra(G, s):
    source = G.getVertex(s)
    source.setDistance(0)
    visited = {}
    unvisitedQueue = [(v.getDistance(), v) for v in G]
    heapq.heapify(unvisitedQueue)
    while len(unvisitedQueue):
        uv = heapq.heappop(unvisitedQueue)
        currVert = uv[1]
        visited[currVert] = True
        for nbr in currVert.getConnections():
            if currVert.getDistance() + currVert.getWeight(nbr) < nbr.getDistance():
                nbr.setDistance(currVert.getDistance() + currVert.getWeight(nbr))
                print("Updated: Current = %s Neighbour = %s New Distance = %s" %(currVert.getVertex_ID(), nbr.getVertex_ID(), nbr.getDistance()))
            else:
                print("Not Updated: Current = %s Neighbour = %s Distance = %s" %(currVert.getVertex_ID(), nbr.getVertex_ID(), nbr.getDistance()))
        while len(unvisitedQueue):
            heapq.heappop(unvisitedQueue)
        unvisitedQueue = [(v.getDistance(), v) for v in G if v not in visited]
        heapq.heapify(unvisitedQueue)
    for v in G:
        print(source.getVertex_ID(), "to", v.getVertex_ID(), "-->", v.getDistance())

ERROR -->

Traceback (most recent call last):
  File "d:\Python\Final 450\Graph\Dijkstra's_Algo.py", line 124, in <module>
    print(Dijkstra(G, "a"))
  File "d:\Python\Final 450\Graph\Dijkstra's_Algo.py", line 86, in Dijkstra 
    heapq.heapify(unvisitedQueue)
TypeError: '<' not supported between instances of 'Vertex' and 'Vertex'

Answer 1

The error is happening because tuples are compared lexicographically. If two distances are the same, the comparison moves on to the Vertex objects themselves.

Two solutions readily come to mind. The first is simply to add a unique index to the tuple before the Vertex but after the distance. This is easy, and would work even if you didn't have access to the Vertex class:

unvisitedQueue = [(v.getDistance(), i, v) for i, v in enumerate(G) if v not in visited]

The second option is to modify Vertex to have a __lt__ magic method:

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

This is nice because you can heapify more directly now:

unvisitedQueue = [v for v in G if v not in visited]