import java.util.*;

public class A5
{


  public static boolean LARGE = false;

  /** process an undirected graph by traversing it,
       applying Kruskal's algorithm and the related
       TSP approxmation algorithm, and printing the
       results of both algorithms.
      @param g the graph
  */

  private static void processGraph(TSPUndirectedGraph g)                      {
    if (!g.isComplete())                                             {
      System.out.println("Graph is not complete: test aborted");
      System.out.println();
      return;                                                        }
    System.out.println("For the graph with adjacency matrix:");
    g.traverse();
    if (g.hasTriangleInequalityProperty())
      System.out.print("The graph has");
    else
      System.out.print("... so the graph does not have");
    System.out.println(" the triangle inequality property");
    System.out.println();
    System.out.println("    A minimum cost spanning tree:");
    List v=g.kruskal();
    g.traverseEdgeList(v,!LARGE);
    System.out.println();
    System.out.println("    The optimal TSP solution");
    v=g.TSP();
    g.traverseEdgeList(v,!LARGE);
    System.out.println();
    System.out.print("    A greedy approximation");
    System.out.println(" to the optimal TSP solution");
    v=g.GreedyTSPApprox();
    g.traverseEdgeList(v,!LARGE);
    System.out.println();
    System.out.print("    Another approximation");
    System.out.println(" to the optimal TSP solution");
    v=g.NewTSPApprox();
    g.traverseEdgeList(v,!LARGE);
    System.out.println();
    System.out.println();                                       }


  private static void processLargeGraph(TSPUndirectedGraph g)                {
    if (!g.isComplete())                                             {
      System.out.println("Graph is not complete: test aborted");
      System.out.println();
      return;                                                        }
    System.out.print("For a graph with ");
    System.out.println(g.getNumberOfVertices() + " vertices");
    if (g.hasTriangleInequalityProperty())
      System.out.print("The graph has");
    else
      System.out.print("... so the graph does not have");
    System.out.println(" the triangle inequality property");
    System.out.println();
    System.out.println("    A minimum cost spanning tree:");
    List v=g.kruskal();
    g.traverseEdgeList(v,LARGE);
    System.out.println();
    System.out.print("    A greedy approximation");
    System.out.println(" to the optimal TSP solution");
    v=g.GreedyTSPApprox();
    g.traverseEdgeList(v,LARGE);
    System.out.println();
    System.out.print("    Another approximation");
    System.out.println(" to the optimal TSP solution");
    v=g.NewTSPApprox();
    g.traverseEdgeList(v,LARGE);
    System.out.println();
    System.out.println();                                       }


  public static void main(String[] args)          {
    Random r = new Random(1);
    int k,kk;

    TSPUndirectedGraph g = new TSPUndirectedGraph(4);
    processGraph(g);

    g = new TSPUndirectedGraph(5);
    for (k=1; k<5; k++)
      g.setEdgeCost(k-1,k,1);
    processGraph(g);

    g = new TSPUndirectedGraph(4,r,1000);
    processGraph(g);

    g = new TSPUndirectedGraph(7,r,1000);
    processGraph(g);

    g = new TSPUndirectedGraph(r,7,1000);
    processGraph(g);

    g = new TSPUndirectedGraph(9,r,1000);
    processGraph(g);

    Random r2 = new Random(2);
    g = new TSPUndirectedGraph(r2,9,100);
    for (int i=0; i<9; i++)
      for (int j=i; j<9; j++)                   {
        int c = 100 + r2.nextInt(5);
        g.setEdgeCost(i,j,c);
        g.setEdgeCost(j,i,c);                   }
    g.setEdgeCost(1,4,200);
    processGraph(g);

    g = new TSPUndirectedGraph(9,r2,1);
    for (k=0; k<9; k++)
      for (kk=k; kk<9; kk++)
        g.setEdgeCost(k,kk,100);
    for (k=0; k<8; k++)
      g.setEdgeCost(k,k+1,10+k);
    g.setEdgeCost(8,0,1000);
    processGraph(g);

    g = new TSPUndirectedGraph(r,50,1000);
    processLargeGraph(g);                                               }

}