0
私は次のエラー取得しています：私は__eq__を定義すると、デフォルトのハッシュ関数は、関数を離れて行くと、私は__hash__方法を再定義する必要があるが、私はありません持っていることを意味していることを知っている非ハッシュタイプ：「頂点」
Traceback (most recent call last):
File "dijkastras.py", line 146, in <module>
g.add_edge(vertices[i], k[0], int(k[1]))
File "dijkastras.py", line 82, in add_edge
self.vertices[frm].add_neighbour(self.vertices[to], weight)
File "dijkastras.py", line 16, in add_neighbour
self.adjacent[neighbour] = weight
TypeError: unhashable type: 'Vertex'
をどのようにそれを行うアイデア。誰かがハッシュ関数の実装を提案できますか？ ありがとうございます。
ここは私のコードです。 （;あなたが選択したものは自分自身をハッシュ可能である必要があります。また、IDだけでなく、異なる属性の組み合わせを選択することができます）
def __hash__():
return hash(str(self.id))
を：
import sys
import heapq
from functools import total_ordering
@total_ordering
class Vertex:
def __init__(self, node):
self.id = node
self.adjacent = {}
# Set the distances to infinity for all nodes
self.distance = sys.maxsize
self.visited = False
self.previous = None
def add_neighbour(self, neighbour, weight=0):
self.adjacent[neighbour] = weight
def get_connections(self):
return self.adjacent.keys()
def get_id(self):
return self.id
def get_weight(self, neighbour):
return self.adjacent[neighbour]
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])
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
class Graph:
def __init__(self):
self.vertices = {}
self.num_vertices = 0
def __iter__(self):
return iter(self.vertices.values())
def add_vertex(self, node):
self.num_vertices += 1
new_vertex = Vertex(node)
self.vertices[node] = new_vertex
return new_vertex
def get_vertex(self, n):
if n in self.vertices:
return self.vertices[n]
return None
def get_vertices(self):
return self.vertices.keys()
def add_edge(self, frm, to, weight=0):
if frm not in self.vertices:
self.add_vertex(frm)
if to not in self.vertices:
self.add_vertex(to)
self.vertices[frm].add_neighbour(self.vertices[to], weight)
self.vertices[to].add_neighbour(self.vertices[frm], weight)
def set_previous(self, current):
self.previous = current
def get_previous(self, current):
return self.previous
def shortest(vertex, path):
''' Find the shortest path from vertex.previous'''
if vertex.previous:
path.append(vertex.previous.get_id())
shortest(vertex.previous, path)
return
def dijkstra(aGraph, start, target):
start.set_distance(0)
univisted = [(v.get_distance(), v) for v in aGraph]
print(univisted)
heapq.heapify(univisted)
while len(univisted):
uv = heapq.heappop(univisted)
current = uv[1]
current.set_visited()
for next in current.adjacent:
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()))
while len(univisted):
heapq.heappop(univisted)
univisted = [(v.get_distance(), v) for v in aGraph if not v.visited]
heapq.heapify(univisted)
if __name__ == '__main__':
g = Graph()
text = open('Graph.txt').read().split('\n')
vertices = text[0].split()
for i in vertices:
g.add_vertex(i)
vert_all = []
for i in range(1, 11):
vert_all.append(list(zip(vertices, text[i].split()[1:])))
filtered_vert_all = []
for i in vert_all:
filtered = [x for x in i if x[1] is not '0']
filtered_vert_all.append(filtered)
# print(filtered_vert_all)
for i, j in enumerate(filtered_vert_all):
for k in j:
print(vertices[i], k[0], int(k[1]))
g.add_edge(vertices[i], k[0], int(k[1]))
for v in g:
for w in v.get_connections():
vid = v.get_id()
wid = w.get_id()
print('({} , {}, {:d})'.format(vid, wid, v.get_weight(w)))
dijkstra(g, g.get_vertex('E'), g.get_vertex('J'))
target = g.get_vertex('E')
path = [target.get_id()]
shortest(target, path)
print('The shortest path is: {}'.format(path[::-1]))