RUBY - PRIM'S ALGORITHM - MINIMUM SPANNING TREE - CODE

Example :

class Edge
	attr_accessor :startVertex, :endVertex, :value
end

def heapify(verticesArray, root, length)
	left = (2*root)+1
	right = (2*root)+2
	smallest = root
	
	if (left < length and right <= length and $vertexVal.fetch(verticesArray[right]) < $vertexVal.fetch(verticesArray[left]))
		smallest = right
	elsif (left <= length)
		smallest = left
	end

	if ($vertexVal.fetch(verticesArray[root]) > $vertexVal.fetch(verticesArray[smallest]))
		temp = verticesArray[root]
		verticesArray[root] = verticesArray[smallest]
		verticesArray[smallest] = temp
		heapify(verticesArray, smallest, length)
	end	
end	

def buildHeap()
	verticesArray = $vertexVal.keys()
	len = (((verticesArray.length-1)-1)/ 2).to_i 
	(0..len).reverse_each do |parent|
		heapify(verticesArray, parent, verticesArray.length-1)
	end
	
	$verticesKeyArray = verticesArray
end	
	
def updateHeap(vertex, length)
	$vertexVal[vertex] = length
	verticesArray = $vertexVal.keys()
	
	len = (((verticesArray.length-1)-1)/ 2).to_i 
	(0..len).reverse_each do |parent|
		heapify(verticesArray, parent, verticesArray.length-1)
	end	
	$verticesKeyArray = verticesArray
end	
	
def containsVertex(vertex)
	if $vertexVal.has_key?(vertex)
		return true
	else
		return false
	end
end	

def delete_min()
	temp = $verticesKeyArray[0]
	lengthArray = $verticesKeyArray.length-1
	$verticesKeyArray[0] = $verticesKeyArray[lengthArray]
	$vertexVal.delete(temp)
	$verticesKeyArray = $verticesKeyArray.slice(0,lengthArray)
	
	if(lengthArray>0)
		heapify($verticesKeyArray, 0, lengthArray-1)
	end	
	return temp
end	

def getWeight(vertex)
	return $vertexVal.fetch(vertex)
end	

def empty()
	if ($verticesKeyArray.length > 0)
		return false
	else
		return true
	end
end		

def primMST()
	$vertexVal = {}

	# Vertex to Edge Hash
	vertexToEdge = {}

	# Assign all the initial values as infinity for all the $vertices.
	for v in $vertices
		$vertexVal[v] = (2**(0.size * 8 -2) -1)
	end	

    # Call buildHeap() to create the MinHeap
	buildHeap()

    # Replace the value of start vertex to 0.
	updateHeap("a",0)

    # Continue until the Min-Heap is not empty.
	while (!empty())
    	# Extract minimum value vertex from Map in Heap
		currentVertex = delete_min()

        # Need to fetch the edge for the vertex and add it to the Minimum Spanning Tree..
        # Just note, the edge for the source vertex will not be added.
		spanningTreeEdge = vertexToEdge[currentVertex]

		if(spanningTreeEdge != nil)
			$result.push(spanningTreeEdge)
		end	

        # fetch all the adjacent $vertices and iterate through them.
		for edge in getEdges(currentVertex)
			adjacentVertex = edge.endVertex
                
            # We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex
            # is greater than this edge length.
			if(containsVertex(adjacentVertex) and getWeight(adjacentVertex) > edge.value)
                # Replace the edge length with this edge weight.
				updateHeap(adjacentVertex, edge.value)
				vertexToEdge[adjacentVertex] = edge
			end
		end
	end
end				

def getEdges(vertex)
	edgeList = []
	i = $vertices.index(vertex)
	for iter in $adjcList[i]
		edgeList.push(iter)
	end	
	return edgeList
end	

def constructAdjacencyList(vertex1, vertex2, edgeVal)
	edge = Edge.new()
	edge.startVertex = vertex1
	edge.endVertex = vertex2
	edge.value = edgeVal

	$adjcList.push([])
	$adjcList[$vertices.index(vertex1)].push(edge)
end	

def insertVertex(vertex)
	$vertices.push(vertex)
end	

def printEdgeList()
	for edge in $result
		print("The Edge between ", edge.startVertex ," and ", edge.endVertex, " is ", edge.value,"\n")
	end
end

$verticesKeyArray
$adjcList = [[]]
$vertices = []
$vertexVal = {}

# Stores the Minimum spanning Tree
$result = []

# Insert $vertices
insertVertex("a")
insertVertex("b")
insertVertex("c")
insertVertex("d")
insertVertex("e")

