import java.util.*;

/** This class represents undirected, weighted graphs.
    An inner class Edge represents edges in a suitable
    form for entry into an instance of a collection class
*/

// An adjacency matrix representation is used.  Methods
//   include those for finding a minimum-cost spanning
//   tree using Kruskal's algorithm, and for finding
//   an approximate TSP solution.  In both cases,
//   solutions are represented by Vectors of Edges,
//   although formally Lists are returned.


public class UndirectedGraph
{

   /** the adjacency matrix */

   protected int[][] adjacency;

   /** the number of vertices in the graph */

   protected int NUM_VERTICES;



  /**
     builds an undirected graph with n vertices
     and no edges
     @param n the number of vertices desired
  */

  public UndirectedGraph(int n)      {
    NUM_VERTICES=n;
    adjacency=new int[n][n];         }

  /**
     builds an undirected graph with n vertices
     and random weights, uniformly distributed
     in the range from 1 through a given maximum weight
     @param n the number of vertices desired
     @param r the Random object to be used in
              computing the random weights
     @param maxCost the maximum weight
  */

  // The adjacency matrix is filled in row major order,
  //   except that since the graph is to be undirected,
  //   only the entries above the main
  //   only the elements above the main diagonal
  //   are computed randomly.  The main diagonal entries
  //   are all zero, and the other entries are
  //   computed by symmetry

  public UndirectedGraph(int n, Random r,int maxCost)      {
    int c;                  // an edge cost
    NUM_VERTICES=n;
    adjacency=new int[n][n];
    for (int i=0; i<n; i++)                 {
      for (int j=i+1; j<n; j++)        {
        c=1+r.nextInt(maxCost);
        adjacency[i][j]=c;
        adjacency[j][i]=c;             }
      adjacency[i][i]=0;                    }              }


  /**
     builds an undirected graph with n vertices
     and random weights satisfying the triangle inequality,
     in the range from 1 through a given maximum weight
     @param r the Random object to be used in
              computing the random weights
     @param n the number of vertices desired
     @param maxCost the maximum weight
  */
  // The triangle inequality is guaranteed by choosing
  //   random points in a square of a size consistent
  //   with the given maximum cost

  public UndirectedGraph(Random r, int n, int maxCost)     {
    int[] x,y;         // for coordinates;
    x = new int[n];
    y = new int[n];
    NUM_VERTICES=n;
    adjacency=new int[n][n];

    // find the size of the square
    int MAX_COORD = maxCost * 5 / 7;

    // create the random points
    for (int i=0; i<n; i++)                           {
      x[i] = r.nextInt(MAX_COORD);
      y[i] = r.nextInt(MAX_COORD);
      adjacency[i][i]=0;                              }

    // determine their distances
    for (int i=0; i<n; i++)                           {
      for (int j=i+1; j<n; j++)                  {
        int diff1 = x[i]-x[j];
        int diff2 = y[i]-y[j];
        long c = Math.round(Math.ceil(
           Math.sqrt(diff1*diff1+diff2*diff2)));
        adjacency[i][j]=(int) c;
        adjacency[j][i]=(int) c;                 }    }    }



  /** Prints an adjacency representation of a
      graph to standard output -- it assumes all cost values
      are at most 1,000,000.
  */

  public void traverse()                             {
    int c;                 // an edge cost
    String s;        // its String version
    for (int i=0; i<NUM_VERTICES; i++)             {
      for (int j=0; j<NUM_VERTICES; j++)         {
        c=adjacency[i][j];
        s="     "+c;
        System.out.print(
          s.substring(s.length()-6,s.length())); }
      System.out.println("");                      } }


  /**
      @return the number of vertices in the graph
  */

  public int getNumberOfVertices()                   {
    return NUM_VERTICES;                             }



  /**
      Find an edge given its source and destination.
      No check is made for illegal vertex values.
      @return the edge.
  */

  protected Edge getEdge(int source, int dest)   {
    return new Edge(source,dest,
                     adjacency[source][dest]); }


  /**
      A mutator, but one that might sometimes be necessary
      in some applications, that updates the cost of a given
      undirected edge.  It allows the two endpoints of the
      vertices to be equal.  No check is made for illegal
      vertex values.
      @param source one vertex of the edge
      @param dest another vertex of the edge
      @param cost the new cost
  */

  public void setEdgeCost(int source, int dest, int cost)  {
    adjacency[source][dest] = cost;
    adjacency[dest][source] = cost;                        }



  /** Construct a priority queue containing the
        edges of a given graph.
      @return the priority queue
  */

  // note that since the graph is undirected, only
  //   half the adjacency matrix needs to be read in

