# 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] < \
self.array[smallest]:
smallest = left
if right < self.size and self.array[right] < \
self.array[smallest]:
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] ] = idx
self.pos[ self.array[idx] ] = 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
# Replace root node with last node
lastNode = self.array[self.size - 1]
self.array = lastNode
# Update position of last node
self.pos[lastNode] = 0
self.pos[root] = 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] = dist
# Travel up while the complete tree is not
# hepified. This is a O(Logn) loop
while i > 0 and self.array[i] < \
self.array[(i - 1) / 2]:
# Swap this node with its parent
self.pos[ self.array[i] ] = (i-1)/2
self.pos[ self.array[(i-1)/2] ] = 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
# Add an edge from src to dest.  A new node is
# 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
key = 0
minHeap.decreaseKey(0, key)
# 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
# Traverse through all adjacent vertices of u
# (the extracted vertex) and update their
# distance values
for pCrawl in self.graph[u]:
v = pCrawl
# 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 < key[v]:
key[v] = pCrawl
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.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] < \
self.array[smallest]:
smallest = left
if right < self.size and self.array[right] < \
self.array[smallest]:
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] ] = idx
self.pos[ self.array[idx] ] = 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
# Replace root node with last node
lastNode = self.array[self.size - 1]
self.array = lastNode
# Update position of last node
self.pos[lastNode] = 0
self.pos[root] = 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] = dist
# Travel up while the complete tree is not
# hepified. This is a O(Logn) loop
while i > 0 and self.array[i] < \
self.array[(i - 1) / 2]:
# Swap this node with its parent
self.pos[ self.array[i] ] = (i-1)/2
self.pos[ self.array[(i-1)/2] ] = 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
# Add an edge from src to dest.  A new node is
# 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
key = 0
minHeap.decreaseKey(0, key)
# 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
# Traverse through all adjacent vertices of u
# (the extracted vertex) and update their
# distance values
for pCrawl in self.graph[u]:
v = pCrawl
# 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 < key[v]:
key[v] = pCrawl
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.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

``````-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)
``````

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.