# Create Adjacency List with Edges.
constructAdjacencyList("a", "b",1)
constructAdjacencyList("a", "c",5)
constructAdjacencyList("a", "d",4)

constructAdjacencyList("b", "a",1)
constructAdjacencyList("b" ,"e",8)

constructAdjacencyList("c", "a",5)
constructAdjacencyList("c", "d",12)
constructAdjacencyList("c", "e",9)

constructAdjacencyList("d", "a", 4)
constructAdjacencyList("d", "c", 12)
constructAdjacencyList("d", "e", 3)

constructAdjacencyList("e", "b", 8)
constructAdjacencyList("e", "c", 9)
constructAdjacencyList("e", "d", 3)

primMST()

printEdgeList()

Output :

1. First step is, we select any vertex and start from it(We have selected the vertex a in this case).


2. Then, we try finding the adjacent Edges of that Vertex(In this case, we try finding the adjacent edges of vertex a).
   
   This is where, we will be using Adjacency List for finding the Adjacent Edges.


3. Next, we will take all the Adjacent edges from above and check, which edge has the smallest length/weight.
   
   Again, this is where, we will be using Min-Heap for finding the Adjacent Edges.

Code explanation for Prim's Algorithm - Minimum Spanning Tree

$vertices = []

$adjcList = [[]]

# Insert Vertices
insertVertex("a")
insertVertex("b")
insertVertex("c")
insertVertex("d")
insertVertex("e")

# Create Adjacency List with Edges.
constructAdjacencyList("a", "b",1)
constructAdjacencyList("a", "c",5)
constructAdjacencyList("a", "d",4)

constructAdjacencyList("b", "a",1)
constructAdjacencyList("b" ,"e",8)

constructAdjacencyList("c", "a",5)
constructAdjacencyList("c", "d",12)
constructAdjacencyList("c", "e",9)

constructAdjacencyList("d", "a", 4)
constructAdjacencyList("d", "c", 12)
constructAdjacencyList("d", "e", 3)

constructAdjacencyList("e", "b", 8)
constructAdjacencyList("e", "c", 9)
constructAdjacencyList("e", "d", 3)

Click Here - For the creation process of Adjacency List.

Explanation of def constructAdjacencyList(vertex1, vertex2, edgeVal) method

def constructAdjacencyList(vertex1, vertex2, edgeVal)
	edge = Edge.new()
	edge.startVertex = vertex1
	edge.endVertex = vertex2
	edge.value = edgeVal

	$adjcList.push([])
	$adjcList[$vertices.index(vertex1)].push(edge)
end

Let us take the example of the Edge (a,b) with length 1 and understand the above code.

constructAdjacencyList("a", "b", 1)

Now, if we look at the method definition,

def constructAdjacencyList(vertex1, vertex2, edgeVal)

vertex1 is initialised with a.

vertex2 is initialised with b.

edgeVal is initialised with 1.

The next thing we do is, create an Edge object.

edge = Edge.new()

And initialise the Edge edge object with the start vertex, end vertex and the length of the Edge.

edge.startVertex = vertex1
edge.endVertex = vertex2
edge.value = edgeVal

And the Edge object looks somewhat like,

Now, since we have the Edge (a,b) initialised. The next task would be, to add this Edge to the AdjacencyList.

And as we have seen, there is a 2D LinkedList to store the Adjacency List.

$adjcList = [[]]

Now, we will be creating the first row of LinkedList,

$adjcList.push([])

And then we will try finding out, for which vertex we are going to insert the Edge.

$adjcList[$vertices.index(vertex1)].push(edge)

In simple words, vertices.index(vertex1) will tell us about the position of the start vertex.

In this case, the start vertex is a. And vertices.indexOf(vertex1) will tell us about its position, i.e. 0.

So, if we substitute the line,

$adjcList[$vertices.index(vertex1)].push(edge)

With the value of vertices.index(vertex1),

adjcList[0].push(edge)

The edge would be added to the 0th location of the 2d LinkedList.

This is how a 2D LinkedList looks like. Just remember, the empty blocks are not yet created, but will be created eventually.

For now, only the first row is created with the first column where the edge

is inserted.

Next, when we try to insert the second adjacent edge of a i.e. a,c.

constructAdjacencyList("a", "c", 5)

An edge object will be created

edge.startVertex = vertex1
edge.endVertex = vertex2
edge.value = edgeVal

And the Edge object looks somewhat like,

