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<>();
//adjacency matrix
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();
adjMatrix.clear();
finalSolution.clear();
}
public void addPoint(Point p) {
points.add(p);
}
public static ArrayList<Point> getPoints() {
return Solver.points;
}
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++) {
if (iter_x == iter_y) {
temp.add(-1.0);
} else {
temp.add(points.get(iter_x).calculateDistanceToPoint(points.get(iter_y)));
}
}
adjMatrix.add(temp);
}
}
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
int nearest = getIndexOfMin(adjMatrix.get(startingPoint));
Solution sol = new Solution();
//until we've visited all points
while (noOfVisited!=points.size()) {
//get next nearest point and add it to visited
nearest = getIndexOfMin(adjMatrix.get(nearest));
visitedPoints.add(nearest);
//add this point to solution
Point newPoint = points.get(nearest);
solution.add(newPoint);
//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());
ss.addPoint(p);
}
sol.addStep(ss);
noOfVisited++;
}
finalSolution=sol;
}
}
Then, the SolutionStep class:
class SolutionStep{
public final ArrayList<Point> step = new ArrayList<>();
public SolutionStep(){}
public void addPoint(Point p){
step.add(p);
}
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 addStep(SolutionStep solutionStep){
playbackSolution.add(solutionStep);
}
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);
frame.add(panel);
panel.setBackground(Color.white);
frame.add(button1, BorderLayout.NORTH);
button1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
tsp.startSimulation(true);
}
});
panel.add(tsp);
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) {
temp.add(-1.0);
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…