tsp.java

this tar includes my code which employ the Lin-Kernighan algorithm to address the tsp problem. this

import java.io.FileReader;
import java.io.FileNotFoundException;
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.Vector;
import java.util.Random;

/**
 * <p>Title: <TSP FUNCTION CLASS>
 * <p>Description: <Methods used for TSPslover>
 * <p>Copyright: Copyright (c) 2005<Tong YuXin>
 * <p>Company: <Uni adelaide>
 * @author: Tong Yuxin
 * @Student NO:a1103993
 * @version 1.0.7
 */

 // class city create the city object with x  coordinate, y coordinate and city name
class City {
  public int lable;
  public double X_axe;
  public double Y_axe;
}
class TSP {
  Vector a; // vector stores the object read from inputfile 
  static int city_number;// the totally number of city
/**
 * <p>Class: <TSP FUNCTION CLASS>
 * <p>Description: <readfromtext used for TSPslover> this method be used to 
 *        read the inputfile and store them in vector
 *       String b is the path of inputfile 
 */
  
  public static Vector readfromtext(String b) throws FileNotFoundException,
      IOException {
    Vector a = new Vector();
    FileReader Reader1 = new FileReader(b);
    BufferedReader in1 = new BufferedReader(Reader1);

    String input = "";
    String rows = "";
    int ro = 0;
    while (rows != null) {
      rows = in1.readLine();
      ro++;
    }// get the city number 
    FileReader Reader = new FileReader(b);
    BufferedReader in = new BufferedReader(Reader);
    if (input != null) {
      for (int i = 0; i < (ro - 1); i++) {
        input = in.readLine();
        StringTokenizer token = new StringTokenizer(input);
        int j = 0;
        for (j = 0; j < 3; j++) {
          a.add(token.nextToken());
        }
      }
    }
    return a;
  }

/**
 * <p>Class: <TSP FUNCTION CLASS>
 * <p>Description: <vectoarray used for TSP> get the object form Vector and  
 *        store them in an array. 
 *        Vector vec is a Vector which stored the object read from inputfile
 */
  public static double[] vectoarray(Vector vec) throws IOException {
    String input = vec.toString();
    double a[] = new double[vec.size()];
    int number = input.length();
    String aa;
    double bb;
    for (int i = 0; i <= (vec.size() - 1); i++) {
      aa = vec.elementAt(i).toString();
      bb = Double.parseDouble(aa);
      a[i] = bb;
    }
    return a;
  }
/**
 * <p>Class: <TSP FUNCTION CLASS>
 * <p>Description: <Distance used for TSP> this method is used to compute
 *       the distance  between two points.
 *       double x, double y, double a, double b are coordinates of two points.
 */
  public static double Distance(double x, double y, double a, double b) {
    double distance = Math.sqrt( (Math.pow( (x - a), 2.0)) +
                                (Math.pow( (y - b), 2.0)));
    return distance;
  }
/**
 * <p>Class: <TSP FUNCTION CLASS>
 * <p>Description: <Dis used for TSP> this method is used to compute
 *       the distance  between two cities(objects).
 *       city1 and city 2 are two cities
 */
  public static double Dis(City city1, City city2) {
    double DIS;

    double X_axe1 = city1.X_axe;// x coordinate
    double Y_axe1 = city1.Y_axe;//  y coordinate
    double X_axe2 = city2.X_axe;// x coordinate
    double Y_axe2 = city2.Y_axe;// y coordinate
    DIS = TSP.Distance(X_axe1, Y_axe1, X_axe2, Y_axe2);// distance between two cities.
    return DIS;
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <Tour used for TSPslover> this method is used to create a random 
 *        tour .       
 *      String str is the times of tour be crested. (the number of iterations)
 */

  public static Vector Tour(String str) throws IOException {
    Vector city_vec = new Vector(); // vector load all data from file
    city_vec = TSP.readfromtext(str); //read file
    city_number = city_vec.size() / 3; // city number
    // City Tour[] = new City[city_number];
    Vector Tour = new Vector();// create new tour 
    Random random = new Random();
    int a = random.nextInt(city_number);
    City temp;
    double city_array[] = TSP.vectoarray(city_vec); // put all element in array
    for (int i = 0; i < city_number; i++) {
      City city = new City();
      city.lable = i + 1;
      city.X_axe = city_array[3 * i + 1];
      city.Y_axe = city_array[3 * i + 2];
      Tour.add(i, city);
    }
// creat a rondom tour . 
    for (int j = 0; j < Tour.size(); j++) {
      a = random.nextInt(city_number);
      temp = (City) Tour.remove(a);
      Tour.add(j, temp);
    }

    return Tour;
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <display_city used for TSPslover> this method is used to print Tour 
 *          
 *      Vector vec is Tour
 */
  public static void display_city(Vector vec) {
    int a = vec.size();
    System.out.println();
    for (int i = 0; i < a; i++) {

      System.out.print("city" + ( (City) vec.get(i)).lable + "--->");

    }
    System.out.println();
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <P_path_to_Tour used for TSPslover> this method is used to revise 
 *   P_path to tour       
 *      Vector vec is Tour
 */
  public static Vector P_path_to_Tour(Vector vec) { 
    Object temp;
    int b = 100000000;// initialize b, find the position of unique point in p path 
	                                // for example 1 2 3 4 5 6 2 ( 2 is unique point in this p path)
    Object search_key = vec.get(vec.size() - 1);
    for (int i = 0; i < vec.size(); i++) {
      if (search_key.equals(vec.get(i))) {
        b = i;
      //  System.out.println("b=" + b);
        break; // find the position and remember the position
      }
    }
   
	vec.remove(vec.size() - 1);// change the P_path to Hamiltonian path 
    for (int k = 0; k < vec.size() - b - 1; k++) {
      temp = vec.remove(vec.size() - 1);// remove point k-----point k+1 
      vec.add(b + k + 1, temp); // add edge to creat tour
    }
    return vec;// tour
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <Change_point used for TSPslover> this method is used change the points
 * of tour  which means outer loop for  each point of k in the tour . for example first tour is 1 2 3 4 5 
 *   then the next loop for point is 2 3 4 5 1.(the oder of point 3 4 5 may be changed )     
 *      Vector vec is Tour ,a is first element of tour 
 */
  public static Vector Change_point(Vector vec, int a) { // done
    Object temp;
    int b = 100000000;//nitialize b, find the point i will changed 
    int search_key = a;// the point will be changed 
    for (int i = 0; i < vec.size(); i++) {
      if (search_key == ( (City) vec.get(i)).lable) {
        b = i;
       // System.out.println("b=" + b);
        break;
      }
    }
    for (int k = 0; k < b; k++) {
      temp = vec.remove(0);
      vec.add(temp);
    }
    return vec; 
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <unclock_path used for TSPslover> this method is used to creat the P_path  
 *      because one tour can creats 2(n-3) p_path with two directions.  unclock_path creats     
 *      the P_path which direction is counter-clockwise
 *      Vector vec is Tour
 */
public static Vector unclock_path(Vector vec){
  Object temp;
  for (int i = 2; i < vec.size() - 1; i++) {
    temp = vec.remove(vec.size() - 1);
    vec.add(i, temp);

  }
return vec; //counter-clockwise P_path
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <Change_edge used for TSPslover> this method is used in  
 *           inner loop of Lin-Kernighan alogrithm which to change the edge (i k)
 *     
 *      Vector vec is Tour
 */

public static Vector Change_edge(Vector vec){//done
  Object temp;
  Vector newvec= new Vector();// new tour 
  for (int i=vec.size()-1;i>0;i--){
  newvec.add(vec.get(i));
  }
   newvec.add(0,vec.get(0));
   return newvec;// new tour 
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <Best_cost used for TSPslover> this method is used to   
 *          compute the  cost of the Tour.
 *     
 *      Vector vec is Tour
 */
  public static double Best_cost(Vector vec) throws IOException { //done
    double best_cost = 0.00;
    double last = 0.00;// the distance between first point and last point .
    for (int i = 0; i < vec.size() - 1; i++) {

      best_cost = TSP.Dis( (City) vec.get(i), (City) vec.get(i + 1)) +
          best_cost;

    }// the cost of Hamiltonian path 

    last = TSP.Dis( (City) vec.get(vec.size() - 1), (City) vec.get(0));//  the cost  between first point and last point .
    best_cost = best_cost + last;// the cost of Tour
    return best_cost;
  }
/**
 * Class: <TSP FUNCTION CLASS>
 * Description: <Best_cost used for TSPslover> this method is used to   
 *          compute the  cost between a Hamiltonian path and a point . such method used 
 *       to compute the cost of P_path. for example  1 2 3 4 5 6 ------2(P_path)
 *      Vector vec is Tour 
 */
  public static double Cost_point(Vector vec, City b) {
  double cost = 0.00;
  for (int i = 0; i < vec.size() - 1; i++)
    cost = TSP.Dis( ( (City) vec.get(i)), ( (City) vec.get(i + 1))) +
        cost;
  cost = TSP.Dis( ( (City) vec.get(vec.size() - 1)), b) + cost;
  return cost;
}


}