unorderable类型：顶点（）<顶点（）

Question

我工作的一个Dijkstra算法，我得到这个错误： 类型错误：unorderable类型：顶点（）<顶点（）

整个错误日志：

Traceback (most recent call last): 
    File "C:/Users/Dimitar/PycharmProjects/Dijkstra/Dijkstra.py", line 165, in <module> 
    dijkstra(g, g.get_vertex('a')) 
    File "C:/Users/Dimitar/PycharmProjects/Dijkstra/Dijkstra.py", line 101, in dijkstra 
    heapq.heapify(unvisited_queue) 
TypeError: unorderable types: Vertex() < Vertex() 

这里是我的代码：

import sys 


class Vertex: 
    def __init__(self, node): 
     self.id = node 
     self.adjacent = {} 
     # Set distance to infinity for all nodes 
     self.distance = sys.maxsize 
     # Mark all nodes unvisited   
     self.visited = False 
     # Predecessor 
     self.previous = None 

    def add_neighbor(self, neighbor, weight=0): 
     self.adjacent[neighbor] = weight 

    def get_connections(self): 
     return self.adjacent.keys() 

    def get_id(self): 
     return self.id 

    def get_weight(self, neighbor): 
     return self.adjacent[neighbor] 

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

    def get_distance(self): 
     return self.distance 

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

    def set_visited(self): 
     self.visited = True 

    def __str__(self): 
     return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent]) 


class Graph: 
    def __init__(self): 
     self.vert_dict = {} 
     self.num_vertices = 0 

    def __iter__(self): 
     return iter(self.vert_dict.values()) 

    def add_vertex(self, node): 
     self.num_vertices = self.num_vertices + 1 
     new_vertex = Vertex(node) 
     self.vert_dict[node] = new_vertex 
     return new_vertex 

    def get_vertex(self, n): 
     if n in self.vert_dict: 
      return self.vert_dict[n] 
     else: 
      return None 

    def add_edge(self, frm, to, cost=0): 
     if frm not in self.vert_dict: 
      self.add_vertex(frm) 
     if to not in self.vert_dict: 
      self.add_vertex(to) 

     self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost) 
     self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost) 

    def get_vertices(self): 
     return self.vert_dict.keys() 

    def set_previous(self, current): 
     self.previous = current 

    def get_previous(self, current): 
     return self.previous 


def shortest(v, path): 
    ''' make shortest path from v.previous''' 
    if v.previous: 
     path.append(v.previous.get_id()) 
     shortest(v.previous, path) 
    return 


import heapq 


# noinspection PyArgumentList 
def dijkstra(aGraph, start): 
    print('''Dijkstra's shortest path''') 
    # Set the distance for the start node to zero 
    start.set_distance(0) 

    # Put tuple pair into the priority queue 
    unvisited_queue = [(v.get_distance(), v) for v in aGraph] 
    heapq.heapify(unvisited_queue) 

    while len(unvisited_queue): 
     # Pops a vertex with the smallest distance 
     uv = heapq.heappop(unvisited_queue) 
     current = uv[1] 
     current.set_visited() 

     for next in current.adjacent: 
      # if visited, skip 
      if next.visited: 
       continue 
      new_dist = current.get_distance() + current.get_weight(next) 

      if new_dist < next.get_distance(): 
       next.set_distance(new_dist) 
       next.set_previous(current) 
       print 
       ('updated : current = %s next = %s new_dist = %s' \ 
       % (current.get_id(), next.get_id(), next.get_distance())) 
      else: 
       print 
       ('not updated : current = %s next = %s new_dist = %s' \ 
       % (current.get_id(), next.get_id(), next.get_distance())) 

     # Rebuild heap 
     # 1. Pop every item 
     while len(unvisited_queue): 
      heapq.heappop(unvisited_queue) 
     # 2. Put all vertices not visited into the queue 
     unvisited_queue = [(v.get_distance(), v) for v in aGraph if not v.visited] 
     heapq.heapify(unvisited_queue) 


if __name__ == '__main__': 

    g = Graph() 

    g.add_vertex('a') 
    g.add_vertex('b') 
    g.add_vertex('c') 
    g.add_vertex('d') 
    g.add_vertex('e') 
    g.add_vertex('f') 

    g.add_edge('a', 'b', 7) 
    g.add_edge('a', 'c', 9) 
    g.add_edge('a', 'f', 14) 
    g.add_edge('b', 'c', 10) 
    g.add_edge('b', 'd', 15) 
    g.add_edge('c', 'd', 11) 
    g.add_edge('c', 'f', 2) 
    g.add_edge('d', 'e', 6) 
    g.add_edge('e', 'f', 9) 

    print 
    ('Graph data:') 
    for v in g: 
     for w in v.get_connections(): 
      vid = v.get_id() 
      wid = w.get_id() 
      print 
      ('(%s , %s, %3d)' % (vid, wid, v.get_weight(w))) 

    dijkstra(g, g.get_vertex('a')) 

    target = g.get_vertex('e') 
    path = [target.get_id()] 
    shortest(target, path) 
    print('The shortest path : %s' % (path[::-1])) 

有人能解释我为什么我得到这样那样的错误。我是一名自学者，一些帮助将非常感激。

的导致该错误是代码行： heapq.heapify（unvisited_queue）

在此先感谢大家对话题谁发表评论。

最佳， 贝尔巴托夫

Answer 1

自定义类型没有隐含地定义排序的实例之间：

>>> v1 = Vertex(1) 
>>> v2 = Vertex(2) 
>>> v1 < v2 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: unorderable types: Vertex() < Vertex() 

你需要告诉蟒蛇怎么比较你的顶点。您需要实施rich comparison方法才能这样做。由于heapify要求<，您必须至少执行__lt__。

你也可以看看@total_ordering修饰器，以避免实现所有这些。

线沿线的东西：

from functools import total_ordering 

@total_ordering 
class Vertex: 
    # Your current class code 

    def __eq__(self, other): 
     if isinstance(other, self.__class__): 
      return self.distance == other.distance 
     return NotImplemented 

    def __lt__(self, other): 
     if isinstance(other, self.__class__): 
      return self.distance < other.distance 
     return NotImplemented 

如果你需要使用类作为字典的键，你就需要添加__hash__方法。可能是这样的：

def __hash__(self): 
     return id(self)