// Kruskal's Algorithm, Section 9.5.2, pp. 323-325
import java.util.Vector;  // to remove problem if link to Bailey's code
import java.util.Enumeration;  

public class Kruskal
{
   public static void main ( String [] args )
   {
      int uset, vset;       // uset anv vset are used by Disjoint Set class
      int u, v;             // u and v are vertices
      int totalCost = 0;    // the sum of the weights of the edges in the MST
      Vector minSpanTree = new Vector ( );

      Graph g = new Graph ( );
      BinaryHeap h = g.readGraphIntoHeapArray ( );
      g.printCityNames ( );
      // print the graph for debugging purposes
      System.out.println ( g.toString ( ) );
 
      // Graph and heap exist.  Now convert array to heap using algorithm
      //    in Figure 6.14 on page 193
      h.buildHeap ( );  // must be changed from private to public
      
      // Create the Disjoint Sets needed           
      int numVertices = g.size( );
      DisjSets s = new DisjSets ( numVertices );

      Edge e;
      int edgesAccepted = 0;

      while ( edgesAccepted < numVertices - 1 )
      {
         e = (Edge) h.deleteMin ( );
         u = e.vertexOne ( );
         v = e.vertexTwo ( );
         uset = s.find (u);
         vset = s.find (v);
         if ( uset != vset )
         {
            // Accept the edge
            edgesAccepted++;
            // add (u,v) to list of accepted edges
            minSpanTree.add ( e );
            s.union( uset, vset );
         }
      }
      // print the edges in the MST, together with their weights
      System.out.println ("The edges of a minimum spanning tree are: " );
      System.out.println ( minSpanTree.toString() );
      // and print the total cost of the MST
      Enumeration enum = minSpanTree.elements ( ); 
      while (enum.hasMoreElements( ) )
      {
         e = (Edge) enum.nextElement( ); 
         System.out.println ("" + e.vertexOne() + "   " + e.vertexTwo() +
            "   " + e.edgeWeight() );  
         totalCost += e.edgeWeight();
      }
      System.out.println("The sum of the edge weights is " + totalCost);
   }
}