Saturday, November 28, 2015

Prim's Algorithm : Eager Implementation using Fibonacci Heap - Java

Fibonacci Heap source from : http://graphstream-project.org/api/gs-algo/org/graphstream/algorithm/util/FibonacciHeap.html#decreaseKey(org.graphstream.algorithm.util.FibonacciHeap.Node, K)

Eager Implementation : 

import java.util.ArrayList;
import org.graphstream.algorithm.util.FibonacciHeap;

public class PrimsEager {
    boolean marked[];
    ArrayList<ArrayList<Edge>> graph;
    ArrayList<Edge> mst;
    
    double distTo[];
    int edgeTo[];
    
    int E, V;
    
    PrimsEager(int v){
        V = v;
        graph = new ArrayList<>();
        for(int i=0;i<v;++i)graph.add(new ArrayList<>());
        distTo = new double[V];
        edgeTo = new int[V];
        mst = new ArrayList<>();
        marked = new boolean[V];
    }
    
    public void applyPrims(int start){
        boolean[] checkAddedNode = new boolean[V];
        marked[start] = true;
        distTo[start] = 0;
        FibonacciHeap<Double, Integer> pq = new FibonacciHeap<>();
        FibonacciHeap.Node n = pq.add(0.0, start);
        FibonacciHeap.Node nodes[] = new FibonacciHeap.Node[V];
        nodes[start] = n;
        
        while(!pq.isEmpty()){ 
            int node = pq.extractMin(); 
            
            /*
                The statement below is necessary, otherwise
                some node may wrongly update the new shorter path
                for a node that has been already processed and
                discarded from the priority queue. (Node 3 in this graph, for example.)
            */
            checkAddedNode[node] = true;
            
            System.out.println("\nRemoved "+node); 
            
            for(Edge w:graph.get(node)){
                int V = w.other(node); 
                if(!marked[V]){
                    marked[V] = true;
                    
                    /*
                      Save the reference to the PriorityQueue Node so that
                      decreaseKey can be performed 
                    */
                    nodes[V] = pq.add(w.weight(), V);  
                    
                    /*
                       distance to the nearest MST node.
                    */
                    distTo[V] = w.weight();
                    
                    /*
                        what node is it.
                    */
                    edgeTo[V] = node;
                    
                    System.out.println("\nSet distTo["+V+"] to "+distTo[V]);
                    System.out.println("Added "+V+" : "+distTo[V]); 
                }else if(!checkAddedNode[V] && distTo[V] > w.weight()){ 
                    //A better path to this node has been found
                    //Need to update (decrease) priority (distanceTo value)
                    
                    System.out.println("\n V = "+V+" old = "+distTo[V]+" new = "+w.weight());
//                   
                    distTo[V] = w.weight();
                    
                    System.out.println("distTo["+V+"] = "+distTo[V]+" new value = "+distTo[V]);
                    
                    pq.decreaseKey(nodes[V], distTo[V]);
                    edgeTo[V] = node;
                    
                    System.out.println("edgeTo["+V+"] = "+node); 
                }
            } 
        }
        
        System.out.println("MST Edges : ");
        for(int i=0;i<V;++i){
            if(i==start)continue;
            System.out.println(i+" - "+edgeTo[i]);
        }
    }
    
    public void addEdge(int v, int w, double weight){
        Edge e = new Edge(v, w, weight);
        graph.get(v).add(e);
        graph.get(w).add(e);
        E++;
    }
    
    public static void main(String[] args){
        PrimsEager prims = new PrimsEager(8);
        prims.addEdge(0, 7, 0.16);
        prims.addEdge(2, 3, 0.17);
        prims.addEdge(1, 7, 0.19);
        prims.addEdge(0, 2, 0.26);
        prims.addEdge(5, 7, 0.28);
        prims.addEdge(1, 3, 0.29);
        prims.addEdge(1, 5, 0.32);
        prims.addEdge(2, 7, 0.34);
        prims.addEdge(4, 5, 0.35);
        prims.addEdge(1, 2, 0.36);
        prims.addEdge(4, 7, 0.37);
        prims.addEdge(0, 4, 0.38);
        prims.addEdge(6, 2, 0.40);
        prims.addEdge(3, 6, 0.52);
        prims.addEdge(6, 0, 0.58);
        prims.addEdge(6, 4, 0.93);
         
        prims.applyPrims(0);
    }
}

Output :

Removed 0

Set distTo[7] to 0.16
Added 7 : 0.16

Set distTo[2] to 0.26
Added 2 : 0.26

Set distTo[4] to 0.38
Added 4 : 0.38

Set distTo[6] to 0.58
Added 6 : 0.58

Removed 7

Set distTo[1] to 0.19
Added 1 : 0.19

Set distTo[5] to 0.28
Added 5 : 0.28

 V = 4 old = 0.38 new = 0.37
distTo[4] = 0.37 new value = 0.37
edgeTo[4] = 7

Removed 1

Set distTo[3] to 0.29
Added 3 : 0.29

Removed 2

 V = 3 old = 0.29 new = 0.17
distTo[3] = 0.17 new value = 0.17
edgeTo[3] = 2

 V = 6 old = 0.58 new = 0.4
distTo[6] = 0.4 new value = 0.4
edgeTo[6] = 2

Removed 3

Removed 5

 V = 4 old = 0.37 new = 0.35
distTo[4] = 0.35 new value = 0.35
edgeTo[4] = 5

Removed 4

Removed 6
MST Edges : 
1 - 7
2 - 0
3 - 2
4 - 5
5 - 7
6 - 2
7 - 0

No comments:

Post a Comment