# Travelling Salesman Problem with visualisation in Java

Posted on

Problem

For practicing purposes, I challenged myself to write a program that solves the TSP and visualises the results step by step.

As for now, my program uses a simple nearest neighbour algorithm. I want my program to be flexible, so when I add a new algorithm, it will be able to visualise the results, too, without messing with the logic of display.

One of the problems I encountered was displaying the solution step by step. I solved it by creating multiple partial solutions, storing them, and displaying one after another. I feel like it can be done better, but I am not really good in graphics, so I hope to get some clues here.

The `Point` class represents a city:

``````class Point {
private double x;
private double y;

public double getX() {
return x;
}
public double getY() {
return y;
}

public Point(double x, double y) {
this.x = x;
this.y = y;
}

public Point(){
Random r = new Random();
x=r.nextInt(1000);
y=r.nextInt(650);
}

public double calculateDistanceToPoint(Point p) {
double dist = Math.sqrt(Math.pow(this.x-p.x, 2) + Math.pow(this.y-p.y, 2));
return round(dist,2);
}

private static double round(double value, int places) {
if (places < 0) throw new IllegalArgumentException();

BigDecimal bd = new BigDecimal(value);
bd = bd.setScale(places, RoundingMode.HALF_UP);
return bd.doubleValue();
}
}
``````

Then, the `Solver` class, which is doing calculations:

``````class Solver {
//list of all points to visit
private static ArrayList<Point> points = new ArrayList<>();

private ArrayList<ArrayList<Double>> adjMatrix = new ArrayList<>();

//found solution
private static ArrayList<Point> solution = new ArrayList<>();

//visited points
private ArrayList<Integer> visitedPoints = new ArrayList<>();

//used for visualisation
private static Solution finalSolution = new Solution();

public void clear() {
points.clear();
solution.clear();
visitedPoints.clear();
finalSolution.clear();
}

}

public static ArrayList<Point> getPoints() {
return Solver.points;
}

int iter_x;
int iter_y;
for (iter_x = 0; iter_x < points.size(); iter_x++) {
ArrayList<Double> temp = new ArrayList<>();
for (iter_y = 0; iter_y < points.size(); iter_y++) {
if (iter_x == iter_y) {
} else {
}
}
}
}

private int getIndexOfMin(ArrayList<Double> arr) {
Double min = Double.MAX_VALUE;
int index = -2;
for (int i = 0; i < arr.size(); i++) {
Double val = arr.get(i);
if (!(val == -1.0) && !visitedPoints.contains(i) && val < min) {
min = val;
index = i;
}
}
return index;
}

public void solveUsingNN(int startingPoint) {
int noOfVisited = 0;

//find nearest point from the starting one
Solution sol = new Solution();

//until we've visited all points
while (noOfVisited!=points.size()) {
//get next nearest point and add it to visited

Point newPoint = points.get(nearest);

//create a new frame for animation, containing all previous steps and recently added one
SolutionStep ss = new SolutionStep();
Point p;
for (Point newPoint : solution) {
p = new Point(newPoint.getX(), newPoint.getY());
}
noOfVisited++;
}
finalSolution=sol;
}
}
``````

Then, the `SolutionStep` class:

``````class SolutionStep{
public final ArrayList<Point> step = new ArrayList<>();
public SolutionStep(){}

}
public void draw(Graphics g) {
Graphics2D g2 = (Graphics2D) g;
for (int i = 0; i < step.size()-1; i++) {
g2.draw(new Line2D.Double(step.get(i).getX(), step.get(i).getY(), step.get(i + 1).getX(), step.get(i + 1).getY()));
}
}
}
``````

And `Solution`, which contains many steps.

``````public class Solution {
private ArrayList<Point> points = new ArrayList<>();
private static ArrayList<SolutionStep> playbackSolution = new ArrayList<>();
private int noOfFrames;

public Solution(ArrayList<SolutionStep> listOfSteps, int noOfFrames){
this.noOfFrames=noOfFrames;
playbackSolution=listOfSteps;
}
public Solution(){}

public static ArrayList<SolutionStep> getPlayback(){
return playbackSolution;
}
public void clear(){
playbackSolution.clear();
}

}

public void draw(Graphics g) {
int numberOfPoints;
points = Solver.getPoints();
Graphics2D g2 = (Graphics2D) g;
//draw all points
for (Point point : points) {
g2.fill(new Rectangle2D.Double(point.getX(), point.getY(), 6, 6));
}

//draw next line
for(int i = 0;i<noOfFrames;i++) {
playbackSolution.get(i).draw(g);
}

//if we are at the final solution, draw a line from last point to the first
if (noOfFrames == points.size()){
numberOfPoints = points.size();
Point first = playbackSolution.get(0).step.get(0);
Point last = playbackSolution.get(numberOfPoints-1).step.get(numberOfPoints-1);
g2.draw(new Line2D.Double(first.getX(), first.getY(), last.getX(), last.getY()));
}
}
}
``````

Finally, the visualisation:

``````   public class MainFrame {

public static void main(String[] args) {
EventQueue.invokeLater(new Runnable() {
@Override
public void run() {
try {
UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
} catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
}

MainFrame f = new MainFrame();
}
});
}
public JFrame frame = new JFrame();
public JPanel panel = new JPanel(new BorderLayout());
private TSPDrawer tsp;

public MainFrame() {
tsp = new TSPDrawer();
JButton button1 = new JButton("Start Simulation");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
panel.setBackground(Color.white);
public void actionPerformed(ActionEvent e) {
tsp.startSimulation(true);
}
});
frame.pack();
frame.setVisible(true);
}

