Attribute Error for Prim's Algorithm implementation in Python

I’ve been struggling with the code used to implement Prim’s Algorithm in Python. I really hope that someone help me as I needed this specific code for my Case Study. Thank you!

Here’s the code:

# A Python program for Prims's MST for
# adjacency list representation of graph
from collections import defaultdict
import sys

class Heap():
    def __init__(self):
        self.array = []
        self.size = 0
        self.pos = []

    def newMinHeapNode(self, v, dist):
           minHeapNode = [v, dist]
           return minHeapNode
# A utility function to swap two nodes of
    # min heap. Needed for min heapify
def swapMinHeapNode(self, a, b):
        t = self.array[a]
        self.array[a] = self.array[b]
        self.array[b] = t
# A standard function to heapify at given idx
    # This function also updates position of nodes
    # when they are swapped. Position is needed
    # for decreaseKey()
def minHeapify(self, idx):
        smallest = idx
        left = 2 * idx + 1
        right = 2 * idx + 2
        if left < self.size and self.array[left][1] < \
                                self.array[smallest][1]:
            smallest = left
        if right < self.size and self.array[right][1] < \
                                self.array[smallest][1]:
            smallest = right
# The nodes to be swapped in min heap
        # if idx is not smallest
        if smallest != idx:
# Swap positions
            self.pos[ self.array[smallest][0] ] = idx
            self.pos[ self.array[idx][0] ] = smallest
# Swap nodes
            self.swapMinHeapNode(smallest, idx)
            self.minHeapify(smallest)
# Standard function to extract minimum node from heap
def extractMin(self):
# Return NULL wif heap is empty
        if self.isEmpty() == True:
           return
# Store the root node
        root = self.array[0]
# Replace root node with last node
        lastNode = self.array[self.size - 1]
        self.array[0] = lastNode
# Update position of last node
        self.pos[lastNode[0]] = 0
        self.pos[root[0]] = self.size - 1
# Reduce heap size and heapify root
        self.size -= 1
        self.minHeapify(0)
        return root
def isEmpty(self):
        return True if self.size == 0 else False
def decreaseKey(self, v, dist):
# Get the index of v in  heap array
    i = self.pos[v]
# Get the node and update its dist value
    self.array[i][1] = dist
# Travel up while the complete tree is not
        # hepified. This is a O(Logn) loop
    while i > 0 and self.array[i][1] < \
                    self.array[(i - 1) / 2][1]:
# Swap this node with its parent
            self.pos[ self.array[i][0] ] = (i-1)/2
            self.pos[ self.array[(i-1)/2][0] ] = i
            self.swapMinHeapNode(i, (i - 1)/2 )
# move to parent index
            i = (i - 1) / 2;
# A utility function to check if a given vertex
    # 'v' is in min heap or not
def isInMinHeap(self, v):
    if self.pos[v] < self.size:
            return True
            return False
def printArr(parent, n):
    for i in range(1, n):
        print ("% d - % d" % (parent[i], i))
class Graph():
    def __init__(self, V):
            self.V = V
            self.graph = defaultdict(list)
# Adds an edge to an undirected graph
def addEdge(self, src, dest, weight):
# Add an edge from src to dest.  A new node is
        # added to the adjacency list of src. The node
        # is added at the begining. The first element of
        # the node has the destination and the second
        # elements has the weight
        newNode = [dest, weight]
        self.graph[src].insert(0, newNode)
# Since graph is undirected, add an edge from
        # dest to src also
        newNode = [src, weight]
        self.graph[dest].insert(0, newNode)
# The main function that prints the Minimum
    # Spanning Tree(MST) using the Prim's Algorithm.
    # It is a O(ELogV) function
def PrimMST(self):
        # Get the number of vertices in graph
            V = self.V
# key values used to pick minimum weight edge in cut
            key = []
# List to store contructed MST
            parent = []
# minHeap represents set E
            minHeap = Heap()
