Skip to main content

Python Key Error Implementing Prim's Algorithm

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

Popular posts from this blog

Where and how is this Laravel kernel constructor called? [closed]

Where and how is this Laravel kernel constructor called? public fucntion __construct(Application $app, $Router $roouter) { } I have read the documentation and some online tutorial but I can find any clear explanation. I am learning Laravel and I am wondering where does this kernel constructor receives its arguments from. "POSTMOTERM" CLARIFICATION: Here is more clarity.I have checked the boostrap/app.php and it is only used for boostrapping the interfaces into the container class. What is not clear to me is where and how the Kernel class is instatiated and the arguments passed to the object calling the constructor.Something similar to; obj = new kernel(arg1,arg2) or, is the framework using some magic functions somewhere? Special gratitude to those who burn their eyeballs and brain cells on this trivia before it goes into a full blown menopause alias "MARKED AS DUPLICATE". To some of the itchy-finger keyboard warriors, a.k.a The mods,because I believe in th...

Why is my reports service not connecting?

I am trying to pull some data from a Postgres database using Node.js and node-postures but I can't figure out why my service isn't connecting. my routes/index.js file: const express = require('express'); const router = express.Router(); const ordersCountController = require('../controllers/ordersCountController'); const ordersController = require('../controllers/ordersController'); const weeklyReportsController = require('../controllers/weeklyReportsController'); router.get('/orders_count', ordersCountController); router.get('/orders', ordersController); router.get('/weekly_reports', weeklyReportsController); module.exports = router; My controllers/weeklyReportsController.js file: const weeklyReportsService = require('../services/weeklyReportsService'); const weeklyReportsController = async (req, res) => { try { const data = await weeklyReportsService; res.json({data}) console...

Confusion between commands.Bot and discord.Client | Which one should I use?

Whenever you look at YouTube tutorials or code from this website there is a real variation. Some developers use client = discord.Client(intents=intents) while the others use bot = commands.Bot(command_prefix="something", intents=intents) . Now I know slightly about the difference but I get errors from different places from my code when I use either of them and its confusing. Especially since there has a few changes over the years in discord.py it is hard to find the real difference. I tried sticking to discord.Client then I found that there are more features in commands.Bot . Then I found errors when using commands.Bot . An example of this is: When I try to use commands.Bot client = commands.Bot(command_prefix=">",intents=intents) async def load(): for filename in os.listdir("./Cogs"): if filename.endswith(".py"): client.load_extension(f"Cogs.{filename[:-3]}") The above doesnt giveany response from my Cogs ...