import java.util.*;
import java.text.DecimalFormat;
import java.awt.Color;
import java.awt.Graphics;

/**
 *  Graph.java, models graph management and creation.<br>
 *  Implements: GraphInterface.<br>
 *  @author <A HREF="mailto:mem1780@tntech.edu">Matt Markham</A><BR>
 */

public class Graph implements GraphInterface
{
    //size integer variable to keep track of number of nodes in the graph
  private int size;
    //Double two-dimensional array for the adjacency matrix
  private double[][] adjacent;
    //boolean to determine whether a graph is directed
  private boolean directed;
    //Vertex storage list
  private ArrayList vertexList;
    //int to determin generic unweighted value
  private final int UNWEIGHTED_VALUE = 1;
    //temporary Arraylist for dfs
  private ArrayList tempAL=new ArrayList();
    //ArrayList containing the current shortest path
  private ArrayList path;


/**
 *  Default Constructor, creates an undirected graph.<br>
 */

  public Graph ()
  {
     size = 0;
     adjacent = new double[size][size];
     vertexList = new ArrayList();
     directed=false;
     path = new ArrayList();
  }

   
/**
 *  Constructor, takes a boolean to determine directed or undirected.<br>
 */

  public Graph (boolean param)
  {
     size = 0;
     adjacent = new double[size][size];
     vertexList = new ArrayList();
     directed=param;
     path = new ArrayList();
  }

  public void makeEmpty()
  {
    size=0;
    adjacent = new double[size][size];
    vertexList.clear();
  }

  public boolean isEmpty()
  {
    return (size==0);
  }

  
  public int numVertices()
  {
     return size;
  }


  public int numEdges()
  {
    int c=0;
    for(int x=0; x<size;x++)
    {
       for(int y=0;y<size;y++)
       {
          if (!(adjacent[x][y]==(Double.POSITIVE_INFINITY)))
          {
             c++;  //Insert nerdy joke here
          }
       }
     }
  return c;
  }

  public void addVertex (GraphNode myItem) throws GraphException  
  { 
      for(int a=0; a<vertexList.size();a++)  

         if ( ((GraphNode) vertexList.get(a)).getKey().compareTo ( myItem.getKey() ) == 0 )

            throw new GraphException ( "Duplicate entry" );

      size++;  

      vertexList.add(myItem);  

      resizeAdjacent ( vertexList.size() ); 
  }


/**
 *  Method to resize the adjacency matrix.<br>
 *  Preconditions: must be passed a new size value.<br>
 *  Postconditions: resizes adjacency matrix.<br>
 *  Throws: None.
 */

   private void resizeAdjacent ( int size )
   {

      double[][] temp = new double[size][size];  

      for( int x = 0; x < size - 1; x++)

         for ( int y = 0; y < size - 1; y++ )

            temp[x][y] = adjacent[x][y];

         for ( int x = 0; x < size; x++ )
         {

            temp[x][size - 1] = Double.POSITIVE_INFINITY;

            temp[size - 1][x] = Double.POSITIVE_INFINITY;

         }

         adjacent = temp;
   }

  public void addEdge(Comparable searchKey1, Comparable searchKey2, double weight) throws GraphException  
  {  
     for(int x=0; x<size; x++)  
     {  
       if ( ((GraphNode) vertexList.get(x)).getKey().compareTo(searchKey1) == 0 ) 
       {  
          for(int y=0; y<size;y++)  
          {  
             if ( ((GraphNode) vertexList.get(y)).getKey().compareTo(searchKey2) == 0 ) 
             {  
                adjacent[x][y]=weight; 
                return; 
             }//end if get(y)  
          }// end for y
        }//end if get(x)  
     }//end for x  
     throw new GraphException ( "Duplicate found!" ); 
  }

  public void addEdge(Comparable searchKey1, Comparable searchKey2) throws GraphException

  {  
     for(int x=0; x<size; x++)  
     {  
       if ( ((GraphNode) vertexList.get(x)).getKey().compareTo(searchKey1) == 0 ) 
       {  
          for(int y=0; y<size;y++)  
          {  
             if ( ((GraphNode) vertexList.get(y)).getKey().compareTo(searchKey2) == 0 ) 
             {  
                adjacent[x][y]=UNWEIGHTED_VALUE;
                  if(!directed)
                    {adjacent[y][x]=UNWEIGHTED_VALUE;}  
                return; 
             }//end if get(y)  
          }// end for y
        }//end if get(x)  
     }//end for x  
     throw new GraphException ( "Duplicate found!" ); 
  }

