/*
    Graph.java
    CIS 260
    David Klick
    4/8/12

    This class implements Graph routines including
    minimal spanning tree and shortest path.
*/

import java.util.*;

public class Graph {

   private boolean DIRECTED = false;
   private boolean WEIGHTED = false;
   private ArrayList<Vertex> vertexList = new ArrayList<Vertex>();
   private ArrayList<ArrayList<Double>> adjacencyMatrix = new ArrayList<ArrayList<Double>>();
   private ArrayList<ArrayList<Edge>> adjacencyList = new ArrayList<ArrayList<Edge>>();

   class Vertex {
      private String name;
      public boolean visited;         // used in isPath
      public boolean inTree;          // used in MST alg
      public double minWeight;        // for shortest path alg
      public boolean weightFound;     // for shortest path alg
      public ArrayList<Integer> minPath; // for shortest path alg
      public Vertex(String s) { name = s; }
      public String getName() { return name; }
      public String toString() { return name; }
   }

   class Edge implements Comparable<Edge> {
      public int src, dest;
      public double weight;
      public String description;
      Edge(int s, int d, double w) { src = s; dest = d; weight = w; description = ""; }
      Edge(int s, int d, double w, String desc) { src = s; dest = d; weight = w; description = desc; }
      public int compareTo(Edge e) { 
         if (weight < e.weight) return -1;
         else if (weight > e.weight) return 1;
         else return 0;
      }
      public String toString() {
         String s = "";
         if (src != -1) s += vertexList.get(src) + "->";
         s += vertexList.get(dest) + " (" + weight + ")";
         return s;
      }
   }

   public Graph() { this(false, false); }
   public Graph(boolean directed) { this(directed, false); }
   public Graph(boolean directed, boolean weighted) {
      DIRECTED = directed;
      WEIGHTED = weighted;
   }

   public int addVertex(String s) {
      int pos = find(s);
      if (pos == -1) {
         vertexList.add(new Vertex(s));

         // create adjacency list and matrix for new vertex
         adjacencyList.add(new ArrayList<Edge>());
         adjacencyMatrix.add(new ArrayList<Double>());

         // make sure there are no edges to new vertex from anywhere else
         for (int i=0; i<vertexList.size()-1; i++) {
            adjacencyMatrix.get(i).add(0.0);
         }

         // set all edges to zero for newly added vertex 
         for (int i=0; i<vertexList.size(); i++) {
            adjacencyMatrix.get(vertexList.size()-1).add(0.0);
         }

         return vertexList.size()-1;
      } else {
         System.err.println("Error: Duplicate vertex found on add: " + s);
         return -1;
      }
   }

   private int find(String s) {
      for (int i=0; i<vertexList.size(); i++) {
         if (vertexList.get(i).getName().equals(s)) return i;
      }
      return -1;
   }

   public boolean addEdge(String src, String dest) {
      return addEdge(src, dest, 1, "");
   }

   public boolean addEdge(String src, String dest, String desc) {
      return addEdge(src, dest, 1, desc);
   }

   public boolean addEdge(String src, String dest, double weight) {
       return addEdge(src, dest, weight, "");
   }

   public boolean addEdge(String src, String dest, double weight, String desc) {
      int posSrc = find(src);
      if (posSrc == -1) posSrc = addVertex(src);
      int posDest = find(dest);
      if (posDest == -1) posDest = addVertex(dest);
      return addEdge(posSrc, posDest, weight, desc);
   }

   private boolean addEdge(int posSrc, int posDest) {
      return addEdge(posSrc, posDest, 1, "");
   }

   private boolean addEdge(int posSrc, int posDest, double weight) {
      return addEdge(posSrc, posDest, weight, "");
   }

   private boolean addEdge(int posSrc, int posDest, String desc) {
      return addEdge(posSrc, posDest, 1, desc);
   }