# Initialize min heap with all vertices. Key values of all
        # vertices (except the 0th vertex) is is initially infinite
            for v in range(V):
                parent.append(-1)
                key.append(sys.maxint)
                minHeap.array.append( minHeap.newMinHeapNode(v, key[v]) )
                minHeap.pos.append(v)
    # Make key value of 0th vertex as 0 so
            # that it is extracted first
            minHeap.pos[0] = 0
            key[0] = 0
            minHeap.decreaseKey(0, key[0])
    # Initially size of min heap is equal to V
            minHeap.size = V;
    # In the following loop, min heap contains all nodes
            # not yet added in the MST.
            while minHeap.isEmpty() == False:
    # Extract the vertex with minimum distance value
                newHeapNode = minHeap.extractMin()
                    u = newHeapNode[0]
# Traverse through all adjacent vertices of u
            # (the extracted vertex) and update their
            # distance values
        for pCrawl in self.graph[u]:
            v = pCrawl[0]
# If shortest distance to v is not finalized
                # yet, and distance to v through u is less than
                # its previously calculated distance
        if minHeap.isInMinHeap(v) and pCrawl[1] < key[v]:
                    key[v] = pCrawl[1]
                    parent[v] = u
# update distance value in min heap also
                    minHeap.decreaseKey(v, key[v])
        printArr(parent, V)
def main():
    #pass
    graph = Graph(9)

graph.addEdge(0, 7, 8)
graph.addEdge(1, 2, 8)
graph.addEdge(1, 7, 11)
graph.addEdge(2, 3, 7)
graph.addEdge(2, 8, 2)
graph.addEdge(2, 5, 4)
graph.addEdge(3, 4, 9)
graph.addEdge(3, 5, 14)
graph.addEdge(4, 5, 10)
graph.addEdge(5, 6, 2)
graph.addEdge(6, 7, 1)
graph.addEdge(6, 8, 6)
graph.addEdge(7, 8, 7)
graph.PrimMST()

if __name__ == '__main__':
    main()

When I tried to run it, it returns an error ‘Graph’ object has no attribute ‘addEdge’. I specifically need this code since this kind of Prim’s Algorithm used a Edge List (node, node, weight) in adding an edge unlike other code that use Adjacency Matrix. Therefore, it is much easier to use this kind of code. Helping me would a huge help for my subject.

I think you may have several indentation errors. Python is based on proper indentations. I am a novice, but I played around with your indentations inside of your Heap class and Graph class and finally got stuck on an error for this line :

 printArr(parent, V)

I don’t see what object method your trying to invoke.

here is some reformatted code i played with that did not produce errors, but I erroneously made changes without trying to grasp whatr your code is doing.

# A Python program for Prims's MST for
# adjacency list representation of graph
from collections import defaultdict
import sys

class Heap():
    def __init__(self):
        self.array = []
        self.size = 0
        self.pos = []

    def newMinHeapNode(self, v, dist):
            minHeapNode = [v, dist]
            return minHeapNode
# A utility function to swap two nodes of
    # min heap. Needed for min heapify
    def swapMinHeapNode(self, a, b):
        t = self.array[a]
        self.array[a] = self.array[b]
        self.array[b] = t
# A standard function to heapify at given idx
    # This function also updates position of nodes
    # when they are swapped. Position is needed
    # for decreaseKey()
    def minHeapify(self, idx):
        smallest = idx
        left = 2 * idx + 1
        right = 2 * idx + 2
        if left < self.size and self.array[left][1] < \
                                self.array[smallest][1]:
            smallest = left
        if right < self.size and self.array[right][1] < \
                                self.array[smallest][1]:
            smallest = right
# The nodes to be swapped in min heap
        # if idx is not smallest
        if smallest != idx:
# Swap positions
            self.pos[ self.array[smallest][0] ] = idx
            self.pos[ self.array[idx][0] ] = smallest
# Swap nodes
            self.swapMinHeapNode(smallest, idx)
            self.minHeapify(smallest)
# Standard function to extract minimum node from heap
    def extractMin(self):
# Return NULL wif heap is empty
        if self.isEmpty() == True:
           return
# Store the root node
        root = self.array[0]
# Replace root node with last node
        lastNode = self.array[self.size - 1]
        self.array[0] = lastNode
# Update position of last node
        self.pos[lastNode[0]] = 0
        self.pos[root[0]] = self.size - 1
# Reduce heap size and heapify root
        self.size -= 1
        self.minHeapify(0)
        return root
    def isEmpty(self):
        return True if self.size == 0 else False
    def decreaseKey(self, v, dist):
# Get the index of v in  heap array
        i = self.pos[v]