  public double getWeight(Comparable searchKey1, Comparable searchKey2) throws GraphException
  {  
     for(int x=0; x<size;x++)  
     {  
        if ( ((GraphNode) vertexList.get(x)).getKey().compareTo(searchKey1) == 0 ) 
        {  
          for(int y=0; y<size;y++)  
          {  
             if ( ((GraphNode) vertexList.get(y)).getKey().compareTo(searchKey2) == 0 ) 
             {  
                return adjacent[x][y]; 
             }//end if get(y)  
          }// end for y
        }//end if get(x)  
     }//end for x  
     throw new GraphException ( "Edge does not exist!"); 
  }

  public GraphNode getVertex(int index) throws GraphException
  {
    if (index>size)
     throw new GraphException ("index out of bounds!");
    else
     return (GraphNode)vertexList.get(index);
  }

  public GraphNode getVertex(Comparable searchKey) throws GraphException
  {
    for (int x=0;x<vertexList.size();x++)
    {
      if ( ((GraphNode) vertexList.get(x)).getKey().compareTo(searchKey) == 0)
      {
         return (GraphNode) vertexList.get(x);
      }
    }
    throw new GraphException ("Vertex not Found in List!");
  }
  
/**
 *  FInds the index of a given searchKey.<br>
 *  Preconditions: Must be passed searchKey.<br>
 *  Postconditions: returns integer index of given searchKey.<br>
 *  Throws:Nonde.
 */

  private int findVertex (Comparable searchKey)
  {
    for (int d=0; d<size;d++)
    {
       if ( ((GraphNode) vertexList.get(d)).getKey().compareTo(searchKey) == 0 )
            { return d; }
    }
       return -1;
  }

/**
 *  Clears all vertices, sets all to be unmarked.<br>
 *  Preconditions: None.<br>
 *  Postconditions: Makes all vertices unmarked.<br>
 *  Throws:None.
 */

  private void clearMarks()
  {
    for (int x=0;x<size;x++)
    {
      ((GraphNode) vertexList.get(x)).setMarked(false);
    }
  }

  public Comparable getSearchKey (int index)
  {
     return ((GraphNode)(vertexList.get(index))).getKey();
  }

  public void removeEdge(Comparable searchKey1, Comparable searchKey2) throws GraphException
  {
    int a=findVertex(searchKey1);
    int b=findVertex(searchKey2);
    if (a==-1 || b==-1)
      throw new GraphException ("Entry not found in list!");
    adjacent[a][b]=Double.POSITIVE_INFINITY;
  }


  public ArrayList bfs (Comparable searchKey) throws GraphException
  {
    GraphNode temp;
    ArrayList searchList = new ArrayList();
    QueueReferenceBased bfsQueue= new QueueReferenceBased();
    bfsQueue.enqueue(vertexList.get(findVertex(searchKey)));
    getVertex(searchKey).setMarked(true);
    searchList.add(getVertex(searchKey));

    while (!bfsQueue.isEmpty())
    {
      temp=(GraphNode)bfsQueue.dequeue();

      for(int g=0;g<size;g++)
      {
        if (adjacent[findVertex(temp.getKey())][g] != Double.POSITIVE_INFINITY && !getVertex(g).isMarked())
        {
          ((GraphNode)vertexList.get(g)).setMarked(true);
          bfsQueue.enqueue(vertexList.get(g));
          searchList.add(getVertex(g));
        }//end if
      }//end for
    }//end while
    clearMarks();
    return searchList;
  }

   public GraphNode removeVertex ( Comparable key ) throws GraphException 
   { 
      int index = -1; 
      for ( int i = 0; i < vertexList.size(); i++ ) 
         if ( ((GraphNode) vertexList.get ( i )).getKey().compareTo ( key ) == 0 ) 
            index = i; 
      if ( index == -1 ) 
         throw new GraphException ( "Vertex not in graph" ); 
      double[][] temp = new double[adjacent.length - 1][adjacent.length - 1]; 
      for ( int row = 0; row < adjacent.length; row++ ) 
      { 
         for ( int col = 0; col < adjacent[0].length; col++ ) 
         { 
            if ( row != index && col != index )
            {
               int newrow = row;
               int newcol = col;
               /* make sure the row/col are not in the row/col of the vertex to be removed */
               if ( row > index )
                  newrow = row - 1;
               if ( col > index )
                  newcol = col - 1;
               temp[newrow][newcol] = adjacent[row][col]; 
            }
         }
      }
      adjacent = temp;
      size--;
      return (GraphNode) vertexList.remove ( index );
   }