Once again the start vertex is a. And vertices.indexOf(vertex1) will tell us about its position, i.e. 0.

So, if we substitute the line,

adjcList[vertices.index(vertex1)].push(edge)

With the value of vertices.indexOf(vertex1),

adjcList[0].push(edge)

The edge would be added to the 1st row of the 2d LinkedList, just next to the first edge.

Similarly, we insert the third adjacent edge of a i.e. a,d.

constructAdjacencyList("a", "d", 4)

An edge object will be created

edge.startVertex = vertex1
edge.endVertex = vertex2
edge.value = edgeVal

And the Edge object looks somewhat like,

Once again the start vertex is a. And vertices.index(vertex1) will tell us about its position, i.e. 0.

So, if we substitute the line,

adjcList[vertices.index(vertex1)].push(edge)

With the value of vertices.index(vertex1),

adjcList[0].push(edge)

The edge would be added to the 1st row of the 2d LinkedList, just next to the first edge.

Similarly, we insert the adjacent edge of b i.e. b,a.

constructAdjacencyList("b", "a", 1);

An edge object will be created

edge.startVertex = vertex1
edge.endVertex = vertex2
edge.value = edgeVal

And the Edge object looks somewhat like,

Now, the start vertex is b. And vertices.index(vertex1) will tell us about its position, i.e. 1.

So, if we substitute the line,

adjcList[vertices.index(vertex1)].push(edge)

With the value of vertices.index(vertex1),

adjcList[1].push(edge)

And this time, the edge would be added to the 2nd row of the 2d LinkedList.

And eventually the AdjacencyList with Edges would be created with the 2D LinkedList.

primMST()

Click Here - For Min-Heap Data Structure Recap.

There are four important method in the MinHeap class that are quite important.

They are :

1. def delete_min()


2. def updateHeap(vertex, length)


3. def buildHeap()


4. def heapify(verticesArray, root, length)

Now, if we look at the primMST() method.

The Hash vertexVal is getting initialised here.

$vertexVal = {}

Next, we initialise the Hash with the vertices as key and assign the value as sys.maxsize. This sys.maxsize is so large that it could be compared with infinity.

# Assign all the initial values as infinity for all the Vertices.
for v in $vertices
	$vertexVal[v] = (2**(0.size * 8 -2) -1)
end

So, the Hash vertexVal is loaded with values.

Next, we call the build_heap() method to create the MinHeap, with the values of the Hash vertexVal.

buildHeap()

Explanation of def buildHeap() method :

def buildHeap()
	verticesArray = $vertexVal.keys()
	len = (((verticesArray.length-1)-1)/ 2).to_i
	(0..len).reverse_each do |parent|
		heapify(verticesArray, parent, verticesArray.length-1)
	end

	$verticesKeyArray = verticesArray
end

Just remember, Hash is not a good Data Structure for Heap. Whereas array is an excellent Data Structure for Heap.

So, we take the keys from the Hash and create an Array out of it.

verticesArray = $vertexVal.keys()

Then, we divide the Array into two parts and run a for loop. Then call the Heapify method.

len = (((verticesArray.length-1)-1)/ 2).to_i
(0..len).reverse_each do |parent|
	heapify(verticesArray, parent, verticesArray.length-1)
end

So, what does the heapify(..) method do?

Let us see.

Explanation of def heapify(verticesArray, root, length) method :

def heapify(verticesArray, root, length)
	left = (2*root)+1
	right = (2*root)+2
	smallest = root

	if (left < length and right <= length and $vertexVal.fetch(verticesArray[right]) < $vertexVal.fetch(verticesArray[left]))
		smallest = right
	elsif (left <= length)
		smallest = left
	end

	if ($vertexVal.fetch(verticesArray[root]) > $vertexVal.fetch(verticesArray[smallest]))
		temp = verticesArray[root]
		verticesArray[root] = verticesArray[smallest]
		verticesArray[smallest] = temp
		heapify(verticesArray, smallest, length)
	end
end

Since, all the values of the Hash vertexVal are infinity now. So, it doesn't matter how the values will be inserted in the Min-Heap.

For the sake of understanding, let us understand the functionality of heapify(...) method.

So, we have passed the verticesArray, root element and the length of the Array to heapify(...) method.

Then, we have calculated the left, right and root element of the Heap.

left = (2*root)+1
right = (2*root)+2
smallest = root

Since, this is a Min-Heap. The smallest element would be at the root of the Heap.

So, we try initialising the smallest element with its right value.

And the below if condition checks, if the left and right element is less than the length of the Array.

