////////////////////////////////////////////////////////////////////////////
/*
      High Level Synthesis Homework#1 - Programming Type homework

        Implemented Algorithm :
           < Find the Shortest Path and Longest Path in direct graph >

                                        20023086 Kim SeonPil
                                        Prof. MAREK ANDRZEJ PERKOWSKI

                                                      2002.9.24
                                                                          */
////////////////////////////////////////////////////////////////////////////

import java.util.LinkedList;

/////////////////////////////////////////////////////////
/*
  << Graph Class >>

  Variables :
      HeadNode[i] : Array of Linkedlist that each of them point head of Linkedlist.
                    Element of LinkedList is vertice that is next to vertex[i].
      w[i][j]     : Double Array of weight on Edge, Negative Sign is available.

  Functions :
      graph(int num_of_vertex)    : make basic directed graph with vertice of (num_of_vertex).
      Max_Function(int a, int b)  : return greater int value.
      Min_Function(int a, int b)  : return less int value.
      NumOfLinksInCompare(int index,int num_of_vertex)
                                  : calculate the number of direct edge to vertex[index].
      LinksInCompare(int index,int num_of_vertex,int array_number)
                                  : calculate the edge's index number to vertex[index].
      public void Put_EdgeToGraph(int vertex_number,int next_vertex_number,int inter_vertex_weight)
                                  : Function that get the edge conditions.

      ShortestPath(int start_vertex,int last_vertex,int num_of_vertex)
                                  : Functions that calculate the shortest path from start_vertex to last_vertex.
      LongestPath(int start_vertex,int last_vertex,int num_of_vertex)
                                  : Functions that calculate the longest path from start_vertex to last_vertex.

 < inner_class >

    Inner_class varible:
            vertex
    Inner_class functions:
           Get_Vertex_Number()
           Vertex_Equal(int JustVertexNumber)
                                                       */
/////////////////////////////////////////////////////////
public class graph{

  /*  Variablie Declaraton*/
  private final int INFINITE = 1000;        // Max Number that I assume
  private LinkedList[] HeadNode;            // Point the hadenode of LinkedList contains neighbor vertex
  private int[][] w;                        // weights on Edge that are expressed by double array type

  /*  Inner Class Declaratoin*/
/////////////////////////////////////////////////////////
/*
    Note:
    vertex class is component Object to fill the LinkedList's element
    It has just one variable.

    Inner_class varible:
            vertex      : This class is filled with LinkedList`s elements. It has int type vertex_number variable.

    Inner_class functions:
           Get_Vertex_Number() : return vertex's number
           Vertex_Equal(int JustVertexNumber) : Check whether this.vertex_number is equal to JustVertexNumber.

                                                       */
/////////////////////////////////////////////////////////

  public class vertex
  {
    private int VertexNumber;

    public vertex(int vertex_number)                      //Vertex Constructor
    {
     this.VertexNumber = vertex_number;
    }
    public boolean Vertex_Equal(int JustVertexNumber)     //Check Equality btw. this.vertex_num and JustVertexNumber
    {
      if(this.VertexNumber == JustVertexNumber) return true;
      else return false;
    }

    public int Get_Vertex_Number()
    {
      return(VertexNumber);
    }
  }

////////////////////////////////////////////////////////////////
//  graph Constructor
////////////////////////////////////////////////////////////////

  public graph(int num_of_vertex) {
    HeadNode = new LinkedList[num_of_vertex];
    for(int i=0;i<num_of_vertex;i++)
    {
      HeadNode[i] = new LinkedList();
    }
    w = new int[num_of_vertex][num_of_vertex];
  }

/////////////////////////////////////////////////////////////////
//  Edge_input Functions
//                : It fills graph with edge that I input
//
//  input : vertex_number , next_vertex_number , weight_on_edge
//  return: None
/////////////////////////////////////////////////////////////////
  public void Put_EdgeToGraph(int vertex_number,int next_vertex_number,int inter_vertex_weight)
  {
      vertex temp = new vertex(next_vertex_number);
      if(!HeadNode[vertex_number].contains(temp))
      {
        HeadNode[vertex_number].add(temp);                // Add vertex to LinkedList
        w[vertex_number][next_vertex_number]=inter_vertex_weight;
                                                          // put value to weight array
      }

    /* Because of this graph is direct graph, We doesn't need to care about complementary edge
        Ex) <1,2> is not equal to >2,1> */

  }

