import net.datastructures.Dijkstra;
import net.datastructures.Graph;
import net.datastructures.AdjacencyListGraph;
import net.datastructures.Vertex;
import net.datastructures.Edge;
import net.datastructures.Vector;
import net.datastructures.ArrayVector;
import java.util.Iterator;

/*
 * This class is an example of how to use the implementation of
 * Dijkstra's algorithm provided by the net.datastructures Package.
 * During the initialization procedure, a bunch of vertices and edges
 * are inserted into an adjacency-list graph at random, and each edge
 * is given a weight.  Next, the algorithm is executed.  Finally, the
 * results are printed by printing the distance from the source to
 * every vertex of the graph.
 */

public class DijkstraExample {

  public static void main(String[] args) {
    
    /* INITIALIZATION */

    // the algorithm object
    Dijkstra dijk = new Dijkstra();

    // the input graph
    Graph g = new AdjacencyListGraph();

    // the weight decoration object
    Object WEIGHT = new Object();

    // vector to keep track of vertices
    Vector vertices = new ArrayVector();

    // insert vertices into the graph
    int num = 10;
    for(int i = 0; i < num-1; i++) {
      Vertex vert = g.insertVertex(new Integer(i));
      vertices.insertAtRank(0,vert);
    }
    // the source vertex
    Vertex source = g.insertVertex(new Integer(num-1));
    vertices.insertAtRank(num-1,source);

    // insert edges into the graph
    int num2 = 20;
    for(int i = 0; i < num2; i++) {

      // pick two random vertices
      Vertex u, v;
      int r, s;
      r = randomNumber(num-1,0);
      s = randomNumber(num-1,0);
      u = (Vertex)vertices.elemAtRank(r);
      v = (Vertex)vertices.elemAtRank(s);
      
      // insert the edge between two random vertices
      Edge edge = g.insertEdge(u,v,new Integer(i));

      // set its weight, which *must* be a non-negative Integer
      // object, using the weight decoration object
      edge.put(WEIGHT,new Integer(i));
    }

    // print the input graph
    System.out.println("The Input Graph: ");
    System.out.println(g);
    System.out.println();

    // print the edge weights
    Iterator edges = g.edges();
    while(edges.hasNext()) {

      // get the edge from the iterator
      Edge edge = (Edge)edges.next();

      // get its weight
      Integer weight = (Integer)edge.get(WEIGHT);

      // print the edge and weight
      System.out.println("Edge " + edge + " has weight " + weight);
    }

    System.out.println();

    /* EXECUTING THE ALGORITHM */
    
    // pass the graph, the source vertex, and the weight decoration
    // object to the execute method
    dijk.execute(g,source,WEIGHT);

    /* PRINTING THE RESULTS */

    System.out.println("RESULTS:\n");

    // print the shortest distance from the source to each vertex
    for(int i = 0; i < vertices.size(); i++) {
      Vertex vert = (Vertex)vertices.elemAtRank(i);

      // get the distance from the source to the current vertex
      int dist = dijk.getDist(vert);

      // see if the current vertex is reachable from the source
      if(dist == Integer.MAX_VALUE)
	System.out.println("There is no path between vertex " +
			   source + " and vertex " + vert + ".");
      else
	System.out.println("The shortest path between vertex " + 
			   source + " and vertex " + vert + " has length "+
			   dist + ".");
    }
  }

  // helper function to return a random number in the interval
  // [low,high] (inclusive)
  private static int randomNumber(int high, int low) {
    return low + (int)(Math.random()*(high-low+1));
  }
  
}