if (left < length and right <= length and $vertexVal.fetch(verticesArray[right]) < $vertexVal.fetch(verticesArray[left]))
	smallest = right
elsif (left <= length)
	smallest = left
end

And, if the element on the right side of the Hash vertexVal is less than the element on the right side.

$vertexVal.fetch(verticesArray[right]) < $vertexVal.fetch(verticesArray[left])

Then element on the right side of the Hash is the smallest element.

smallest = right

And in the else part, we can assume that the element on the left side of the Hash has the smallest element.

smallest = left

Now, since we got the smallest element. We need to check if the actual root element is greater than the smallest element or not.

if ($vertexVal.fetch(verticesArray[root]) > $vertexVal.fetch(verticesArray[smallest]))
	temp = verticesArray[root]
	verticesArray[root] = verticesArray[smallest]
	verticesArray[smallest] = temp
	heapify(verticesArray, smallest, length)
end

And this is where, we swap the contents of the root element and the smallest element. Assuming the element in the root is greater than the smallest element.

Which shouldn't be. As the root element should always be the smallest element.

Then a recursive call is made to heapify(...) method.

heapify(verticesArray, smallest, length)

And the recursion continues until all the elements are arranged in MinHeap.

In the next line, we would update the value of source element a to 0.

# Replace the value of start vertex to 0.
updateHeap("a",0)

Now, if we see the updateHeap(...) method,

Explanation of def updateHeap(vertex, length) method :

def updateHeap(vertex, length)
	$vertexVal[vertex] = length
	verticesArray = $vertexVal.keys()

	len = (((verticesArray.length-1)-1)/ 2).to_i
	(0..len).reverse_each do |parent|
		heapify(verticesArray, parent, verticesArray.length-1)
	end
	$verticesKeyArray = verticesArray
end

The first thing we do is, replace the value in the Hash vertexVal.

$vertexVal[vertex] = length

Then we follow the same process we followed above. And convert into an Array.

verticesArray = $vertexVal.keys()

Then we call the heapify(...) method. Because we have updated a new value and in that case the Heap has to be rearranged to form a Min-Heap.

Explanation of def primMST() method :

def primMST()
	$vertexVal = {}

	# Vertex to Edge Hash
	vertexToEdge = {}

	# Assign all the initial values as infinity for all the $vertices.
	for v in $vertices
		$vertexVal[v] = (2**(0.size * 8 -2) -1)
	end

	# Call buildHeap() to create the MinHeap
	buildHeap()

	# Replace the value of start vertex to 0.
	updateHeap("a",0)

	# Continue until the Min-Heap is not empty.
	while (!empty())
		# Extract minimum value vertex from Map in Heap
		currentVertex = delete_min()

		# Need to fetch the edge for the vertex and add it to the Minimum Spanning Tree..
		# Just note, the edge for the source vertex will not be added.
		spanningTreeEdge = vertexToEdge[currentVertex]

		if(spanningTreeEdge != nil)
			$result.push(spanningTreeEdge)
		end

		# fetch all the adjacent $vertices and iterate through them.
		for edge in getEdges(currentVertex)
			adjacentVertex = edge.endVertex

			# We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex
			# is greater than this edge length.
			if(containsVertex(adjacentVertex) and getWeight(adjacentVertex) > edge.value)
				# Replace the edge length with this edge weight.
				updateHeap(adjacentVertex, edge.value)
				vertexToEdge[adjacentVertex] = edge
			end
		end
	end
end

1. vertexVal;
   
   The Hash with key as vertex and value as the Edge length. We put this in the Heap.Also we will call the Hash vertexVal as Map in the Heap.


2. vertexToEdge
   
   The Hash with key as vertex and value as the actual Edge.


3. result
   
   The List that stores the final result. i.e. All the edges to be included in the Minimum Spanning Tree.

1. So, firstly we initialise the Hash vertexVal. Which we are going to place in the Heap. Also, we will call the Hash vertexVal as Map in the Heap.
   
   

   vertexVal = {}



2. Then we assign the Hash vertexToEdge, where we will be storing the vertex as key and Edge as value.
   
   

   vertexToEdge = {}



3. The next task is to assign the value infinity to all the vertices in the Hash vertexToEdge.
   
   

   for v in vertices:
   	vertexVal[v] = sys.maxsize

   
   
   
   
   
   We can see the value sys.maxsize initialised to all the vertices. It can be said as infinity as it has a very large value that can be compared with infinity.


