COP 3530
Section U02
Fall 2013

                    PRIMS'S ALGORITHM
                    =================


 /**
 *
 * @author pelina
 */
public class Main {
   
    // define infinity
    private static final double INFINITY = Double.MAX_VALUE;
    private static final int SIZE = 6; // the number of nodes
    // a driver for prim
    public static void main(String[] args) {
        
    // create the weight array
    double[][] weight = { {0, 10, INFINITY, 30, 45, INFINITY},
        {10, 0, 50, INFINITY, 40, 25}, {INFINITY, 50, 0, INFINITY, 35, 15},
        {30, INFINITY, INFINITY, 0, INFINITY, 20},{45, 40, 35, INFINITY, 0, 55},
        {INFINITY, 25,15,20,55,0}};
        
    // create the edge array
    int[][] e = { {0,1}, {0,3}, {0,4}, {1,2}, {1,4}, {1,5}, {2,4}, {2,5},
        {3,5}, {4,5}};
        
    // the tree array
    int[][] tree = new int[SIZE-1][2];

    System.out.println("The cost matrix is ");
    printCostMatrix(weight);
        
    System.out.println("\n\nThe minimal spanning tree costs " + prim(e,weight,tree));
        
    System.out.println("\n\nThe tree is ");
    for (int i = 0; i < SIZE -1; i++)
        System.out.println(tree[i][0] + "-------->" + tree[i][1]);

        
    }

    // the node are 0, 1, 2, ... , n-1
    // edge ia an e X 2 array where e is the number of edges
    // edge[i][0] = u and edge[i][1] = v means that the i-th edge is between nodes u and v
    // cost is the cost matrix. c[i][j] is the cost of the edge i---j
    // it satisfies the equalities c[i][i] = 0 and c[i][j] = c[j][i]
    // if there is no edge from i to j the cost is INFINITY
    // t is the tree represented as a set of edges
    // the method returns the cost of the tree
    public static double prim(int edge[][], double cost[][], int t[][] )
    {
        double minCost = 0.0; // the minimal cost of the tree
        int n = cost.length; // the number of nodes
        int[] near = new int[n];
        
        // find the minimal cost edge
        int k = edge[0][0],
            l = edge[0][1]; // the nodes of the first edge 
        for (int i = 1; i < edge.length; i++)
        {
            // get the nodes of edge[i]
            int u = edge[i][0];
            int v = edge[i][1];
            if (cost[u][v] < cost[k][l])
            {
                k = u;
                l = v;
            }                
        }
        
        if ( cost[k][l] == INFINITY)
            throw new IllegalArgumentException("There is no spanning tree");
        // update minCost and t
        minCost += cost[k][l];
        t[0][0] = k;
        t[0][1] = l;
        
        // initialize near

        for (int i = 0; i < n; i++)
        {
            if (cost[i][k] < cost[i][l])
                near[i] = k;
            else
                near[i] = l; 
        }
         
        near[k] = near[l] = -1;
         
     
        // find n-2 other edges
        for (int i = 1; i < n - 1; i++)
        {
            // find a j such that near[j] != -1 and cost[i][near[i]] is minimal
            int min = -1;
            for ( int j = 0; j < n; j++)
            {
                if ( near[j] != -1 && cost[j][near[j]] != INFINITY)
                {
                    if (min == -1 || cost[min][near[min]] > cost[j][near[j]])
                        min = j;
                }
            }    
            
            if (min == -1)
                throw new IllegalArgumentException("There no spanning tree");
            
            // add the edge to the tree and update minCost
            minCost += cost[min][near[min]];
            t[i][0] = min;
            t[i][1] = near[min];
            
            // update near;
            near[min] = -1;
            for ( int u  = 0; u < n; u++)
            {
                if (near[u] != -1 && cost[u][min] < cost[u][near[u]])
                    near[u] = min;                
            }

        }    
            
        return minCost;
        
    }
    
    // print the cost matrix
    public static void printCostMatrix(double[][] c)
    {
        System.out.printf("The cost matrix c[i,j]\n");
        System.out.printf(" i/ j");
        // print header
        for (int i = 0; i < c.length; i++)
            System.out.printf("%6d", i);
        // print the matrix
        for (int i = 0; i < c.length; i++)
        {
            System.out.printf("\n%2d   ", i);
            for (int j = 0 ; j < c.length; j++)
                if ( c[i][j] == INFINITY)
                    System.out.printf("%6s", "INF");
                else
                    System.out.printf("%6.1f", c[i][j]);
        }
    }    

}    



/* The output:
The cost matrix is 
The cost matrix c[i,j]
 i/ j     0     1     2     3     4     5
 0      0.0  10.0   INF  30.0  45.0   INF
 1     10.0   0.0  50.0   INF  40.0  25.0
 2      INF  50.0   0.0   INF  35.0  15.0
 3     30.0   INF   INF   0.0   INF  20.0
 4     45.0  40.0  35.0   INF   0.0  55.0
 5      INF  25.0  15.0  20.0  55.0   0.0

The minimal spanning tree costs 105.0


The tree is 
0-------->1
5-------->1
2-------->5
3-------->5
4-------->2
BUILD SUCCESSFUL (total time: 0 seconds)
*/