# Get the node and update its dist value
        self.array[i][1] = dist
# Travel up while the complete tree is not
        # hepified. This is a O(Logn) loop
        while i > 0 and self.array[i][1] < \
                    self.array[(i - 1) / 2][1]:
# Swap this node with its parent
            self.pos[ self.array[i][0] ] = (i-1)/2
            self.pos[ self.array[(i-1)/2][0] ] = i
            self.swapMinHeapNode(i, (i - 1)/2 )
# move to parent index
            i = (i - 1) / 2;
# A utility function to check if a given vertex
    # 'v' is in min heap or not
    def isInMinHeap(self, v):
        if self.pos[v] < self.size:
            return True
            return False
    def printArr(parent, n):
        for i in range(1, n):
            print ("% d - % d" % (parent[i], i))
class Graph():
    def __init__(self, V):
            self.V = V
            self.graph = defaultdict(list)
# Adds an edge to an undirected graph
    def addEdge(self, src, dest, weight):
# Add an edge from src to dest.  A new node is
        # added to the adjacency list of src. The node
        # is added at the begining. The first element of
        # the node has the destination and the second
        # elements has the weight
        newNode = [dest, weight]
        self.graph[src].insert(0, newNode)
# Since graph is undirected, add an edge from
        # dest to src also
        newNode = [src, weight]
        self.graph[dest].insert(0, newNode)
# The main function that prints the Minimum
    # Spanning Tree(MST) using the Prim's Algorithm.
    # It is a O(ELogV) function
    def PrimMST(self):
        # Get the number of vertices in graph
            V = self.V
# key values used to pick minimum weight edge in cut
            key = []
# List to store contructed MST
            parent = []
# minHeap represents set E
            minHeap = Heap()
# Initialize min heap with all vertices. Key values of all
        # vertices (except the 0th vertex) is is initially infinite
            for v in range(V):
                parent.append(-1)
                key.append(sys.maxsize)
                minHeap.array.append( minHeap.newMinHeapNode(v, key[v]) )
                minHeap.pos.append(v)
    # Make key value of 0th vertex as 0 so
            # that it is extracted first
            minHeap.pos[0] = 0
            key[0] = 0
            minHeap.decreaseKey(0, key[0])
    # Initially size of min heap is equal to V
            minHeap.size = V;
    # In the following loop, min heap contains all nodes
            # not yet added in the MST.
            while minHeap.isEmpty() == False:
    # Extract the vertex with minimum distance value
                newHeapNode = minHeap.extractMin()
                u = newHeapNode[0]
# Traverse through all adjacent vertices of u
            # (the extracted vertex) and update their
            # distance values
            for pCrawl in self.graph[u]:
                v = pCrawl[0]
# If shortest distance to v is not finalized
                # yet, and distance to v through u is less than
                # its previously calculated distance
            if minHeap.isInMinHeap(v) and pCrawl[1] < key[v]:
                    key[v] = pCrawl[1]
                    parent[v] = u
# update distance value in min heap also
                    minHeap.decreaseKey(v, key[v])
            Heap.printArr(parent, V)
def main():
    #pass
    graph = Graph(9)

    graph.addEdge(0, 7, 8)
    graph.addEdge(1, 2, 8)
    graph.addEdge(1, 7, 11)
    graph.addEdge(2, 3, 7)
    graph.addEdge(2, 8, 2)
    graph.addEdge(2, 5, 4)
    graph.addEdge(3, 4, 9)
    graph.addEdge(3, 5, 14)
    graph.addEdge(4, 5, 10)
    graph.addEdge(5, 6, 2)
    graph.addEdge(6, 7, 1)
    graph.addEdge(6, 8, 6)
    graph.addEdge(7, 8, 7)
    graph.PrimMST()

if __name__ == '__main__':
    main()

with proper indentation , you may need to just tweak this to your expectations

 Heap.printArr(parent, V)

Maybe that will help I hope. I used Pycharm editor that made the indentations stick out like a sore thumb. Good Luck

edit
the output I received :

-1 -  1
-1 -  2
-1 -  3
-1 -  4
-1 -  5
-1 -  6
-1 -  7
-1 -  8

Process finished with exit code 0

and also I had to change this:

key.append(sys.maxint) 
key.append(sys.maxsize)