import java.util.*;

  public class A5
  {

   /**
       Constructs a random square matrix of nonnegative integers
       of a given size, with zeros down the main diagonal and no
       zeroes elsewhere.
      @param s the desired size of the matrix
      @param maxValue the largest acceptable entry value
      @param r a Random object for the construction of random entries
   */
   // The matrix is constructed in row major order by consulting
   //   the Random object, skipping entries on the main diagonal.

   public static Integer[][]
   buildRandomIntegerArray(int s, int maxValue, Random r)              {
     Integer[][] entry = new Integer[s][s];
     for (int i=0; i<s; i++)
       for (int j=0; j<s; j++)
         if (i==j)
           entry[i][j] = new Integer(0);
         else
           entry[i][j] = new Integer(1+r.nextInt(maxValue-1));
      return entry;                                                    }


   /**
       Prints a simple representation of a graph, with a given
       number of character positions allocated for the printing
       of each entry
       @param g the graph
       @param fieldLength the maximum number of characters printed
         for each entry
   */

   public static void print(Graph g, int fieldLength)                  {
     StringBuffer blanks = new StringBuffer();
     for (int row=0; row<g.size(); row++)                        {
       for (int col=0; col<g.size(); col++)                   {
         String s = g.getEntry(row,col).toString();
         for (int i=0; i<fieldLength-s.length(); i++)
           System.out.print(' ');
         System.out.print(s);                                 }
       System.out.println();                                     }     }



   public static void main(String[] args)                              {


     // test the counting of the number of paths of a given length

     Random r = new Random(5);
     PathCounterGraph g1 =
       new PathCounterGraph(buildRandomIntegerArray(3,10,r));
     print(g1,6);
     System.out.println();

     // find the number of paths of length 2

     PathCounterGraph g2 =
       new PathCounterGraph(g1.combine(g1));
     print(g2,6);
     System.out.println();

     // and length 3

     PathCounterGraph g3 =
       new PathCounterGraph(g2.combine(g1));
     print(g3,6);
     System.out.println();


     // Test the existence of a path of at least a given length

     Boolean f = new Boolean(false);
     Boolean t = new Boolean(true);
     Boolean[][] b = { {f,t,f,f}, {f,t,t,f}, {f,f,f,t}, {f,f,f,t} };
     TransitivizerGraph g4 = new TransitivizerGraph(b);
     print(g4,7);
     System.out.println();

     // test for length <= 2

     TransitivizerGraph g5 = new TransitivizerGraph(g4.combine(g4));
     print(g5,7);
     System.out.println();

     // and for length <= 3

     TransitivizerGraph g6 = new TransitivizerGraph(g5.combine(g4));
     print(g6,7);
     System.out.println();


     // test the naive Theta(n**4) algorithm for solving the
     //   all-pairs problem (returning cost information only)

     r = new Random(59);
     NaiveAllPairsGraph n1 =
        new NaiveAllPairsGraph(buildRandomIntegerArray(5,100,r));
     print(n1,4);
     System.out.println();
     Graph n2 = n1.allpairs(true);
     print(n2,4);
     System.out.println();
     System.out.println();

     // test Floyd's algorithm (with only cost information returned)

     r = new Random(59);
     FloydGraph f1 = new FloydGraph(buildRandomIntegerArray(5,100,r));
     print(f1,4);
     System.out.println();
     Graph f2 = f1.allpairs(true);
     print(f2,4);
     System.out.println();
     System.out.println();


     r = new Random(59);
     f1 = new FloydGraph(buildRandomIntegerArray(5,100,r));
     f2 = f1.allpairs(false);
     print(f2,4);
     System.out.println();
     System.out.println();


     // test Floyd's algorithm (returning cost & packed path info)

     r = new Random(59);
     FloydPathGraph fp1 =
       new FloydPathGraph(buildRandomIntegerArray(5,100,r));
     print(fp1,10);
     System.out.println();
     FloydPathGraph fp2 = fp1.allpairs(true);
     print(fp2,10);
     System.out.println();
     System.out.println();                                             }


  }