minimumspanningtree.java

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

/******************************************************************************
   
   Project Name.......: Travelling Salesman Problem
   Project Number.....: 18050315
   Description........: The famous travelling salesman problem, in which the 
			program tries to find the minimum distance between 
			given cities.
   Technical Details..: * Using trees.
			* The permute function.
   Compiler...........: Java(R) 2 SDK, Standard Edition, v 1.2.1
   Author.............: Ozer Senturk
   Web Site...........: www23.brinkster.com/ozersenturk/projects.htm
   E-Mail.............: [e-mail]

******************************************************************************/

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

public class MinimumSpanningTree{
	
	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...
	int Indices[];         //...Indices of the resulting sequence...
	double Distances[][];  //...The distances between cities...
	int candidateIndex;    //...The index of the Cities array that is candidate to be the next...
	int currentIndex[];    //...The pv array...
	Node Result;           //...The root of the resulting tree...
	int lastKnownIndex;    //...The node that is last appended to the tree...
	int indicesIndex = 0;
	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...
	Node temp = Result;
	
	//...Adds a child to the specified node...
	public void AddChild(int parent, int child, Node root){
		if(root == null) return;
		temp = root;
		//...First find the parent...
		if(temp.index != parent){
			ListIterator iter = temp.children.listIterator(0);
			while(iter.hasNext()){
				AddChild(parent, child, (Node)iter.next());
			}		
		}
		else{
			temp.children.add(new Node(child));
			return;
		}
	}

	//...Traverses the tree in preorder fashion...
	public void Dfs(Node root){
		root.picked = true;
		Indices[indicesIndex++] = root.index;
		if(root.children.size() != 0){
			ListIterator iter = root.children.listIterator(0);
			while(iter.hasNext()){
				temp = (Node)iter.next();
				if(temp.picked != true) Dfs(temp);
			}
		}
	}
	 	
	//...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));
	}
	
	public void printResult() throws Exception{
		double elapsedTime = (double)(endTime - beginTime) / (double)1000;

		File out = new File("mst_tsp" + number + ".txt");
		FileWriter fw = new FileWriter(out);
		PrintWriter pw = new PrintWriter(fw);
		pw.println("************************************************");
		pw.println("* Solutions By Minimum Spanning Tree Algorithm *");
		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[Indices[i]].name + " - ");
		pw.println("Istanbul");
		pw.println("Minimum distance is...: " + totalDistance);
		pw.println("Time elapsed...: " + elapsedTime + " seconds");
		fw.close();
		System.out.println("Minimum distance is...: " + totalDistance);
		System.out.println("Time elapsed...: " + elapsedTime + " seconds");
		System.out.println("Check file \"mst_tsp" + number + ".txt\" for details.");
	}

	public MinimumSpanningTree(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);
		}
		
		//...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));
		}
		//...Create the indices array...
		Indices = new int[number];
		//...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);
		
		//...Apply the minimum spanning tree algorithm...
		currentIndex = new int[number];   //...pv array...
		lastKnownIndex = 0;
		for(i = 0; i < number; i++) currentIndex[i] = 0; //...Initialize currentIndex array...
		candidateIndex = 0;
		Cities[0].picked = true;
		Result = new Node(0);
		//...Get the nearest point to the currentIndex'ed element...
		for(i = 0; i < number - 1; i++){
			minDistance = 999999999;
			for(j = 0; j < number; j++){
				if(Cities[j].picked != true){
					if(Distances[currentIndex[j]][j] < minDistance){
						candidateIndex = j;
						minDistance = Distances[currentIndex[j]][j];
					}
				}
			}
			AddChild(lastKnownIndex, candidateIndex, Result); //...Add j as a child to the last know index...
			lastKnownIndex = candidateIndex;			
			Cities[candidateIndex].picked = true;
			//...Update the pv array...
			for(j = 0; j < number; j++){
				if(Distances[currentIndex[j]][j] > Distances[lastKnownIndex][j])
					currentIndex[j] = lastKnownIndex;
			}
		}
		Dfs(Result); //...Traverse the tree in dfs and fill in the Indices array... 		
		//...Calculate the total distance...
		for(i = 0; i < number; i++){
			totalDistance += Distances[Indices[i]][Indices[(i + 1) % number]];
		}		
		endTime = System.currentTimeMillis(); //...Get the end time...

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

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

class City{
	String name;    //...The name of the city...
	double theta;   //...The theta coordinate...
	double phi;     //...the phi coordinate...
	boolean picked; //...Is the item picked or not...
	
	City(String Name, double Theta, double Phi){
		name = Name;
		theta = Theta;
		phi = Phi;
		picked = false;
	}
}

class Node{
	int index;           //...The index of the city...
	boolean picked;      //...Is the node traversed or not...
	LinkedList children; //...Childrens of the node...

	Node(int Index){
		index = Index;
		picked = false;
		children = new LinkedList();
	}
}