// Prim's algorithm with a priority queue (binary heap)
//
// Author: Rahul Simha
// Date: Oct, 2001.
import edu.gwu.algtest.*;
import edu.gwu.util.*;
import edu.gwu.debug.*;
import java.util.*;
import java.io.*;
/**
* Class FastPrim
implements Prim's algorithm but with
* the customary priority-queue. The queue is a standard implementation
* of a binary heap with the decreaseKey operation.
*
* @see SpanningTreeAlgorithm
*/
public class FastPrim implements SpanningTreeAlgorithm {
// Debugging for internal use.
private static final boolean debug = true;
int algID; // Given by test-environment.
PropertyExtractor props; // Properties file.
int numVertices; // Number of vertices (when initialized).
boolean useMatrix; // Adjacency matrix or list?
double[][] adjMatrix; // The adjacency matrix (given as input).
GraphVertex[] adjList; // The adjacency list (given as input).
int[] predecessor; // Store predecessors to build MST.
double[] predecessorEdgeWeight; // Store edge weights as well.
double[][] treeMatrix; // The MST, if required in matrix form.
GraphVertex[] treeList; // The MST, if required in list form.
double treeWeight; // Total weight of tree.
//---------------- Algorithm interface ------------------------------------
public String getName ()
{
return "FastPrim";
}
public void setPropertyExtractor (int algID, PropertyExtractor props)
{
this.algID = algID;
this.props = props;
}
//---------------- SpanningTreeAlgorithm interface -------------------------
public void initialize (int numVertices)
{
this.numVertices = numVertices;
predecessor = new int [numVertices];
predecessorEdgeWeight = new double [numVertices];
}
public double[][] minimumSpanningTree (double[][] adjMatrix)
{
// Consistency check:
if (numVertices != adjMatrix.length) {
System.out.println ("ERROR: adjMatrix length not equal to numVertices");
return null;
}
// We are using an adjacency matrix.
useMatrix = true;
// Create heap. Note: BinaryHeap implements the PriorityQueueAlgorithm
// interface (that has insert, extractMin and decreaseKey operations.
PriorityQueueAlgorithm priorityQueue = new BinaryHeap (numVertices);
priorityQueue.initialize (numVertices);
// Since we are given an adjacency matrix, we need to build vertices
// to use in the priority queue. GraphVertex is a class that holds
// the vertex id and also can hold an edge-list (Therefore, it's
// used for the adjacency-list representation.
// NOTE: most importantly, GraphVertex implements the PriorityQueueNode
// interface that allows the priority queue to store indices inside the node.
GraphVertex[] vertices = new GraphVertex [numVertices];
// Place vertices in priority queue.
for (int i=0; i 0) ) {
// We have found a neighbor: explore the edge (v,i).
double w = adjMatrix[v][i];
// If the current priority is higher, lower it via edge (v,i).
if (vertices[i].getKey() > w) {
// decreaseKey operation.
priorityQueue.decreaseKey (vertices[i], w);
// Record predecessor and weight for building MST later.
predecessor[i] = v;
predecessorEdgeWeight[i] = w;
}
}
} // endfor
} // endwhile
// Create space for tree.
treeMatrix = new double [numVertices][];
for (int i=0; i