  protected PriorityQueue readGraphIntoHeap()    {
    int n=NUM_VERTICES;
    Vector v=new Vector(n*n);
    for (int i=0; i<n; i++)
      for (int j=i+1; j<n; j++)           {
        Edge e = getEdge(i,j);
        if (e.getCost() != 0)
          v.add(getEdge(i,j));            }
    return new PriorityQueue(v);               }


/**
  Constructs a minimum cost spanning tree
  for the graph
  @return a Vector containing the edges
   in the spaning tree
*/
// Uses Kruskal's algorithm.  This method
//   is that of Weiss, p. 324, with a few
//   minor changes (e.g, vertices and
//   equivalence classes are represented
//   by integers).


public List kruskal()                     {
  int edgesAccepted=0;
  Vector output=new Vector();
  DisjSetsFast s;
  PriorityQueue h;
  int uset,vset;      // result of s.find
  Edge e;
  h=readGraphIntoHeap();   // calls buildHeap
  if (h.size() < NUM_VERTICES-1)  // changed 12/07/02
    return output;
  s = new DisjSetsFast(NUM_VERTICES);
  edgesAccepted=0;
  while (edgesAccepted < NUM_VERTICES-1) {
    e=(Edge) h.deleteMin();
    uset=s.find(e.getSource());
    vset=s.find(e.getDest());
    if (uset != vset)              {
      edgesAccepted++;
      s.union(uset,vset);
      output.add(e);               }     }
  return output;                            }


  /**
  Constructs a list of edges representing
    an approximate solution to the TSP instance
    for the graph
  @return the list of edges, or an empty list
   if no approximation can be found
  */
  // Uses a greedy algorithm is similar to Kruskal's
  // The edges are inspected in nondecreasing order
  //   of cost, and an edge is included in the output
  //   iff it does not complete a cycle, and both
  //   endpoints have degree less than 2.  For ease
  //   in checking this (and in finding the last
  //   edge of the cycle), an array "degree" is
  //   maintained containing the degrees of each node
  //   in the solution
  // Note that partially constructed solutions may
  //   be disconnected subgraphs, as in Kruskal's
  //   algorithm.
  // The first n-1 edges of the output cycle are
  //   constructed this way, and the final edge
  //   is constructed from the two remaining
  //   endpoints of degree 1.

  public List GreedyTSPApprox()                              {
  int edgesAccepted=0;
  int[] degree=new int[NUM_VERTICES];
  Vector output=new Vector();
  DisjSetsFast s;
  PriorityQueue h;
  int uset,vset;      // result of s.find
  int u,v;                     // vertices
  Edge e;
  h=readGraphIntoHeap();   // calls buildHeap
  s = new DisjSetsFast(NUM_VERTICES);
  edgesAccepted=0;
  while (edgesAccepted < NUM_VERTICES-1)               {
    e=(Edge) h.deleteMin();
    if (e == null)
      return new Vector();
    u=e.getSource();
    v=e.getDest();
    uset=s.find(u);
    vset=s.find(v);
    if (uset != vset && degree[u]<2 && degree[v]<2)  {
      edgesAccepted++;
      s.union(uset,vset);
      degree[u]++;
      degree[v]++;
      output.add(e);                                  } }
    u=-1;              // will be endpoints
    v=-1;              //   of the last edge
    int i=0;          // find these endpoints (of degree < 2)
    while (u==-1)                {
      if (degree[i]<2)
        u=i;
      i++;                       }
    while (v==-1)                {
      if (degree[i]<2)
        v=i;
      i++;                       }
    output.add(new Edge(u,v,adjacency[u][v]));
  return output;                                            }


  /**
  Takes a vector of edges and prints them all
    to standard output.  Prints the cost
    of each edge, as well as the total cost.
  It assumes that the total cost is an appropriate
  value for a <code>int</code>.
  @ param v the vector of edges
  @ return the total cost
  */

  public static int traverseEdgeList(List v, boolean isDetailWanted) {
  Edge e=null;
  int totalCost=0;
  Iterator it = v.iterator();
  while (it.hasNext())                       {
    e=(Edge) it.next();
    totalCost+=e.getCost();
    System.out.print(e.getSource());
    System.out.print("<->");
    System.out.print(e.getDest());
    if (isDetailWanted)                    {
      System.out.print(",    cost ");
      System.out.println(e.getCost());     }
    else
      System.out.print(" ");                 }
  System.out.print("total cost: ");
  System.out.println(totalCost);
  return totalCost;                                                   }





   /** an inner class for representing edges
   */

   protected class Edge implements Comparable      {
     int source;
     int dest;
     int cost;


     /** a basic edge constructor
     @param s the desired source vertex
     @param d the desired destination vertex
     @param c the desired cost
     */

     public Edge(int s, int d, int c)  {
       source=s;
       dest=d;
       cost=c;                         }

     /**
     @return the source vertex of an edge
     */

     int getSource()                   {
       return source;                  }

     /**
     @return the destination vertex of an edge
     */

     int getDest()                     {
       return dest;                    }


     /**
     @return the cost of an edge
     */


     int getCost()                     {
       return cost;                    }


     /**
     the comparison method for edges --
     it simply compares costs
     @param e the edge
     @return an integer with the
      conventional interpretation for
      compareTo(Object)
     */

     public int compareTo(Object e)    {
     int ecost=((Edge) e).getCost();
     if (cost<ecost)
       return -1;
     else if (cost>ecost)
       return 1;
     else
       return 0;                       }

}   // end Edge


}