/** The Traveling Sales Person problem solution class
* This program includes four TSP solution methods
* @author Arnas Kainskas and modified by Softhut Group
* @author i5arka@vaidila.vdu.lt
* @version 2.0
*/
//package com.softwarehut.lsl.algorithm.costalgorithm;
import java.awt.Dimension;
public class Tsp {
//** public sector
/** Maximal cities number */
public static final int MAXCITIES = 500;
/** Array of current cities x co-ordinates */
public int xCities[] = new int[MAXCITIES];
/** Array of current cities y co-ordinates */
public int yCities[] = new int[MAXCITIES];
/** Array of current route */
public int route[] = new int[MAXCITIES + 1];
//** private sector
/** Current maximal cities number */
private int citiesLimit;
/** Current maximal x co-ordinate value */
private int maxX;
/** Current maximal y co-ordinate value */
private int maxY;
/** Current minimal x co-ordinate value */
private int minX;
/** Current minimal y co-ordinate value */
private int minY;
/** best=0 , worse=1 */
private int best_or_worst_route_calculation;
private double BIG_NUMBER_FOR_DISTANCE_MATRIX= 10000.0; //FIXME calculate the biggest number for distance matrix
private int cities; // current cities number
private int iterations; // number of iterations
private double[][] d = new double[MAXCITIES][MAXCITIES]; // distances matrix
private boolean[] visitedCities = new boolean[MAXCITIES]; // city is visited or not
private int[] sortedByY = new int[MAXCITIES];
//** constructors
/** Constructs a TSP using users parameters.
@param minx Initial start x co-ordinate of the map
@param miny Initial start y co-ordinate of the map
@param width Map width
@param height Map height
@param citiesNr Cities limit
*/
public Tsp(int minx, int miny, int width, int height, int citiesNr) {
minX = minx;
minY = miny;
maxX = minx + width;
maxY = miny + height;
citiesLimit = citiesNr;
cities = 0;
iterations = 0;
}
/** Constructs a TSP using users parameters.
@param minx Initial start x co-ordinate of the map
@param miny Initial start y co-ordinate of the map
@param width Map width
@param height Map height
@param citiesNr Cities limit
@param best_or_worse best_route = 0; worse_route = 1;
**/
public Tsp(int minx, int miny, int width, int height, int citiesNr, int best_or_worst) {
minX = minx;
minY = miny;
maxX = minx + width;
maxY = miny + height;
citiesLimit = citiesNr;
cities = 0;
iterations = 0;
this.best_or_worst_route_calculation= best_or_worst;
}
/** Constructs a TSP using users parameters.
@param width Map width
@param height Map height
@param citiesNr Cities limit
*/
public Tsp(int width, int height, int citiesNr) {
this(0, 0, width, height, citiesNr);
}
/** Default constructor. Constructs a TSP with map, which is 200 width and 200 height. City limit is 100 */
public Tsp() {
this(0, 0, 200, 200, MAXCITIES);
}
//***
//** public methods sector
/** Returns string, representing main parameters of Tsp
* @return Returns Tsp param string
*/
public String getTspParams() {
return "Minx: " + minX + " Miny: " + minY + " Maxx: " + maxX + " Cities limit: "
+ citiesLimit + " Map size: " + (maxX - minX) + "x" + (maxY - minY);
}
/** Generates random test data. Generates random cities number and random cities co-ordinates. */
public void randomTestData() {
int nr;
cities = 0;
nr = (int) (3 + Math.random() * (citiesLimit - 3));
for (int i = 0; i < nr; i++) {
xCities[i] = (int) (minX + Math.random() * (maxX - minX));
yCities[i] = (int) (minY + Math.random() * (maxY - minY));
cities++;
}
}
/** Changes current maximal cities number
* @param maxCities New maximal cities value.
* @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
public boolean setCitiesLimit(int maxCities) {
if (maxCities < MAXCITIES) {
citiesLimit = maxCities;
return true;
}
return false;
}
/** Changes cities number
* @param citiesNr New cities value.
* @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
public boolean setCitiesNr(int citiesNr) {
if (citiesNr < MAXCITIES) {
cities = citiesNr;
return true;
}
return false;
}
/** Returns the value of current cities limit
* @return Returns the value of current cities limit
*/
public int getCitiesLimit() {
return citiesLimit;
}
/** Changes minimal x co-ordinate value
* @param minx New minimal x co-ordinate value
* @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
public boolean setMinX(int minx) {
if (minx < maxX) {
minX = minx;
return true;
}
return false;
}
/** Changes minimal y co-ordinate value
* @param miny New minimal y co-ordinate value
* @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
public boolean setMinY(int miny) {
if (miny < maxY) {
minY = miny;
return true;
}
return false;
}
/** Changes maximal x co-ordinate value
* @param maxx New minimal x co-ordinate value
* @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
public boolean setMaxX(int maxx) {
if (maxx > minX) {
maxX = maxx;
return true;
}
return false;
}
/** Changes maximal y co-ordinate value
* @param maxy New minimal y co-ordinate value
* @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
public boolean setMaxY(int maxy) {
if (maxy > minY) {
maxY = maxy;
return true;
}
return false;
}
/** Returns tsp map size
* @return Returns dimension of tsp map size.
*/
public Dimension getMapSize() {
return new Dimension(maxX - minX, maxY - minY);
}
/** Removes the cities, which are out of map bounds
* @return No return value
*/
public void removeOutOfBoundsCities() {
int[] temp = new int[MAXCITIES];
int j = 0;
for (int i = 0; i < cities; i++) {
if ((xCities[i] > maxX) || (yCities[i] > maxY) || (xCities[i] < minX)
|| (yCities[i] < minY)) {
temp[j] = i;
j++;
}
}
for (int i = j - 1; i > -1; i--) {
removeCity(temp[i]);
}
}
/** Removes defined city from the map
* @param cityNr City number in array.
* @return Returns <I> true </I> if city was removed and <I> false </I> if not.
*/
public boolean removeCity(int cityNr) {
if (cityNr < cities) {
while (cityNr < cities - 1) {
if (cityNr < MAXCITIES - 1) {
xCities[cityNr] = xCities[cityNr + 1];
yCities[cityNr] = yCities[cityNr + 1];
cityNr++;
} else {
xCities[cityNr] = 0;
yCities[cityNr] = 0;
cityNr++;
}
}
cities--;
return true;
}
return false;
}
// **************
/** Adds a city to the map
* @param x New city x co-ordinate
* @param y New city y co-ordinate
* @return Returns <I> true </I> if city was added and <I> false </I> if not.
*/
public boolean addCity(int x, int y) {
if (cities < citiesLimit) {
//if ((x <= maxX) && (y <= maxY) && (x >= minX) && (y >= minY)) {
xCities[cities] = x;
yCities[cities] = y;
cities++;
return true;
//}
}
System.err.println("Can not add new city x: " +x+ " y: "+ y +" cityNr. " + cities);
return false;
}
/** Returns current number of added cities
* @return Returns current number of added cities
*/
public int getCitiesNr() {
return cities;
}
/** Returns current iterations number
* @return Returns number of iterations, needed to calculate TSP distance and route
*/
public int getIterationsNumber() {
return iterations;
}
/** Clears all cities from the map */
public void clearCiti
