org.generation5.util
Class TravellingSalesman

java.lang.Object
  org.generation5.util.TravellingSalesman

All Implemented Interfaces:

Visualizable

Direct Known Subclasses:

EvoTravellingSalesman

public class TravellingSalesman

extends java.lang.Object

implements Visualizable

A utility class that provides the necessary methods for calculating route length, managing cities and rendering the scenario. The route is stored as a simple int[], with each integer corresponding to the city to visit (as defined within cityCoordinates). The route is circular, so the route is calculated as follows: for (int i=0; i Important: no validation of the route is done for flexibility. My thanks to Simon Cogan for his insight into the life of a travelling salesman.

Field Summary

protected static int[][]	cityCoordinates The city coordinates.
protected static int	maximumCities The maximum number of cities in the world.
protected static int	maximumX The maximum x-dimension for the city coordinates.
protected static int	maximumY The maximum y-dimension for the city coordinates.
protected static java.lang.String[]	nodeLabels Optional labels for each city.
protected static int	numberCities The number of cities in the world.
protected int[]	route The route to use.
protected static Gradient	routeGradient The gradient rendered for the route.

Constructor Summary

TravellingSalesman()
Creates a new instance of TravellingSalesman

Method Summary

static void	addCity(int x, int y) Add a city to the world at position (x,y).
static void	addCity(int x, int y, java.lang.String label) Add a city of position x, y with specified label.
static int[]	getCity(int i) Return the specified city coordinates.
static double	getCityDistance(int i1, int i2) Retrieves the distance between two cities.
static int	getDimensionX() Retrieve the x-dimension.
static int	getDimensionY() Retrieve the y-dimension.
static void	main(java.lang.String[] args) A basic test function.
void	render(java.awt.Graphics g, int width, int height) Render the map and route with labels on a graphics context.
static void	resetCities() Removes all cities from the world.
double	routeLength() Returns the length for this route.
static double	routeLength(int[] route) Calculates total distance travelled within the world using the given route.
static void	setDimension(int mx, int my) Set the maximum world dimensions.
static void	setMaximumCities(int maxCities) Set the maximum number of cities allowed within the world.
void	writeImage(java.lang.String s, int width, int height) Write the map, route and labels to an image.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

cityCoordinates

protected static int[][] cityCoordinates

The city coordinates.

maximumX

protected static int maximumX

The maximum x-dimension for the city coordinates.

maximumY

protected static int maximumY

The maximum y-dimension for the city coordinates.

maximumCities

protected static int maximumCities

The maximum number of cities in the world.

numberCities

protected static int numberCities

The number of cities in the world.

nodeLabels

protected static java.lang.String[] nodeLabels

Optional labels for each city.

routeGradient

protected static Gradient routeGradient

The gradient rendered for the route. This helps visualize the route from start to finish when rendered.

route

protected int[] route

The route to use.

Constructor Detail

TravellingSalesman

public TravellingSalesman()

Creates a new instance of TravellingSalesman

Method Detail

setMaximumCities

public static void setMaximumCities(int maxCities)

Set the maximum number of cities allowed within the world. This method allocates the necessary memory, as well as calculating the gradient.

Parameters:

maxCities - the maximum number of cities.

setDimension

public static void setDimension(int mx,
                                int my)

Set the maximum world dimensions. World is assumed to extend from 0 to mx, 0 to my.

Parameters:

mx - maximum x-dimension.

my - maximum y-dimension.

resetCities

public static void resetCities()

Removes all cities from the world.

getDimensionX

public static int getDimensionX()

Retrieve the x-dimension.

Returns:

the x-dimension.

getDimensionY

public static int getDimensionY()

Retrieve the y-dimension.

Returns:

the y-dimension.

addCity

public static void addCity(int x,
                           int y)

Add a city to the world at position (x,y). This version of the method adds a default label of the form "i: (x,y)" where i is index of the city.

Parameters:

x - x-position of the house.

y - y-position of the house.

routeLength

public static double routeLength(int[] route)

Calculates total distance travelled within the world using the given route.

Parameters:

route - the route to take.

Returns:

the total distance travelled.

routeLength

public double routeLength()

Returns the length for this route.

Returns:

total distance travelled.

addCity

public static void addCity(int x,
                           int y,
                           java.lang.String label)

Add a city of position x, y with specified label.

Parameters:

x - the x-position.

y - the y-position.

label - the city's label.

getCityDistance

public static double getCityDistance(int i1,
                                     int i2)

Retrieves the distance between two cities. The method takes two integers corresponding to the indices within the cityCoordinates array.

Parameters:

i1 - index of city one.

i2 - index of city two.

Returns:

the distance between the two cities.

render

public void render(java.awt.Graphics g,
                   int width,
                   int height)

Render the map and route with labels on a graphics context.

Specified by:

render in interface Visualizable

Parameters:

g - the graphics context.

width - the width of the context.

height - the height of the context.

writeImage

public void writeImage(java.lang.String s,
                       int width,
                       int height)

Write the map, route and labels to an image.

Specified by:

writeImage in interface Visualizable

Parameters:

s - the image filename.

width - the image width.

height - the image height.

main

public static void main(java.lang.String[] args)

A basic test function.

Parameters:

args - command-line arguments (ignored).

getCity

public static int[] getCity(int i)

Return the specified city coordinates.

Parameters:

i - the index of the city to return.

Returns:

the coordinates of the city.