/* File: Graph.java - May 2011 */
package l25;
import java.util.ArrayList;

/**
 *  Represents a weighted graph via its adjacencies. Includes methods
 *  for shortest paths, and minimal spanning trees. In principal could
 *  be used for directed case, but at the moment assumes the graph to
 *  be undirected.
 *
 *  @author Michael Albert
 *
 */

public class Graph{

   private static final int NOT_VISITED = -1;

   Vertex[] vertices;
   ArrayList<Edge> edges = new ArrayList<Edge>();

   public Graph() {}

   public Graph(int size) {
      vertices = new Vertex[size];
      for(int i = 0; i < size; i++) {
         vertices[i] = new Vertex(i);
      }
   }

   public int size() {
      return vertices.length;
   }

   public void removeEdges() {
      for(int i = 0; i < vertices.length; i++) {
         vertices[i] = new Vertex(i);
      }
      edges.clear();
   }


   public void addEdge(int i, int j) {
      addWeightedEdge(i,j,1);
   }

   public void addWeightedEdge(int i, int j, int weight) {
      Edge e = new Edge(i, j, weight);
      edges.add(e);
      vertices[i].addEdge(e);
      vertices[j].addEdge(e.reverse());
   }

   public int[] computeDistances(int v) {
      int[] distances = new int[vertices.length];
      for(int i = 0; i < distances.length; ++i) {
         distances[i] = NOT_VISITED;
      }
      distances[v] = 0;
      PriorityQueue<Edge> q = new PriorityQueue<Edge>();
      for(Edge e: vertices[v].edges) {
         q.add(e, -e.weight);
      }
      while (!q.isEmpty()) {
         Edge e = q.removeNext();
         if (distances[e.finish] == NOT_VISITED) {
            distances[e.finish] = distances[e.start]+ e.weight;
            for(Edge f: vertices[e.finish].edges) {
               q.add(f, -distances[e.finish]-f.weight);
            }
         }
      }
      return distances;
   }


   public Edge[] dijkstra(int v) {
      int[] distances = new int[vertices.length];
      Edge[] result = new Edge[vertices.length-1];
      boolean[] visited = new boolean[vertices.length];
      for(int i = 0; i < vertices.length; i++) {
         visited[i] = false;
      }
      visited[v] = true;
      int resultIndex = 0;
      PriorityQueue<Edge> q = new PriorityQueue<Edge>();
      for(Edge e: vertices[v].edges) {
         q.add(e, -e.weight);
      }
      while (!q.isEmpty()) {
         Edge e = q.removeNext();
         if (!visited[e.finish]) {
            visited[e.finish] = true;
            distances[e.finish] = distances[e.start] + e.weight;
            result[resultIndex] = e;
            resultIndex++;
            for(Edge f: vertices[e.finish].edges) {
               q.add(f, -distances[e.finish]-f.weight);
            }
         }
      }
      return result;
   }


   public Edge[] prim(int v) {
      Edge[] result = new Edge[vertices.length-1];
      boolean[] visited = new boolean[vertices.length];
      for(int i = 0; i < vertices.length; i++) {
         visited[i] = false;
      }
      visited[v] = true;
      int resultIndex = 0;
      PriorityQueue<Edge> q = new PriorityQueue<Edge>();
      for(Edge e: vertices[v].edges) {
         q.add(e, -e.weight);
      }
      while (!q.isEmpty()) {
         Edge e = q.removeNext();
         if (!visited[e.finish]) {
            visited[e.finish] = true;
            result[resultIndex] = e;
            resultIndex++;
            for(Edge f: vertices[e.finish].edges) {
               q.add(f, -f.weight);
            }
         }
      }
      return result;
   }

   public String toString() {
      StringBuilder result = new StringBuilder();
      for(int i = 0; i < vertices.length; i++) {
         result.append(vertices[i].toString());
         result.append('\n');
      }
      result.deleteCharAt(result.length()-1);
      return result.toString();
   }

   public static Graph randomGraph(int size, double p) {
      Graph result = new Graph(size);
      for(int i = 0; i < size; i++) {
         for(int j = i+1; j < size; j++) {
            if (Math.random() < p) {
               result.addEdge(i,j);
            }
         }
      }
      return result;
   }

   public static Graph randomGraph(int size, int edges) {
      Graph result = new Graph(size);
      double edgesRemaining = size*(size-1)/2;
      for(int i = 0; i < size; i++) {
         for(int j = i+1; j < size; j++) {
            if (Math.random() < edges/edgesRemaining) {
               result.addEdge(i,j);
               edges--;
            }
            edgesRemaining--;
         }
      }
      return result;
   }
   
   private class Vertex{
    
      private ArrayList<Edge> edges;
      private int label;

      private Vertex(int label) {
         this.label = label;
         edges = new ArrayList<Edge>();
      }

      private void addEdge(Edge e) {
         if (!edges.contains(e)) edges.add(e);
      }

      private ArrayList<Edge> getEdges(){
         return edges;
      }

      public String toString() {
         StringBuilder result = new StringBuilder(label + ": ");
         for(Edge e: this.edges){

            result.append(e.finish + "(" + e.weight + ") ");
         }
         return result.toString();
      }

   }
}