  public ArrayList dfs (Comparable searchKey) throws GraphException
  {
    ArrayList dfsList = new ArrayList();
    dfsList=dfsRec(getVertex(searchKey), dfsList);
    clearMarks();
    return dfsList;
  }


/**
 *  Private recursive method called to generate a breadth-first search.<br>
 *  Preconditions: Must be passed a graphNode and an ArrayList.<br>
 *  Postconditions: Returns an Arraylist for the bfs.<br>
 *  Throws:None.
 */

  private ArrayList dfsRec(GraphNode vertex, ArrayList searchRecList)
  {
    searchRecList.add(vertex);
    vertex.setMarked(true);
    int i=vertexList.indexOf(vertex);
      for(int j=0; j<size; j++)
      {
        if (adjacent[i][j]!=(Double.POSITIVE_INFINITY) &&
            !(getVertex(j)).isMarked())
          dfsRec( getVertex(j), searchRecList );
          
       }//end for j
    return searchRecList;
  }

   /**
    * Draws the panel with all of the edges and vertices. <BR>
    * Preconditions: A Graphics object and the radius of the vertecies. <BR>
    * Postconditions: Draws all of the neccessary components onto the GraphScreen. <BR>
    * @author <A HREF="mailto:arc4472@tntech.edu">Andrew Coleman</A><BR>
    */
   public void draw ( Graphics g, int radius )
   {
      /* draw all of the edges in orange */
      g.setColor ( Color.orange );
      for ( int i = 0; i < adjacent.length; i++ )
      {
         int firstx = getVertex ( i ).getX();
         int firsty = getVertex ( i ).getY();
         String firstkey = getVertex ( i ).getKey().toString();
         for ( int j = 0; j < adjacent[i].length; j++ )
         {
            if ( adjacent[i][j] != Double.POSITIVE_INFINITY )
            {
               int secondx = ((GraphNode) getVertex ( j )).getX();
               int secondy = ((GraphNode) getVertex ( j )).getY();
               String secondkey = (String)((GraphNode) getVertex ( j )).getKey();
               DecimalFormat format = new DecimalFormat();
               format.setMaximumFractionDigits ( 3 );
               int difference = 10;
               /* the final x and y coordinates for the string for each edge */
               int xcoord, ycoord;
               if ( firstx < secondx )
                  xcoord = (secondx - firstx) / 2 + firstx;
               else
                  xcoord = (firstx - secondx) / 2 + secondx;
               if ( firsty < secondy )
                  ycoord = (secondy - firsty) / 2 + firsty;
               else
                  ycoord = (firsty - secondy) / 2 + secondy;
               /* if i < j, then the edge goes from j to i */
               if ( i < j )
               {
                  g.drawLine ( firstx, firsty - 10, secondx, secondy - 10 );
                  g.drawString ( firstkey + " to " + secondkey + ", Weight: " + format.format ( adjacent[i][j] ), xcoord, ycoord - 11 );
               }
               /* if i > j, then the edge goes from i to j */
               else if ( i > j )
               {
                  g.drawLine ( firstx, firsty + 10, secondx, secondy + 10 );
                  g.drawString ( firstkey + " to " + secondkey + ", Weight: " + format.format ( adjacent[i][j] ), xcoord, ycoord + 11 );
               }
            }
         }
      }

      /* draw the shortest path stored in green */
      g.setColor ( Color.green );
      for ( int i = 1; i < path.size(); i++ )
      {
         int firstx = ((GraphNode) path.get ( i - 1 )).getX();
         int firsty = ((GraphNode) path.get ( i - 1 )).getY();
         int secondx = ((GraphNode) path.get ( i )).getX();
         int secondy = ((GraphNode) path.get ( i )).getY();
         g.drawLine ( firstx, firsty, secondx, secondy );
      }

      /* draw all of the vertices in dark gray with a light gray border and the comparable data in the middle */
      for ( int i = 0; i < numVertices(); i++ )
      {
         g.setColor ( Color.lightGray );
         GraphNode temp = getVertex ( i );
         g.fillOval ( temp.getX() - radius, temp.getY() - radius, radius * 2, radius * 2 );
         g.setColor ( Color.darkGray );
         int difference = 2;
         g.fillOval ( temp.getX() - radius + difference, temp.getY() - radius + difference, (radius - difference) * 2, (radius - difference) * 2 );
         g.setColor ( Color.white );
         g.drawString ( (String) temp.getKey(), temp.getX(), temp.getY() );
      }
   }