   private boolean addEdge(int posSrc, int posDest, double weight, String desc) {
      if (!WEIGHTED || weight==0) weight = 1;

      // check for existing edges (parallel edges not allowed in this implementation)
      if (adjacencyMatrix.get(posSrc).get(posDest) != 0) {
         System.err.println("Error: Edge already exists: " + vertexList.get(posSrc)
            + "->" + vertexList.get(posDest) + " ("
            + adjacencyMatrix.get(posSrc).get(posDest) + ")");
         return false;
      }
      if (!DIRECTED && adjacencyMatrix.get(posDest).get(posSrc) != 0) {
         System.err.println("Error: Edge already exists: " + vertexList.get(posDest)
            + "->" + vertexList.get(posSrc) + " ("
            + adjacencyMatrix.get(posDest).get(posSrc) + ")");
         return false;
      }
      
      // set weights in adjacency matrix
      adjacencyMatrix.get(posSrc).set(posDest, weight);
      if (!DIRECTED) adjacencyMatrix.get(posDest).set(posSrc, weight);

      // update adjacency list
      adjacencyList.get(posSrc).add(new Edge(posSrc, posDest, weight, desc));
      if (!DIRECTED) adjacencyList.get(posDest).add(new Edge(posDest, posSrc, weight, desc));
      return true;
   }

   public String toString() {
      String s = "----- Graph listing -----\n\nList of vertices:\n";
      for (int i=0; i<vertexList.size(); i++) {
         s += vertexList.get(i) + " (" + i + ")\n";
      }

      s += "\nAdjacency list:\n";
      for (int i=0; i<vertexList.size(); i++) {
         s += vertexList.get(i) + ": ";
         for (int j=0; j<adjacencyList.get(i).size(); j++) {
            Edge e = adjacencyList.get(i).get(j);
            s += ((j>0?", ":"") + e);
         }
         s += "\n";
      }

      s += "\nAdjacency Matrix\n     ";
      for (int j=0; j<adjacencyMatrix.get(0).size(); j++) {
         s += String.format("%3s ", vertexList.get(j).getName());
      }
      s += "\n";
      for (int i=0; i<adjacencyMatrix.size(); i++) {
         s += String.format("%3s: ", vertexList.get(i).getName());
         for (int j=0; j<adjacencyMatrix.get(i).size(); j++) {
            s += String.format("%3d ", adjacencyMatrix.get(i).get(j).intValue());
         }
         s += "\n";
      }
      return s + "\n----- End of graph listing ---\n";
   }

   // finds an adjacent vertex to v which has not been visited
   public int getAdjacentUnvisited(int v) {
      for (int i=0; i<adjacencyList.get(v).size(); i++) {
         int n = adjacencyList.get(v).get(i).dest;
         if (!vertexList.get(n).visited) return n;
      }
      return -1;
   }

   public boolean isPath(String src, String dest) {
      // default isPath method uses depthFirst search
      return isPath(src, dest, true);
   }

   // use this method to specify depth-first or breadth-first
   public boolean isPath(String src, String dest, boolean depthFirst) {
      // make sure source vertex exists
      int posSrc = find(src);
      if (posSrc == -1) {
         System.out.println("Error: Vertex not found: " + src);
         return false;
      }

      // make sure destination vertex exists
      int posDest = find(dest);
      if (posDest == -1) {
         System.out.println("Error: Vertex not found: " + dest);
         return false;
      }
      
      // check for obvious case of same node
      if (posSrc == posDest) return true;

      // set all vertices to unvisited
      for (int i=0; i<vertexList.size(); i++) {
         vertexList.get(i).visited = false;
      }
      
      // handles both depth-first and breadth-first search
      ArrayList<Integer> v = new ArrayList<Integer>();
      vertexList.get(posSrc).visited = true;
      v.add(posSrc);
      while (!v.isEmpty()) {
         int v1 = depthFirst ? v.remove(v.size()-1) : v.remove(0);
         int v2;
         while ( (v2=getAdjacentUnvisited(v1)) != -1 ) {
            if (v2 == posDest) return true;
            vertexList.get(v2).visited = true;
            v.add(v2);
         }
      }
      return false;
   }

