// Dijkstra'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 <code>Dijkstra</code> implements Dijkstra's algorithm
 * with the customary priority queue, using a standard binary heap
 * (with decreaseKey). The interface <code>ShortestPathAlgorithm</code>
 * defines signatures of methods for single-source and all-pairs 
 * shortest-paths.
 *
 * @see ShortestPathAlgorithm
 */

public class Dijkstra implements ShortestPathAlgorithm {

  // 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.

  GraphPath[][] paths;               // paths[i][j] = shortest path from vertex
                                     // i to vertex j. GraphPath is a list of edges.


  //---------------- Algorithm interface ------------------------------------

  public String getName ()
  {
    return "Dijkstra";
  }


  public void setPropertyExtractor (int algID, PropertyExtractor props)
  {
    this.algID = algID;
    this.props = props;
  }


  //---------------- ShortestPathAlgorithm interface -----------------------

  public void initialize (int numVertices)
  {
    this.numVertices = numVertices;
    paths = new GraphPath [numVertices][];
    for (int i=0; i < numVertices; i++)
      paths[i] = new GraphPath [numVertices];
    predecessor = new int [numVertices];
    predecessorEdgeWeight = new double [numVertices];
  }

  
  public GraphPath[] singleSourceShortestPaths (double[][] adjMatrix, int source)
  {
    this.adjMatrix = adjMatrix;

    // All the work is done here:
    return singleSourceShortestPaths (source);
  }
  


  public GraphPath[] singleSourceShortestPaths (int source)
  {
    // 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];
    for (int i=0; i<numVertices; i++) {
      GraphVertex vertex = new GraphVertex (i);
      vertices[i] = vertex;
      if (i != source) {
        vertex.setKey (Double.MAX_VALUE);
        predecessor[i] = -1;
      }
      else {
        vertex.setKey (0);
        predecessor[i] = i;
      }
      priorityQueue.insert (vertex);
    }
    

    // Now process vertices one by one in order of priority (which changes
    // during the course of the iteration.

    while (! priorityQueue.isEmpty() ) {

      // Extract vertex with smallest priority value.
      GraphVertex vertex = (GraphVertex) priorityQueue.extractMin ();

      // For readability we'll use these shortcuts.
      int v = vertex.vertexID;
      double v_key = vertex.getKey();
      
      // Scan neighbors in adjMatrix.

      for (int i=0; i<numVertices; i++) {

        // Look at row adjMatrix[v][i].
        if ( (v != i) && (adjMatrix[v][i] > 0) ) {

          // We have found a neighbor: relax 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() > v_key + w) {

            // decreaseKey operation.
            priorityQueue.decreaseKey (vertices[i], v_key+w);

            // Record predecessor to build SPT later.
            predecessor[i] = v;

          }

        }

      } //endfor
      
    }
    

    // Next, we need to build the paths. 
    GraphPath path = null;
    // path.edgeList[k] = k-th edge in path.

    for (int i=0; i < numVertices; i++) {

      if (i != source) {

        // Find path from source to i and place that in paths[source][i]
        // in reverse order (walking back from i).

        // ... (not shown) ...


      } // endif
    } // endfor
    
    return paths[source];
  }
  

  public GraphPath[][] allPairsShortestPaths (double[][] adjMatrix)
  {
    // We are using an adjacency matrix.
    useMatrix = true;

    this.adjMatrix = adjMatrix;
    
    // Consistency check:
    if (numVertices != adjMatrix.length) {
      System.out.println ("ERROR: adjMatrix length=" + adjMatrix.length + " not equal to numVertices=" + numVertices);
      return null;
    }

    // Now, compute shortest paths, one source at a time.
    for (int source=0; source < numVertices; source++) {
      singleSourceShortestPaths (source);
    }

    return paths;
  }
  

  public GraphPath[] singleSourceShortestPaths (GraphVertex[] adjList, int source)
  {
    // ... (not shown) ...
    return null;
  }
  
  
  public GraphPath[][] allPairsShortestPaths (GraphVertex[] adjList)
  {
    // ... (not shown) ...
    return paths;
  }
  

  public GraphPath[] singleSourceShortestPathsAdjList (int source)
  {
    // ... (not shown) ...
    return paths;
  }


  public double getPathWeight (int source, int dest)
  {
    // ... (not shown) ...
    return 0;
  }
  
  
  public GraphPath getPath (int source, int dest)
  {
    return paths[source][dest];
  }


}