In Prim's algorithm, it is recommended to maintain the invariant in the following way :
When a vertice v is added to the MST:
For each edge (v,w) in the unexplored tree:
1. Delete w from the min heap.
2. Recompute the key[w] (i.e. it's value from the unexplored tree
to the explored one).
3. Add the value back to the heap.
So, basically this involves deletion from the heap (and heapify which takes O(logn)) and then reinserting (again O(logn))
Instead, if I use the following approach:
For each edge (v,w) in the unexplored tree:
1. Get the position of the node in the heap(array) using HashMap -> O(1)
2. Update the value in place.
3. Bubble up or bubble down accordingly. -> O(logn)
Which gives better constants than the previous one.
The controversial part is the 3rd part where Im supposed to bubble up or down.
My implementation is as follows :
public int heapifyAt(int index){
// Bubble up
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
// Bubble down
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
return index;
}
And I'am plucking from the heap this way :
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF; // set this to infinity, so it'll be at the bottom
// of the heap.
heapifyat(0);
visited.add(minNodeNumber);
updatevertices(minNodeNumber); // Update the adjacent vertices
return toRet;
}
And updating the plucked vertices this way :
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){ // Skip the nodes that are already visited
int positionInHeap = map.get(adjacentNode.nodeNumber); // Retrive the position from HashMap
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
heap[positionInHeap].edgeCost = adjacentNode.edgeCost; // Update if the cost is better
heapifyAt(positionInHeap); // Now this will go bottom or up, depending on the value
}
}
}
}
But when I execute it on large graph, the code fails, There are small values in the bottom of heap and large values at the top. But the heapifyAt() API seems to work fine. So I am unable to figure out is my approach wrong or my code? Moreover, if I replace the heapifyAt() API by siftDown(), i.e. construct the heap, it works fine, but it doesnt make sense calling siftDown() that takes O(n) time for every updates which can be processed in logarithmic time.
In short : Is it possible to update the values in Heap both way, or the algorithm is wrong, since that's why it is recommended to first remove the element from Heap and reinsert it.
EDIT : Complete code:
public class Graph1{
public static final int INF = 9999999;
public static final int NEGINF = -9999999;
static class AdjNode{
int nodeNumber;
int edgeCost;
AdjNode next;
AdjNode(int nodeNumber, int edgeCost){
this.nodeNumber = nodeNumber;
this.edgeCost = edgeCost;
}
}
static class AdjList implements Iterable<AdjNode>{
AdjNode head;
AdjList(){
}
public void add(int to, int cost){
if(head==null){
head = new AdjNode(to, cost);
}else{
AdjNode temp = head;
while(temp.next!=null){
temp = temp.next;
}
temp.next = new AdjNode(to, cost);
}
}
public Iterator<AdjNode> iterator(){
return new Iterator<AdjNode>(){
AdjNode temp = head;
public boolean hasNext(){
if(head==null){
return false;
}
return temp != null;
}
public AdjNode next(){
AdjNode ttemp = temp;
temp = temp.next;
return ttemp;
}
public void remove(){
throw new UnsupportedOperationException();
}
};
}
public void printList(){
AdjNode temp = head;
if(head==null){
System.out.println("List Empty");
return;
}
while(temp.next!=null){
System.out.print(temp.nodeNumber + "|" + temp.edgeCost + "-> ");
temp = temp.next;
}
System.out.println(temp.nodeNumber + "|" + temp.edgeCost);
}
}
static class Heap{
int size;
AdjNode[] heap;
Graph g;
int pluckSize;
Set<Integer> visited = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<>();
Heap(){
}
Heap(Graph g){
this.g = g;
this.size = g.numberOfVertices;
this.pluckSize = size - 1;
heap = new AdjNode[size];
copyElements();
constructHeap();
}
public void copyElements(){
AdjList first = g.list[0];
int k = 0;
heap[k++] = new AdjNode(0, NEGINF); //First entry
for(AdjNode nodes : first){
heap[nodes.nodeNumber] = nodes;
}
for(int i=0; i<size; i++){
if(heap[i]==null){
heap[i] = new AdjNode(i, INF);
}
}
}
public void printHashMap(){
System.out.println("Priniting HashMap");
for(int i=0; i<size; i++){
System.out.println(i + " Pos in heap :" + map.get(i));
}
line();
}
public void line(){
System.out.println("*******************************************");
}
public void printHeap(){
System.out.println("Printing Heap");
for(int i=0; i<size; i++){
System.out.println(heap[i].nodeNumber + " | " + heap[i].edgeCost);
}
line();
}
public void initializeMap(){
for(int i=0; i<size; i++){
map.put(heap[i].nodeNumber, i);
}
}
public void swap(int one, int two){
AdjNode first = heap[one];
AdjNode second = heap[two];
map.put(first.nodeNumber, two);
map.put(second.nodeNumber, one);
AdjNode temp = heap[one];
heap[one] = heap[two];
heap[two] = temp;
}
public void constructHeap(){
for(int i=size-1; i>=0; i--){
int temp = i;
while(heap[temp].edgeCost < heap[(int)Math.floor(temp/2)].edgeCost){
swap(temp, (int)Math.floor(temp/2));
temp = (int)Math.floor(temp/2);
}
}
initializeMap();
}
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){
int positionInHeap = map.get(adjacentNode.nodeNumber);
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
// //System.out.println(adjacentNode.nodeNumber + " not visited, Updating vertice " + heap[positionInHeap].nodeNumber + " from " + heap[positionInHeap].edgeCost + " to " + adjacentNode.edgeCost);
// heap[positionInHeap].edgeCost = INF;
// //heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
// int heapifiedIndex = heapifyAt(positionInHeap); // This code follows my logic
// heap[heapifiedIndex].edgeCost = adjacentNode.edgeCost; // (which doesnt work)
// //heapifyAt(size - 1);
heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
//heapifyAt(positionInHeap);
constructHeap(); // When replaced by SiftDown,
} // works as charm
}
}
}
public void printSet(){
Iterator<Integer> it = visited.iterator();
System.out.print("Printing set : [");
while(it.hasNext()){
System.out.print((int)it.next() + ", ");
}
System.out.println("]");
}
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF;
constructHeap();
visited.add(minNodeNumber);
updatevertices(minNodeNumber);
return toRet;
}
public int heapifyAt(int index){
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
if(index*2 + 2 < size){
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
}
return index;
}
}
static class Graph{
int numberOfVertices;
AdjList[] list;
Graph(int numberOfVertices){
list = new AdjList[numberOfVertices];
for(int i=0; i<numberOfVertices; i++){
list[i] = new AdjList();
}
this.numberOfVertices = numberOfVertices;
}
public void addEdge(int from, int to, int cost){
this.list[from].add(to, cost);
this.list[to].add(from, cost);
}
public void printGraph(){
System.out.println("Printing Graph");
for(int i=0; i<numberOfVertices; i++){
System.out.print(i + " = ");
list[i].printList();
}
}
}
public static void prims(Graph graph, Heap heap){
int totalMin = INF;
int tempSize = graph.numberOfVertices;
while(tempSize>0){
AdjNode min = heap.pluck();
totalMin += min.edgeCost;
System.out.println("Added cost : " + min.edgeCost);
tempSize--;
}
System.out.println("Total min : " + totalMin);
}
public static void main(String[] args) throws Throwable {
Scanner in = new Scanner(new File("/home/mayur/Downloads/PrimsInput.txt"));
Graph graph = new Graph(in.nextInt());
in.nextInt();
while(in.hasNext()){
graph.addEdge(in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
}
Heap heap = new Heap(graph);
prims(graph, heap);
}
}