   // This minimal spanning tree algorithm accounts for weighted edges,
   //    but not directed edges
   public String minimumSpanningTree() {
      // check for empty graph
      if (vertexList.size() == 0) return "No MST - empty graph";
      if (DIRECTED) return "This app does not calculate MST for directed graphs";

      // create new graph to contain MST
      Graph mst = new Graph(false, true);

      // populate with all vertices
      for (int i=0; i<vertexList.size(); i++) {
         mst.addVertex(vertexList.get(i).getName());
      }

      // set all vertices to not being in MST
      for (int i=0; i<vertexList.size(); i++) {
         vertexList.get(i).inTree = false;
      }

      int current = 0;  // current vertex
      int ntree   = 0;  // number of vertices connected in MST
      int nverts  = vertexList.size();  // number of vertices
      PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
      Edge e;

      vertexList.get(current).inTree = true;
      ntree++;

      while (ntree < nverts) {
         for (int j=0; j<adjacencyList.get(current).size(); j++) {
            e = adjacencyList.get(current).get(j);
            if (!vertexList.get(e.dest).inTree) pq.add(e);
         }
         if (pq.isEmpty()) return "No MST - graph is not connected";
         
         // add lowest cost edge to MST
         e = pq.poll();
         mst.addEdge(e.src, e.dest, e.weight);
         
         // remove edges from priority queue with same destination
         Iterator<Edge> iter = pq.iterator();
         while (iter.hasNext()) {
            Edge etmp = iter.next();
            if (etmp.dest == e.dest) iter.remove();
         }
         
         current = e.dest;
         vertexList.get(current).inTree = true;
         ntree++;
      }      
      return "\nWeighted MST:\n" + mst + "\n";
   }

   public String shortestPath(String src, String dest) {
       return shortestPath(src, dest, false);
   }

   public String shortestPath(String src, String dest, boolean displayEdgeDescriptions) {
      // make sure source and destination vertices exist
      int posSrc = find(src);
      if (posSrc == -1) return "Error: Source vertex not found: " + src;
      int posDest = find(dest);
      if (posDest == -1) return "Error: Destination vertex not found: " + dest;

      int i, j, v=0;
      for (i=0; i<vertexList.size(); i++) {
         vertexList.get(i).minPath = new ArrayList<Integer>();
         double wgt = adjacencyMatrix.get(posSrc).get(i);
         if (wgt == 0) wgt = Double.MAX_VALUE;
         else {
            if (i != posSrc) vertexList.get(i).minPath.add(posSrc);
            vertexList.get(i).minPath.add(i);
         }
         vertexList.get(i).minWeight = wgt;
         vertexList.get(i).weightFound = false;
      }

      vertexList.get(posSrc).minWeight = 0;
      vertexList.get(posSrc).weightFound = true;

      for (i=0; i<vertexList.size()-1; i++) {
         double minWeight = Double.MAX_VALUE;
         for (j=0; j<vertexList.size(); j++) {
            if (!vertexList.get(j).weightFound) {
               if (vertexList.get(j).minWeight < minWeight) {
                  v = j;
                  minWeight = vertexList.get(v).minWeight;
               }
            }
         }
         vertexList.get(v).weightFound = true;

         for (j=0; j<vertexList.size(); j++) {
            if (!vertexList.get(j).weightFound) {
               double wgt = adjacencyMatrix.get(v).get(j);
               if (wgt != 0 && (minWeight + wgt
                  < vertexList.get(j).minWeight)) {
                  vertexList.get(j).minWeight = minWeight + wgt;
                  vertexList.get(j).minPath = new ArrayList<Integer>();
                  for (int x=0; x<vertexList.get(v).minPath.size(); x++) {
                     vertexList.get(j).minPath.add(vertexList.get(v).minPath.get(x));
                  }
                  vertexList.get(j).minPath.add(j);
               }
            }
         }
      }

      String s = "Shortest path from " + src + " to " + dest + ": ";
      ArrayList<Integer> path = vertexList.get(posDest).minPath;
      int pathSize = path.size();
      if (pathSize == 0) return s + "Not found";

      if (displayEdgeDescriptions) {
         int ndx1 = posSrc;
         for (int x=1; x<pathSize; x++) {
            int ndx2 = path.get(x);
            ArrayList<Edge> elist = adjacencyList.get(ndx1);
            for (Edge e: elist) if (e.dest == ndx2) { s += e.description; break; }
            ndx1 = ndx2;
         }
      } else {
         for (int x=0; x<pathSize; x++) s += path.get(x) + " ";
     }
     return s + "\n";
   }
}