/* This code is based on the fortran code of minimal spanning tree
construction by Whitney, M.(Communications of the ACM, Volume 15, Number
4. pp273-274).  

This code is provided "as is" without any warranty of any kind.  We
don't warrant, guarantee or make any representations regarding the
correctness, reliability, currentness of this code. 

We welcome your questions and comments, and request that you share any
modifications with us. 

          Sunhee Kwon
         shkwon@iastate.edu
          Dianne Cook
         dicook@iastate.edu
*/

import java.awt.*;
import java.awt.event.*;
import java.io.*;
import java.util.*;
import java.lang.*;

public class MST1 extends Object { 
 double cst;
 int kkk;
 public void Minimal_Spanning_Tree(double x[][],int n, int dim
                    ,int sta_mst[], int end_mst[], double dist[][]) { 
  
  double temp, d, uk;
  int kk;
  int kp;
  int imst, ni;
  int nit[] = new int[n+1];
  int min_idx, nitp;
  int ji[] = new int[n];
  double ui[] = new double[n+1];
// Compute the Euclid distances between points   

  for (int i=1;i<=n;i++) {
  for (int j=1;j<=n; j++) {
   temp = 0.0;
   for (int k=0; k<dim; k++) {
    temp += Math.pow( (x[i-1][k]-x[j-1][k]) , 2);
   }  
   dist[i][j] = Math.sqrt(temp);
  }
  }

// Select MST edges   
  kp = n;
  imst = 0;

//// initialization
  for (int j=1; j<=n-1; j++) {
   nit[j] = j;
   ui[j] = dist[j][kp];
   ji[j] = kp;
  }

  for (nitp=n-1; nitp >= 1; nitp--) {
   for (kk=1; kk<=nitp; kk++) {
    ni = nit[kk];
    d = dist[ni][kp];                
    if (ui[kk] > d) {
      ui[kk] = d;
      ji[kk] = kp;
    } 
   }
   uk = ui[1];
   for (kk=1; kk<=nitp; kk++) {
    if (ui[kk] <= uk) {
     uk=ui[kk];
     kkk=kk;
    }
   }
   imst = imst+1;
   sta_mst[imst-1] = nit[kkk];
   end_mst[imst-1] = ji[kkk];
   cst = cst+uk;
   kp = nit[kkk];
   ui[kkk]=ui[nitp];
   nit[kkk]=nit[nitp];
   ji[kkk]=ji[nitp];
  }
 }

 protected void finalize() throws Throwable{
//  System.out.println("Class MST1 is not necessary any more!");
  super.finalize(); 
 }




}