import java.util.Random;

/**
     This is the final version of a class that tests the
       Graph methods of Assignment 3,
       CS 155, Fall 2007, San Jose State University
 */


public class A3
{

    // for random generation of test data
    private static Random r = new Random(1);


    /**
        Tests several all-pairs methods on a graph and prints the
          solutions
        @param g the graph
    */

    private static void testAndPrintAllAlgorithms(Graph g)        {
      Graph allPairs = g.naiveAllPairs();
      System.out.println(allPairs);
      allPairs = g.floydAllPairs();
      System.out.println(allPairs);
      allPairs = g.gtAllPairs();
      System.out.println(allPairs);
      allPairs = g.bfAllPairs();
      System.out.println(allPairs);                               }


    /**
        Tests several all-pairs methods on a graph.  Compares
          the solutions and prints the results.
          Prints the time required to compute each of the
          solutions
        @param g the graph
    */

    private static void testAllAlgorithms(Graph g)                {
      int NUMBER_OF_TESTS = 4;
      Graph[] result = new Graph[NUMBER_OF_TESTS];
      Long currentTime = System.currentTimeMillis();
      result[0] = g.naiveAllPairs();
      Long elapsedTime1 =
        System.currentTimeMillis() - currentTime;
      currentTime = System.currentTimeMillis();
      result[1] = g.floydAllPairs();
      Long elapsedTime2 =
        System.currentTimeMillis() - currentTime;
      currentTime = System.currentTimeMillis();
      result[2] = g.gtAllPairs();
      Long elapsedTime3 =
        System.currentTimeMillis() - currentTime;
      currentTime = System.currentTimeMillis();
      result[3] = g.bfAllPairs();
      Long elapsedTime4 =
        System.currentTimeMillis() - currentTime;
      System.out.println("    naive  Floyd     GT      BF ");
      for (int i=0; i<NUMBER_OF_TESTS; i++)                    {
        for (int j=0; j<NUMBER_OF_TESTS; j++)
          System.out.printf("%8s",
            result[i].equals(result[j]));
        System.out.println();                                   }
      System.out.println();
      System.out.print(" n = " + g.getSize() + ", ");
      System.out.println("elapsed time in msec for ");
      System.out.println("    naive  Floyd     GT      BF ");
      System.out.printf("%8d%8d%8d%8d", elapsedTime1,
           elapsedTime2, elapsedTime3, elapsedTime4);
      System.out.println();                                       }


    /**
        Constructs a weighted, directed graph with a given
          number of vertices, and integer edge weights drawn randomly
          and uniformly from the interval [1,99], except that
          all edges of the form (v,v) will be forced to
          have weight 0 by the Graph constructor.
        @param n the desired number of vertices
    */

    private static Graph buildRandomGraph(int n)                  {
      int [][] adjacency = new int[n][n];
        for (int i=0; i<n; i++)
          for (int j=0; j<n; j++)
            adjacency[i][j] = 1 + r.nextInt(99);
      return new Graph(adjacency);                                }



    /**
         Tests various all-pairs shortest path algorithms
           on various graphs
         @param args is ignored.
    */

    public static void main(String[] args)                        {
      int[][] adjacency0 =
        {{0, 1, 1},
         {1, 0, 1, 1, 1},
         {1, 1, 0, 1},
         {1, 1, 1, 1}};
      Graph g0 = new Graph(adjacency0);
      System.out.println(g0);
      testAndPrintAllAlgorithms(g0);
      System.out.println(g0);
      System.out.println("================");

      int[][] adjacency =
        {{0, 3, 8, Integer.MAX_VALUE, -4},
         {Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 1, 7},
         {Integer.MAX_VALUE, 4, 0, Integer.MAX_VALUE, Integer.MAX_VALUE},
         {2, Integer.MAX_VALUE, -5, 0, Integer.MAX_VALUE},
         {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 6,0}
        };
      Graph g = new Graph(adjacency);
      System.out.println(g);
      testAndPrintAllAlgorithms(g);
      System.out.println(g);
      System.out.println("================");

      Graph g1 = new Graph(adjacency);
      System.out.print(g0.equals(g0) + " ");
      System.out.print(g0.equals(g) + " ");
      System.out.print(g0.equals(g1) + " ");
      System.out.println();
      System.out.print(g.equals(g0) + " ");
      System.out.print(g.equals(g) + " ");
      System.out.print(g.equals(g1) + " ");
      System.out.println();
      System.out.print(g1.equals(g0) + " ");
      System.out.print(g1.equals(g) + " ");
      System.out.print(g1.equals(g1) + " ");
      System.out.println();
      System.out.println("================");


      int testSize = 8;
      adjacency = new int[testSize][testSize];
        for (int i=0; i<testSize; i++)
          for (int j=0; j<testSize; j++)
            if (i!=j)
              adjacency[i][j] = 1 + r.nextInt(99);
      g = new Graph(adjacency);
      System.out.println(g);
      testAndPrintAllAlgorithms(g);
      System.out.println(g);
      System.out.println("================");

      for (int s=0; s<testSize; s++)            {
        int[] path = g.bfSinglePair(s,7);
        for (int j=0; j<path.length; j++)
          System.out.print(path[j] + " ");
        System.out.println();                   }
      System.out.println("================");
      testAndPrintAllAlgorithms(new Graph());
      System.out.println("================");

      testSize = 8;
      adjacency = new int[testSize][testSize];
        for (int i=0; i<testSize; i++)
          for (int j=0; j<testSize; j++)
            if (i!=j)
              adjacency[i][j] = r.nextInt(100) - 20;
      g = new Graph(adjacency);
      System.out.println(g);
      testAndPrintAllAlgorithms(g);
      System.out.println(g);
      System.out.println("================");

      for (int i=8; i<=256; i=2*i)              {
        g = buildRandomGraph(i);
        testAllAlgorithms(g);
        System.out.println("================"); }

   }
}