  ////////////////////////////////////////////////////////////////
  public int NumOfLinksInCompare(int index,int num_of_vertex)
  {
    vertex temp = new vertex(index);
    int NumOfLink=0;

    for(int i=0; i<num_of_vertex; i++)
    {
      for(int j=0;j<HeadNode[i].size();j++)
      {
        if(temp.Vertex_Equal(((vertex)HeadNode[i].get(j)).Get_Vertex_Number()) )
          NumOfLink++;
      }
    }
    return(NumOfLink);
  }

////////////////////////////////////////////////////////////////
//  Function that calculate the number of edges to vertex[index]
//
//  input : index_of_vertex,vertex's total number,array number that I want to get
//  return: array of number_of_vertex
////////////////////////////////////////////////////////////////
  public int LinksInCompare(int index,int num_of_vertex,int array_number)
  {
  /* Variable Declaration*/
    vertex temp = new vertex(index);
    int[] ListOfPointedLink = new int[num_of_vertex];
    int NumOfLink=0;

    for(int i=0; i<num_of_vertex; i++)
    {
      for(int j=0;j<HeadNode[i].size();j++)
      {
        if(temp.Vertex_Equal(((vertex)HeadNode[i].get(j)).Get_Vertex_Number()) )
           ListOfPointedLink[NumOfLink++]=i;
          /* Find All vertex in all LinkedList that has edge point vertex[index] */
          /* and save values in ListOfPointedLink[] array */
      }
    }

    return(ListOfPointedLink[array_number]);    // return the array value that carry vertex's index
  }
////////////////////////////////////////////////////////////////
//  Minimum Function
//        : return less integer value
//  input : two integer values that will be compared
//  return: less integer value
////////////////////////////////////////////////////////////////
  public int Min_Function(int a, int b)
  {
      if(a<b) return a;
      else return b;
  }

////////////////////////////////////////////////////////////////
//  Maximum Function
//        : return greater integer value
//  input : two integer values that will be compared
//  return: greater integer value
////////////////////////////////////////////////////////////////
  public int Max_Function(int a, int b)
  {
      if(a>(INFINITE/2)) return b;              //CHECK the Boundary
      else if(b>(INFINITE/2)) return a;         //CHECK the Boundary
      else if(a>b) return a;
      else return b;
  }

////////////////////////////////////////////////////////////////
//  ShortestPath Function
//        : return the smalliest path weight from start_vertex to last_vertex
//  input : start_vertex,last_vertex(destination),number of vertex
//  return: None
////////////////////////////////////////////////////////////////

