optimumsolver.java

collective processing environment for mobile devices. It is an environment for mobile device to solv

import java.io.*;    //...For file operations...
import java.util.*;  //...For StringTokenizer...

public class OptimumSolver{
	
	int number = 0;          //...Number of first cities that will be read...
	File inFile;             //...The input file...
	City Cities[];           //...The first "number" cities that are read...
	double Distances[][];    //...the distances between cities...
	int Indices[];           //...Indices of the current array...
	int resultIndices[];     //...The indices of the result...
	FileReader fr;
	BufferedReader br;
	String name, theta, phi, space;
	StringTokenizer st;
	int i, j;
	double minDistance = 999999999;  	
	double totalDistance;
	long beginTime, endTime; //...For the time elapsed...
	//...Variables to make the user sure that program is responding...
	char continuing = 176;   //...The character to be printed...
	int iteration = 0;       //...Print it in every maxIterations step...
	int maxIterations = 1000000;
 	
	//...Calculates the distance between two cities given their theta and phi coordinates...
	double calculateDistance(double theta1, double phi1, double theta2, double phi2){
		theta1 = Math.toRadians(theta1);
		theta2 = Math.toRadians(theta2);
		phi1   = Math.toRadians(phi1);
		phi2   = Math.toRadians(phi2);
		return 6400 * Math.acos(Math.cos(phi1) * Math.cos(phi2) * (Math.cos(theta1) * Math.cos(theta2) +
			Math.sin(theta1) * Math.sin(theta2)) + Math.sin(phi1) * Math.sin(phi2));
	}
	
	//...Permute the array...
	public boolean permute(){
		//...Note: Operates on the "Indices" array...
		int headIndex = 1; //...Start always from Istanbul...
		int tailIndex = number;
		int temp1Index = tailIndex;
		int temp;
		if(headIndex == tailIndex || headIndex == --temp1Index)
			return false;
		while(true){
			int middleIndex = temp1Index;
			if(Indices[--temp1Index] < Indices[middleIndex]){
				int temp2Index = tailIndex;
				while(!(Indices[temp1Index] < Indices[--temp2Index]));
				//...Swap elements in temp1Index with temp2Index...
				temp = Indices[temp1Index];
				Indices[temp1Index] = Indices[temp2Index];
				Indices[temp2Index] = temp;
				//...Apply a reversion...
				while(middleIndex != tailIndex && middleIndex != --tailIndex){
					temp = Indices[middleIndex];
					Indices[middleIndex] = Indices[tailIndex];
					Indices[tailIndex] = temp;
					middleIndex++;
				}
				return true;
			}
			if(temp1Index == headIndex){
				while(temp1Index != headIndex && temp1Index != --headIndex){
					temp = Indices[temp1Index];
					Indices[temp1Index] = Indices[headIndex];
					Indices[headIndex] = temp;
					temp1Index++;
				}
				return false;
			}
		}
	}
					
	public void printResult() throws Exception{
		double elapsedTime = (double)(endTime - beginTime) / (double)1000;

		File out = new File("opt_tsp" + number + ".txt");
		FileWriter fw = new FileWriter(out);
		PrintWriter pw = new PrintWriter(fw);
		pw.println("******************************");
		pw.println("* Solutions By OptimumSolver *");
		pw.println("******************************");
		pw.println();
		pw.println("Number of cities...: " + number);
		pw.println();
		pw.println("Distances between cities...:");
		for(i = 0; i < number; i++)
			for(j = i + 1; j < number; j++)
				pw.println(Cities[i].name + " - " + Cities[j].name + " ...: " + Distances[i][j]);
		pw.println();
		pw.println("Shortest tour is...:");
		for(i = 0; i < number; i++)
			pw.print(Cities[resultIndices[i]].name + " - ");
		pw.println("Istanbul");
		pw.println("Minimum distance is...: " + minDistance);
		pw.println("Time elapsed...: " + elapsedTime + " seconds");
		fw.close();
		System.out.println("\nMinimum distance is...: " + minDistance);
		System.out.println("Time elapsed...: " + elapsedTime + " seconds");
		System.out.println("Check file \"opt_tsp" + number + ".txt\" for details.");
	}

	public OptimumSolver(String args[]) throws Exception{
		
		beginTime = System.currentTimeMillis(); //...Get the start time...
	
		//...Make sure that number of arguments is correct...
		if(args.length != 2){
			System.out.println("ERROR...\nUsage: javac OptimumSolver <Number> <FileName>");
			System.exit(0);
		}
		//...Make sure that file exists and is readable...
		inFile = new File(args[1]);
		if(!inFile.exists() || !inFile.canRead()){
			System.out.println("ERROR...\nCan not read from input file \"" + inFile + "\"");
			System.out.println("Make sure that file exists and is readable");
			System.exit(0);
		}
		//...Make sure that number is an integer...
		try{
			number = Integer.parseInt(args[0]);
		}
		catch(Exception e){
			System.out.println("ERROR...\nNumber should be an integer");
			System.exit(0);
		}
		//...If number is greater than or equal to 20, computations may be long....
		if(number >= 20){
			System.out.println("WARNING...\nCalculations may be long.");
			System.out.println("Please be patient.");
		}
		
		//...Up to know everything is fine...
		//...Read the file and fill in the "Cities" array...
		Cities =  new City[number];
		fr = new FileReader(inFile);
		br = new BufferedReader(fr);
		for(i = 0; i < number; i++){
			name  = br.readLine();
			theta = br.readLine();
			phi   = br.readLine();
			space = br.readLine();
			st = new StringTokenizer(name, ",");
			name = st.nextToken();
			Cities[i] = new City(name, Double.parseDouble(theta), Double.parseDouble(phi));
		}
		//...Fill in the "Distance" array...
		Distances = new double[number][number];
		for(i = 0; i < number; i++)
			for(j = 0; j < number; j++)
				Distances[i][j] = calculateDistance(Cities[i].theta, Cities[i].phi, 
								    Cities[j].theta, Cities[j].phi);
		//...Fill in the "Indices" array...
		Indices = new int[number];
		for(i = 0; i < number; i++) Indices[i] = i;
		
		//...Create the "resultIndices" array...
		resultIndices = new int[number];

		//...Get all permutations and list the minimum distance...
		do{
			totalDistance = 0;
			//...Calculate the total distance...
			for(i = 0; i < number; i++){
				totalDistance += Distances[Indices[i]][Indices[(i + 1) % number]];
			}
			if(totalDistance < minDistance){
				//...Change the minimum distance...
				minDistance = totalDistance;
				//...Change the resultIndices array...
				for(i = 0; i < number; i++){
					resultIndices[i] = Indices[i];
				}
			}
			//...Make the user sure that the program is running...
			iteration++;
			if(iteration == maxIterations){
				System.out.print(continuing);
				iteration = 0;
			}
		}while(permute());
		
		endTime = System.currentTimeMillis(); //...Get the end time...

		//...Print the result in a file...
		printResult();					
	}

	public static void main(String args[]) throws Exception{
		OptimumSolver os = new OptimumSolver(args);
	}
}

class City{
	String name; //...The name of the city...
	double theta; //...The theta coordinate...
	double phi;   //...the phi coordinate...
	
	City(String Name, double Theta, double Phi){
		name = Name;
		theta = Theta;
		phi = Phi;
	}
}