   /**
    * This method is used to set the arraylist containing the shortest path to be displayed. <BR>
    * Preconditions: An arraylist containing a valid shortest path. <BR>
    * Postconditions: Sets the current path to the given arraylist. <BR>
    * @author <A HREF="mailto:arc4472@tntech.edu">Andrew Coleman</A><BR>
    */
   public void setShortestPathDisplay ( ArrayList path )
   {
      this.path = path;
   }

   /**
    * Used to calculate the shortest distance between two vertices using Djisktra's algorithm. <BR>
    * Preconditions: Two comparables representing the data in the two vertices. <BR>
    * Postconditions: Returns an ArrayList containing the GraphNodes in the path. <BR>
    * Throws: Throws a GraphException if the comparables are the same or there is no connecting path. <BR>
    * @author <A HREF="mailto:arc4472@tntech.edu">Andrew Coleman</A><BR>
    */
   public ArrayList shortestPath ( Comparable firstkey, Comparable lastkey ) throws GraphException	{
      if ( firstkey.compareTo ( lastkey ) == 0 )
         throw new GraphException ( "Cannot find shortest path to same vertex!" );
      /* the arraylist containing the raw path array */
      ArrayList path = new ArrayList ( vertexList.size() );
      /* mark the first vertex */
      getVertex ( firstkey ).setMarked ( true );
      /* indexes of the first and last search keys */
      int firstindex = findIndex ( firstkey );
      int secondindex = findIndex ( lastkey );
      /* the row of the adjacency matrix at firstindex */
      double[] weight = new double[vertexList.size()];
      /* initialize the weight/path arrays */
      for ( int i = 0; i < weight.length; i++ )
      {
         path.add ( vertexList.get ( i ) );
         weight[i] = adjacent[firstindex][i];
         /* if the weight is not infinity we must change the path to reflect the changes */
	 if ( weight[i] < Double.POSITIVE_INFINITY )
            path.set ( i, getVertex ( firstkey ) );
      }

      /* loop through all the elements in the graph, must mark them all */
      for ( int i = 1; i < vertexList.size(); i++ )
      {
         /* index of smallest vertex */
         int smallest = -1;
         /* smallest weight thus far that is not marked */
         double smallestweight = Double.POSITIVE_INFINITY;
         for ( int j = 0; j < weight.length; j++ )
            /* run through the weight array and find the smallest weight */
            if ( smallestweight >= weight[j] && !((GraphNode) vertexList.get ( j )).isMarked() )
            {
               /* note smallest vertex */
               smallest = j;
               smallestweight = weight[j];
            }
         /* mark smallest vertex */
	 GraphNode smallnode = (GraphNode) vertexList.get ( smallest );
         smallnode.setMarked ( true );
         /* update the weight/path arrays */
         for ( int j = 0; j < weight.length; j++ )
            /* if a new weight to that vertex is less than the current weight, change the weight in the array and change the path arraylist */
            if ( weight[j] > weight[smallest] + adjacent[smallest][j] )
            {
               weight[j] = weight[smallest] + adjacent[smallest][j];
               path.set ( j, vertexList.get ( smallest ) );
	    }
      }
      /* backwards path */
      ArrayList result = new ArrayList();
      GraphNode node = getVertex ( lastkey );
      int lastindex = findIndex ( lastkey );
      /* while the node is not the first node */
      while ( lastindex != firstindex )
      {
         result.add ( node );
         node = (GraphNode) path.get ( lastindex );
         int newlastindex = findIndex ( node.getKey() );
         /* if the indexes are the same, then there is no way to get to that vertex */
         if ( newlastindex == lastindex )
            throw new GraphException ( "No connecting path!" );
         else
            lastindex = newlastindex;
      }
      /* gotta add the first one */
      result.add ( getVertex ( firstkey ) );
      /* the result to return */
      ArrayList sortedresult = new ArrayList ( result.size() );
      /* reverse the arraylist */
      for ( int i = result.size() - 1; i >= 0; i-- )
         sortedresult.add ( result.get ( i ) );
      return sortedresult;
   }

   /**
    * This method finds the index of a given comparable object. <BR>
    * Preconditions: A valid comparable key in the graph. <BR>
    * Postcondtions: Returns the index of the key, or -1 if the key is not in the graph. <BR>
    */
   private int findIndex ( Comparable key )
   {
      for ( int i = 0; i < vertexList.size(); i++ )
         if ( ((GraphNode) vertexList.get ( i )).getKey().compareTo ( key ) == 0 )
            return i;
      return -1;
   }

}