  public void ShortestPath(int start_vertex,int last_vertex,int num_of_vertex)
  {
      /* Variable Declaration */
      int[] S_old = new int[num_of_vertex];     // pair of weight_sum to iterate operation to get
      int[] S_new = new int[num_of_vertex];     // shorter path
      int PointedLink;

      for(int i=0;i<num_of_vertex;i++)          //Initialization
      {
        S_old[i]=INFINITE;
        S_new[i]=INFINITE;
      }

      // write w(i,j)<Weight from i to j> values to S_new Array

      for(int i=0;i<HeadNode[start_vertex].size();i++)
      {
        S_old[((vertex)(HeadNode[start_vertex].get(i))).Get_Vertex_Number()]=
        w[start_vertex][((vertex)(HeadNode[start_vertex].get(i))).Get_Vertex_Number()];
      }

      S_old[start_vertex]=0;  // For SelfToSelf case, Weight is zero.

      int compare_temp=INFINITE;

      for(int i=0;i<num_of_vertex;i++)       // Iterate as # of total vertex
      {
        for(int j=0;j<num_of_vertex;j++)
        {

          compare_temp=INFINITE;             //refresh
          compare_temp=Min_Function(S_old[j],compare_temp);       // Compare (Si0 and (Sj+Wi,j)

          for(int k=0;k<NumOfLinksInCompare(j,num_of_vertex);k++) // Min (Sj+Wi,j)
          {
            PointedLink = LinksInCompare(j,num_of_vertex,k);
            compare_temp = Min_Function(compare_temp, S_old[PointedLink]+w[PointedLink][j] );
          }

          S_new[j]=compare_temp;              // Save the Smaillest path's weight
        }

        for(int c=0; c<num_of_vertex;c++)
          S_old[c]=S_new[c];                  // refresh the weight for next iteration

      }
      if(S_old[last_vertex]!=INFINITE)        // Print out Function
        System.out.println("The Shortest Path from vertex("+start_vertex+") to vertex("+last_vertex+") is "+S_old[last_vertex]);
      else System.out.println("The Shortest Path from vertex("+start_vertex+") to vertex("+last_vertex+") is INFINITE" );
}

////////////////////////////////////////////////////////////////
//  LongestPath Function
//        : return the largeest path weight from start_vertex to last_vertex
//
//  < CAUTION >
//          This Bellman LongestPath Algorithm can't cover whole path. For example, if there is cycle on graph,
//          loop is created. So there are no Longest Path. Finnaly iteration terminate by # of total vertex
//
//  input : start_vertex,last_vertex(destination),number of vertex
//  return: None
////////////////////////////////////////////////////////////////

  public void LongestPath(int start_vertex,int last_vertex,int num_of_vertex)
  {
      /* Variable Declaration */
      int[] S_old = new int[num_of_vertex];     // pair of weight_sum to iterate operation to get
      int[] S_new = new int[num_of_vertex];     // shorter path
      int PointedLink;

      for(int i=0;i<num_of_vertex;i++)          //Initialization
      {
        S_old[i]=INFINITE;
        S_new[i]=INFINITE;
      }

      // write w(i,j)<Weight from i to j> values to S_new Array
      for(int i=0;i<HeadNode[start_vertex].size();i++)
      {
        S_old[((vertex)(HeadNode[start_vertex].get(i))).Get_Vertex_Number()]=
        w[start_vertex][((vertex)(HeadNode[start_vertex].get(i))).Get_Vertex_Number()];
      }

      S_old[start_vertex]=0;  // For SelfToSelf case, Weight is zero.

      int compare_temp=INFINITE;

      for(int i=0;i<num_of_vertex;i++)
      {
        for(int j=0;j<num_of_vertex;j++)
        {

          compare_temp=INFINITE;             //refresh
          compare_temp=Max_Function(S_old[j],compare_temp);       // Compare (Si0 and (Sj+Wi,j)

          for(int k=0;k<NumOfLinksInCompare(j,num_of_vertex);k++) // Max (Sj+Wi,j)
          {
            PointedLink = LinksInCompare(j,num_of_vertex,k);
            compare_temp = Max_Function(compare_temp, S_old[PointedLink]+w[PointedLink][j] );
          }

          S_new[j]=compare_temp;              // Save the largest path's weight
        }

        for(int c=0; c<num_of_vertex;c++)
          S_old[c]=S_new[c];                  //refresh the weight for next iteration
      }

      if(S_old[last_vertex]!=INFINITE)        //Print Function
        System.out.println("The Longest Path from vertex("+start_vertex+") to vertex("+last_vertex+") is "+S_old[last_vertex]);
      else System.out.println("The Longest Path from vertex("+start_vertex+") to vertex("+last_vertex+") is INFINITE" );

  }

}