4. Next, we call the build_heap(...) method . That will create the Heap for us, by placing the elements in the right order.
   
   

   buildHeap()

   
   
   Just remember, in a Min-Heap the root element is always smaller than its left and right child.


5. Then we replace the value of the start element to 0 by calling the updateHeap(...) method.
   
   

   updateHeap("a",0)

   
   
   


6. Then we come to the while loop, that continues until the Min-Heap is empty.
   
   

   	
   while (!empty())
   	# Extract minimum value vertex from Map in Heap
   	currentVertex = delete_min()
   	# Need to fetch the edge for the vertex and add it to the Minimum Spanning Tree..
   	# Just note, the edge for the source vertex will not be added.
   	spanningTreeEdge = vertexToEdge[currentVertex]
   	if(spanningTreeEdge != nil)
   		$result.push(spanningTreeEdge)
   	end
   	# fetch all the adjacent $vertices and iterate through them.
   	for edge in getEdges(currentVertex)
   		adjacentVertex = edge.endVertex
   
   		# We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex
   		# is greater than this edge length.
   		if(containsVertex(adjacentVertex) and getWeight(adjacentVertex) > edge.value)
   			# Replace the edge length with this edge weight.
   			updateHeap(adjacentVertex, edge.value)
   			vertexToEdge[adjacentVertex] = edge
   		end
   	end
   end



7. Inside the while loop, the first thing we do is, get the smallest element from the Heap. That is the root element.
   
   Also we delete the root element from the Heap at the same time.
   
   And the delete_min() method of the Heap does the work for us.
   
   

   currentVertex = delete_min()

   
   
   Since, the vertex a has the smallest value i.e. 0. It is deleted from vertexVal. i.e. Heap in the Map.
   
   


8. Then we go to the Hash vertexToEdge which has the key as vertex and the value as actual Edge. And try getting the Edge for that corresponding vertex (i.e. a).
   
   But in this case, the Hash vertexToEdge has not yet being initialised.
   
   Why is it so ?
   
   Because a is the starting vertex and we won't be adding the starting vertex to the Minimum Spanning Tree.
   
   So, the Edge spanningTreeEdge gets nil and is not added to the Mimimim Spanning Tree.
   
   

   spanningTreeEdge = vertexToEdge[currentVertex]
   if(spanningTreeEdge != nil)
   	$result.push(spanningTreeEdge)
   end



9. The next task we have done is getting the adjacent vertices and iterate through and get the corresponding Edges for the vertices.
   
   And the getEdges() method helps us getting the Adjacent Edges of the vertex a.
   
   
   
   
   

   for edge in getEdges(currentVertex)
   	adjacentVertex = edge.endVertex
   
   	# We check if adjacent vertex exist in Map in Heap and length of the edge is with this vertex
   	# is greater than this edge length.
   	if(containsVertex(adjacentVertex) and getWeight(adjacentVertex) > edge.value)
   		# Replace the edge length with this edge weight.
   		updateHeap(adjacentVertex, edge.value)
   		vertexToEdge[adjacentVertex] = edge
   	end
   end



10. Once we have the first Adjacent Edge i.e. a,b,
    
    
    
    
    We would only take the end vertex from it. And edge object already has the endVertex.
    
    

    adjacentVertex = edge.endVertex



11. Now, that we got the adjacentVertex i.e. b. The next thing we check is, if this adjacentVertex i.e. b, exist in Map in Heap and also check, if the value of the edge length associated with this vertex i.e. The value associated with vertex b is greater than this edge length i.e. The length of edge a,b. Which is 1.
    
    
    
    
    So, we find that vertex b is present in vertexVal i.e. Map in heap.
    
    And the value of b in vertexVal i.e. Map in heap is ∞. Which is greater that the value of the edge i.e. 1.
    
    So, the if condition is satisfied and we get into the if block.
    
    

    	if(containsVertex(adjacentVertex) and getWeight(adjacentVertex) > edge.value)
    		# Replace the edge length with this edge weight.
    		updateHeap(adjacentVertex, edge.value)
    		vertexToEdge[adjacentVertex] = edge
    	end



12. Now, since we are in the blocks of if statement, we had updated the vertex with the new value of the Edge i.e. 1.
    
    

    updateHeap(adjacentVertex, edge.value)
    
    Similarly, we put the actual edge i.e. a,b to the value of vertex b in the Hash
    vertexToEdge that stores vertex as key and the Edge associated to it as value.
    vertexToEdge[adjacentVertex] = edge

    
    
    

Time Complexity of Prim's Algorithm for Minimum Spanning Tree