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...

How to show number of registered users in Laravel based on usertype?

i'm trying to display data from the database in the admin dashboard i used this: <?php use Illuminate\Support\Facades\DB; $users = DB::table('users')->count(); echo $users; ?> and i have successfully get the correct data from the database but what if i want to display a specific data for example in this user table there is "usertype" that specify if the user is normal user or admin i want to user the same code above but to display a specific usertype i tried this: <?php use Illuminate\Support\Facades\DB; $users = DB::table('users')->count()->WHERE usertype =admin; echo $users; ?> but it didn't work, what am i doing wrong? source https://stackoverflow.com/questions/68199726/how-to-show-number-of-registered-users-in-laravel-based-on-usertype