/////////////////////////////////////////////////////////////////////////

//  May 9, 2002:

//  The destination of the getComponentsFromPaths message has been
//    changed from ma to ma2.  If you want to write the corresponding 
//    method to be destructive, replacing the input array by the output
//    array, you may do so as long as you document what you are
//    doing.  In this case you may leave the destination of the message
//    as ma if you want.



import java.util.*;


/**
   The test class for Assignment 5, CS 146, Sections 6 & 8
     Spring 2002
*/


public class A5
{


  /**
     Prints the name of each vertex in a collection of vertices.
     Terminates in midprinting if a nonvertex is found.
     @param d the collection
  */

  public static void traverseVertexCollection(Collection d){
    Iterator dit=d.iterator();
    try                                              {
      while (dit.hasNext())                    {
        Vertex v=(Vertex) dit.next();
        System.out.print(v.getName()+" ");     }
      System.out.println("");                        }
    catch(ClassCastException e)                      {
      System.err.println(
        "nonvertex found -- can't continue");        }    }


  /**
      Traverses each component in a collection of
        components (collections of vertices).
      Terminates in midtraversal if a top-level
        element of the collection is not a collection.
      @param c the collection of components
  */

  public static void traverseComponents(Collection c)     {
  Iterator cit=c.iterator();
  try                                                  {
    while (cit.hasNext())                         {
      Collection d=(Collection) cit.next();
      traverseVertexCollection(d);                }    }
  catch(ClassCastException e)                          {
      System.err.println(
        "bad component found -- can't continue");      }  }



  /** the main test function
      @param args ignored
  */

  public static void main(String[] args)            {

  ArrayList alphaLabels=new ArrayList(26);
  String[] alphaArray = new String[26];
  Random r=new Random(2);
  String alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  for (int i=0; i<26; i++)                  {
    alphaArray[i] = alpha.substring(i,i+1);
    alphaLabels.add(alphaArray[i]);         }
  MatrixGraph ma=new MatrixGraph(alphaLabels);
  ListGraph la=new ListGraph(alphaLabels);
  for (int k=1; k<26; k++)
    for (int j=0; j<k; j++)
      if (r.nextInt(13)==0)               {
        ma.addEdge(
            alphaArray[j],alphaArray[k]);
        la.addEdge(
            alphaArray[j],alphaArray[k]); }
  System.out.println("Matrix Array: ");
  traverseComponents(ma.getComponents());
  System.out.println("");
  int infinity=ma.getNumberOfVertices();
  MatrixGraph ma2=ma.allPairsShortestPaths(infinity);
  traverseComponents(ma2.getComponentsFromPaths(infinity));
  System.out.println("");
  System.out.println("List Array: ");
  traverseComponents(la.getComponents());
  System.out.println("");

  LinkedList vertexLabels=new LinkedList();
  vertexLabels.add("a1");
  vertexLabels.add("a2");
  vertexLabels.add("b1");
  vertexLabels.add("b2");
  vertexLabels.add("b3");
  vertexLabels.add("b4");
  vertexLabels.add("c1");
  vertexLabels.add("c2");
  vertexLabels.add("d1");
  vertexLabels.add("a1");
  vertexLabels.add(new Integer(3));
  MatrixGraph m1=new MatrixGraph(vertexLabels);
  ListGraph l1=new ListGraph(vertexLabels);
  m1.addEdge("a1","a2");
  m1.addEdge("b1","b2");
  m1.addEdge("b1","b3");
  m1.addEdge("b3","b4");
  m1.addEdge("c1","c2");
  m1.addEdge("c1","c2");
  m1.addEdge("x1","b3");
  l1.addEdge("a1","a2");
  l1.addEdge("b1","b2");
  l1.addEdge("b1","b3");
  l1.addEdge("b3","b4");
  l1.addEdge("c1","c2");
  l1.addEdge("x2","y2");
  l1.addEdge("c1","c2");
  System.out.println("");
  System.out.println("Matrix Array: ");
  Collection md=m1.getComponents();
  traverseComponents(md);
  System.out.println("");
  System.out.println("List Array: ");
  Collection ld=l1.getComponents();
  traverseComponents(ld);
  System.out.println("");

  Vector nycLabels=new Vector();
  nycLabels.add("Manhattan");
  nycLabels.add("Brooklyn");
  nycLabels.add("Queens");
  nycLabels.add("Bronx");
  nycLabels.add("Richmond");
  nycLabels.add("Jersey");
  nycLabels.add("Nassau");
  nycLabels.add("Upstate");
  nycLabels.add("Connecticut");
  MatrixGraph mn=new MatrixGraph(nycLabels);
  ListGraph ln=new ListGraph(nycLabels);
  mn.addEdge("Brooklyn","Queens");
  mn.addEdge("Queens","Nassau");
  mn.addEdge("Bronx","Upstate");
  mn.addEdge("Upstate","Jersey");
  mn.addEdge("Upstate","Connecticut");
  ln.addEdge("Brooklyn","Queens");
  ln.addEdge("Queens","Nassau");
  ln.addEdge("Bronx","Upstate");
  ln.addEdge("Upstate","Jersey");
  ln.addEdge("Upstate","Connecticut");
  System.out.println("Matrix Array: ");
  traverseComponents(mn.getComponents());
  System.out.println("");
  System.out.println("List Array: ");
  traverseComponents(ln.getComponents());
  System.out.println("");
  mn.addEdge("Brooklyn","Manhattan");
  ln.addEdge("Brooklyn","Manhattan");
  mn.addEdge("Manhattan","Bronx");
  ln.addEdge("Manhattan","Bronx");
  mn.addEdge("Queens","Bronx");
  ln.addEdge("Queens","Bronx");
  System.out.println("Matrix Array: ");
  traverseComponents(mn.getComponents());
  System.out.println("");
  System.out.println("List Array: ");
  traverseComponents(ln.getComponents());

  }


};