public class TSPDrawer extends JPanel {

private Timer timer;
private int displayNoOfSteps = 0;
public Solution solution = null;
private int noOfFrames;
public TSPDrawer() {
setOpaque(false);
timer = new Timer(80, new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
solution = new Solution(Solution.getPlayback(),displayNoOfSteps);
noOfFrames = Solver.getPoints().size();
if (displayNoOfSteps<noOfFrames+1) {
repaint();
displayNoOfSteps++;
}
else
startSimulation(false);
}
});
timer.setRepeats(true);
timer.setCoalesce(true);
}

@Override
public Dimension getPreferredSize() {
return new Dimension(1000, 600);
}

protected void paintComponent(Graphics g) {
super.paintComponent(g);
if (!(solution==null)) {
solution.draw(g);
}
}

public void startSimulation(boolean run) {
if (run){
displayNoOfSteps=0;
tsp.removeAll();
Solver s = new Solver(100);
s.solveUsingNN(0);
timer.start();
}
else {
timer.stop();
}
}
}
}
``````

I feel like I’m using too much static fields and methods- but on the other hand, would it be better to create instances of, for example, `Solver` and then have non-static methods to get the solutions?

As I mentioned earlier, I want to get some feedback on this code before I write more complex algorithms, such as simulated annealing, so it would be easy to maintain good code quality.

I know it’s quite a bit of code, so thank you for reading and analyzing it.

Solution

I feel like I’m using too much static fields and methods- but on the other hand, would it be better to create instances of, for example, Solver and then have non-static methods to get the solutions?

Sure! About the only sane reason for using static is a utility class like `java.lang.Math`. A static class with mutable state like yours is a sin. Just imagine two threads trying to solve a TSP at the same time.

## Point

``````class Point {
private double x;
private double y;
``````

I see that your `Point` is immutable. That’s a good decision, but then also declare `x` and `y` as `final`. This makes your class thread-safe and makes the immutability obvious.

``````    public Point(){
Random r = new Random();
x=r.nextInt(1000);
y=r.nextInt(650);
}
``````

Creating a `Random` instance for a single use doesn’t feel right. With

``````    public Point(Random random) {
x = random.nextInt(SCREEN_WIDTH);
y = random.nextInt(SCREEN_HEIGHT);
}
``````

you allow the user to make their random TSP reproducible (by seeding the `random`). Note also the spacing and constants.

``````    public double calculateDistanceToPoint(Point p) {
double dist = Math.sqrt(Math.pow(this.x-p.x, 2) + Math.pow(this.y-p.y, 2));
return round(dist,2);
}
``````

Most of the time, any rounding outside of presentation is wrong.

``````private static double round(double value, int places) {
if (places < 0) throw new IllegalArgumentException();

BigDecimal bd = new BigDecimal(value);
bd = bd.setScale(places, RoundingMode.HALF_UP);
return bd.doubleValue();
}
``````

This looks rather inefficient, but that’s fine for your case. I’d simply go for

``````private static double roundToTwoPlaces(double value) {
return 0.01 * Math.round(100 * value);
}
``````

as it’s much simpler and good enough. Still, I can’t see what you gain by this rounding…

## Solver

``````class Solver {
//list of all points to visit
private static ArrayList<Point> points = new ArrayList<>();
``````

Either use proper javadoc or leave it out. I guess everyone knowing TSP will thing that the `points` are to be visited. Maybe you should call it `pointsToBeVisited`.. probably no, too long and too small added value. Maybe `cities`? Or just leave it as is.

But always use `List` instead of `ArrayList` in declarations. Here, it rather doesn’t matter, but in a parameter list it would.

``````//adjacency matrix
private ArrayList<ArrayList<Double>> adjMatrix = new ArrayList<>();
``````

Again, either `adjMatrix` is clear enough (to me it is) or name it `adjacencyMatrix`.

Consider using an array here as you never need it to grow. An `double[][]` is quite a bit faster as you need no autoboxing.

``````    //used for visualisation
private static Solution finalSolution = new Solution();
``````

This should ideally be not there. Maybe adding a callback (e.g., a `Callable<Solution>`) to be called after each step would help.

``````    public static ArrayList<Point> getPoints() {
return Solver.points;
}
``````

By returning the internal list, you allow everyone who gets it to manipulate it later. So everything may happen and you’ve lost any encapsulation. Either return a copy, or provide `getPoint(int index)`, or just leave it out.

``````    public void fillAdjacencyMatrix() {
int iter_x;
int iter_y;
for (iter_x = 0; iter_x < points.size(); iter_x++) {
ArrayList<Double> temp = new ArrayList<>();
for (iter_y = 0; iter_y < points.size(); iter_y++) {
``````

No, please. No `iter_x` as underscore shouldn’t be used except in constant names. No declaration before the loop as the scope should always be minimized. I’d go for

``````    public void fillAdjacencyMatrix() {
for (int ix = 0; ix < points.size(); ix++) {
List<Double> temp = new ArrayList<>();
for (int iy = 0; iy < points.size(); iy++) {
``````

if I really wanted to make the correspondence between `ix`/`iy` and `x`/`y` clear…. but there’s no `x` and `y` there. So use just plain `i` and `j`. It caries no information and this is fine as there’s no information to carry.

``````                if (iter_x == iter_y) {
``````

This doesn’t feel right. The distance from a point to itself is 0 not -1. Ideally, you should never need such a distance. Leave out this branch if you can.

``````private int getIndexOfMin(ArrayList<Double> arr) {
Double min = Double.MAX_VALUE;
``````

Don’t use `Double` when you need `double`.

``````    int index = -2;
``````

Why not -3? …

``````        SolutionStep ss = new SolutionStep();
Point p;
for (Point newPoint : solution) {
p = new Point(newPoint.getX(), newPoint.getY());
``````

Declare `p` in the right place, i.e., two lines down. You save one line and do the right thing.

I’ve got lazy…