I'm working on Prim's algorithm however I keep getting this error:
Traceback (most recent call last):
File "Prims/main.py", line 32, in <module>
graph.prims("r")
File "Prims/new_prims.py", line 94, in prims
if neighbour.weight < v.weight:
TypeError: '<' not supported between instances of 'str' and 'float'
I have a feeling that the add_vertex function isn't taking in parameters as it should but I'm not sure I am importing a .gl file in the format:
undirected weighted
r=a=2.2
r=b=6.4
r=d=12.5
d=c=1.0
d=e=9.75
e=h=4.0
e=f=3.4
f=g=1.4
When I tested my code, I can make it work like this
graph.add_vertex("a")
graph.add_vertex("b")
graph.add_vertex("f")
graph.add_vertex("c")
graph.add_vertex("d")
graph.add_vertex("e")
graph.add_edge("a", "b", 4)
graph.add_edge("a", "f", 2)
graph.add_edge("b", "c", 6)
graph.add_edge("f", "b", 3)
graph.add_edge("f", "c", 1)
graph.add_edge("f", "e", 4)
graph.add_edge("c", "d", 3)
graph.add_edge("d", "e", 2)
I want to be able to import the .gl file however so I wrote a function to read in the data and split by the "=":
graph: Graph = Graph()
file1 = open('Prims/Prim_000-1.gl', 'r')
firstline, *lines = file1.readlines()
direction, weight = firstline.split()
if direction == "undirected" and weight == "weighted":
for line in lines:
graph.add_edge(*(graph.add_vertex(key.strip())
for key in line.split("=")))
print(graph.getVertices())
Here is my code:
class Vertex:
def __init__(self, label: str = None, weight: int = float("inf"), key: int = None):
self.label: str = label
self.weight: int = weight
self.key: int = key
class PriorityQueue:
def __init__(self):
self.pq: list = [None]
self._pointer: int = 0
def is_empty(self) -> bool:
return self._pointer == 0
def insert(self, vertex: Vertex):
self.pq.append(vertex)
self._pointer += 1
vertex.key = self._pointer
self._perc_up(self._pointer)
def _perc_up(self, pointer: int):
while pointer // 2 > 0:
if self.pq[pointer // 2].weight > self.pq[pointer].weight:
self.pq[pointer // 2], self.pq[pointer] = self.pq[pointer], self.pq[pointer // 2]
self.pq[pointer // 2].key = pointer // 2
self.pq[pointer].key = pointer
pointer = pointer // 2
def decrease_key(self, pointer: int):
self._perc_up(pointer)
def delete_min(self) -> Vertex:
if self.is_empty():
raise Exception("Priority queue is empty")
v: Vertex = self.pq[1]
self.pq[1] = self.pq[self._pointer]
self.pq[1].key = 1
self.pq.pop()
self._pointer -= 1
self._perc_down(1)
return v
def _perc_down(self, pointer: int):
while pointer * 2 <= self._pointer:
min_index: int = self._find_swap_index(pointer)
if self.pq[pointer].weight > self.pq[min_index].weight:
self.pq[pointer], self.pq[min_index] = self.pq[min_index], self.pq[pointer]
self.pq[pointer].key = pointer
self.pq[min_index].key = min_index
pointer = min_index
def _find_swap_index(self, pointer: int) -> int:
if pointer * 2 + 1 > self._pointer:
return pointer * 2
else:
if self.pq[pointer * 2].weight <= self.pq[pointer * 2 + 1].weight:
return pointer * 2
else:
return pointer * 2 + 1
class Graph:
def __init__(self):
self._vertices: dict = {}
self._adjacency_map: dict = {}
self._prev: dict = {}
def add_vertex(self, label: str):
if label not in self._vertices:
v: Vertex = Vertex(label)
self._vertices[label] = v
self._adjacency_map[label]= []
self._prev[label] = None
return label
def add_edge(self, label1: str, label2: str, weight: int):
self._adjacency_map[label1].append(Vertex(label2, weight))
self._adjacency_map[label2].append(Vertex(label1, weight))
def prims(self, label: str):
result: str = ""
self._vertices[label].weight = 0
pq: PriorityQueue = PriorityQueue()
for label in self._vertices:
pq.insert(self._vertices[label])
while not pq.is_empty():
current: Vertex = pq.delete_min()
if self._prev[current.label] is not None:
result += self._prev[current.label] + " -> " + current.label + ", "
for neighbour in self._adjacency_map[current.label]:
v: Vertex = self._vertices[neighbour.label]
if neighbour.weight < v.weight:
v.weight = neighbour.weight
self._prev[v.label] = current.label
pq.decrease_key(v.key)
print(result)
source https://stackoverflow.com/questions/71819785/python-key-error-implementing-prims-algorithm
Comments
Post a Comment