# Visualization of the Traveling Salesmen Problem

I am working on a little project to visualize the algorithm for the Traveling Salesman Problem. I have cities, which are movable objects painted with AWT and Swing. Also I can make a connection between two cities in the form of a undirected edge. Each city should have at least one connection between another city.

In my current solution every city has an ArrayList of the connected city. But I am afraid that this is not the optimal solution. I would like to hear some comments about my code in general and improvements for my explained solution.

PS: I know that there are lots of external libraries, but I want to solve that problem without using any external libraries.

The City Panel

public class CityPanel extends JPanel implements MouseListener, MouseMotionListener {

public final static int UNIT = 16;
public final static int GRIDWIDTH = 3 * UNIT;
public final static int PANELWIDTH = 12 * GRIDWIDTH;
public final static int PANELHEIGHT = 12 * GRIDWIDTH;

private boolean connect;
private boolean connectClick;
private Mediator mediator;
private CityList cityList = new CityList();
private CityList bestTrail = new CityList();
private City marked;
private boolean move;
private int pressX;
private int pressY;

private Graphics2D g2;

public CityPanel(Mediator mediator)  {
this.setPreferredSize(new Dimension(PANELWIDTH, PANELHEIGHT));
this.setBorder(BorderFactory.createLineBorder(Color.BLACK));
this.mediator = mediator;
this.mediator.registerCityPanel(this);
}

//Painting methods

private void paintGrid() {
g2.setColor(Color.LIGHT_GRAY);
for(int i = 0; i < PANELWIDTH; i += GRIDWIDTH) {
this.g2.drawLine(i,0,i,PANELHEIGHT);
this.g2.drawLine(0,i,PANELHEIGHT,i);
}
}

private void paintCities() {
g2.setColor(Color.BLUE);
for (int i = 0; i < cityList.size(); i++) {
paintEdge(cityList.get(i));
paintCity(cityList.get(i));
}
if (marked != null) {
paintEdge(marked);
}
}

private void paintCity(City city) {
int rimX = city.getRimX();
int rimY = city.getRimY();
int x = city.getPos().x();
int y = city.getPos().y();
g2.setColor(city.getColor());
box(rimX, rimY, City.WIDTH, true);
write(String.valueOf(city.getId()), x, y);
if (marked == city) {
g2.setColor(Color.GREEN);
} else {
g2.setColor(Color.WHITE);
}
box(rimX, rimY, City.WIDTH, false);
}

private void paintConnections() {
for (int i = 0; i < this.cityList.size(); i++) {
for (int k = i+1; k < this.cityList.size(); k++) {
paintConnection(this.cityList.get(i), this.cityList.get(k));
}
}
}

private void paintConnection(City city1, City city2) {
if (city1.contains(city2)) {
g2.setColor(Color.GRAY);
g2.drawLine(city1.getPos().x(), city1.getPos().y(),
city2.getPos().x(), city2.getPos().y());
}
}

private void paintEdge(City city) {
g2.setColor(Color.CYAN);
if (city == marked) {
g2.setColor(Color.YELLOW);
}
}

private void box(int x, int y, int width, boolean b) {
if(b) {
g2.fillOval(x, y, width, width);
}
else
g2.drawOval(x, y, width, width);
}

private void write(String name, int x, int y) {
g2.setFont(new Font("Calibri", Font.PLAIN, City.WIDTH/2));
g2.setColor(Color.WHITE);
final FontMetrics fm = g2.getFontMetrics();
final int strWidth = SwingUtilities.computeStringWidth(fm, name);
g2.drawString(name, (int) (x - strWidth/2), (int) (y + fm.getMaxAscent()/2));
}

private void paintDescriptions() {
for (int i = 0; i < this.cityList.size(); i++) {
City city1 = this.cityList.get(i);
for (int k = 0; k < city1.getConnections().size(); k++) {
City city2 = city1.getConnections().get(k);
Pos pos = getCenterOfLine(city1, city2);
String dist = String.valueOf(this.cityList.getDistance(city1, city2));
g2.setColor(Color.GRAY);
g2.setFont(new Font("Calibri", Font.PLAIN, City.WIDTH/3));
final FontMetrics fm = g2.getFontMetrics();
final int strWidth = SwingUtilities.computeStringWidth(fm, dist);
g2.drawString(dist, pos.x() - strWidth/2, pos.y());
}
}
}

private void paintBestTrail() {
for (int i = 1; i < this.bestTrail.size(); i++) {
City a = this.bestTrail.get(i-1);
City b = this.bestTrail.get(i);
g2.setColor(Color.RED);
g2.drawLine(a.getPos().x(), a.getPos().y(), b.getPos().x(), b.getPos().y());
}
}

//other methods

this.cityList.clear();
for (int i = 1; i <= number; i++) {
}
this.repaint();
}

public void connectAllCities() {
for (int i = 0; i < this.cityList.size(); i++) {
for (int k = i+1; k < this.cityList.size(); k++) {
}
}
repaint();
}

public void showConnections() {
for (int i = 0; i < this.cityList.size(); i++) {
System.out.print("City " + this.cityList.get(i).getId() + ":\t");
for (int k = 0; k < this.cityList.get(i).getConnections().size(); k++) {
System.out.print(this.cityList.get(i).getConnections().get(k).getId() + "\t");
}
System.out.println();
}
System.out.println();
}

public void setConnect(boolean connect) {
this.connect = connect;
}

public Pos getCenterOfLine(City city1, City city2) {
Pos pos1 = city1.getPos();
Pos pos2 = city2.getPos();
int newX = (pos2.x() - pos1.x()) / 2 + pos1.x();
int newY = (pos2.y() - pos1.y()) / 2 + pos1.y();
return new Pos(newX, newY, true);
}

private boolean isStartable() {
boolean b = true;
for (City city : this.cityList) {
if (city.getConnections().size() == 0)
b = false;
}
return this.cityList.size() != 0 && b;
}

public void setBestTrail() {
this.bestTrail.clear();
CityList temp = (CityList) this.cityList.clone();
Random rand = new Random();
for (int i = 0; i < temp.size(); i++) {
int r = rand.nextInt(this.cityList.size()-i);
temp.remove(r);
}
}

//MouseListener methods

@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
this.g2 = (Graphics2D) g;
this.g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
this.g2.setRenderingHint(RenderingHints.KEY_INTERPOLATION,
RenderingHints.VALUE_INTERPOLATION_BICUBIC);

this.paintGrid();
this.paintConnections();
this.paintCities();
if (connectClick) {
g2.setColor(Color.GRAY);
g2.drawLine(this.marked.getPos().x(), this.marked.getPos().y(),
this.pressX, this.pressY);
}
paintDescriptions();
paintBestTrail();
this.mediator.enableStartButton(isStartable());
}

@Override
public void mouseClicked(MouseEvent e) {
if(SwingUtilities.isRightMouseButton(e)) {
if(this.cityList.isOccupied(new Pos(e.getX(), e.getY()), null)) {
cityList.remove(cityList.getMarked(e.getX(), e.getY()));
repaint();
} else  {
cityList.add(new City(cityList.size() + 1, e.getX(), e.getY()));
repaint();
}
} else
showConnections();
}

@Override
public void mousePressed(MouseEvent e) {
if (marked != null) {
if (this.connect) {
this.connectClick = true;
}
this.move = true;
}
}

@Override
public void mouseReleased(MouseEvent e) {
if (this.connectClick)  {
City city = this.cityList.getMarked(e.getX(), e.getY());
if (city != null)   {
}
}
this.move = false;
this.connectClick = false;
this.connect = false;
this.repaint();
}

@Override
public void mouseEntered(MouseEvent e) {
}

@Override
public void mouseExited(MouseEvent e) {
}

@Override
public void mouseDragged(MouseEvent e) {
if (this.connectClick)  {
this.pressX = e.getX();
this.pressY = e.getY();
} else {
int maxHeight = CityPanel.PANELHEIGHT - City.WIDTH / 2;
int minHeight = City.WIDTH / 2;
int maxWidth = CityPanel.PANELWIDTH - City.WIDTH / 2;
int minWidth = CityPanel.WIDTH / 2;
if (e.getX() > maxWidth || e.getX() < minWidth ||       //Checks if Mouse is out of Panelrange, the field is Occupied, or if move=false
e.getY() > maxHeight || e.getY() < minHeight ||
this.cityList.isOccupied(new Pos(e.getX(), e.getY()), marked) ||
!move)
return;
this.marked.setPos(new Pos(e.getX(), e.getY()));
}
repaint();
}

@Override
public void mouseMoved(MouseEvent e) {
if (this.move || this.connectClick)
return;
City neu = this.cityList.getMarked(e.getX(), e.getY());
if (this.marked != neu) {
this.marked = neu;
this.repaint();
}
}
}


The City Class

public class City {

private int id;
private Pos pos;
public static int WIDTH = (int) (0.75 * CityPanel.GRIDWIDTH);
private Color color = Color.BLACK;
private ArrayList<City> connections = new ArrayList<City>();
private Random r = new Random();

public City(int id) {
this.id = id;
System.out.println("City " + id);
this.pos = new Pos();
}

public City(int id, int x, int y) {
this.id = id;
this.pos = new Pos(x,y);
}

public boolean isMarked(int x, int y) {
return (distFromCenter(x, y) < this.WIDTH/2);
}

public double distFromCenter(int x, int y) {
int dx = Math.abs(pos.x() - x);
int dy = Math.abs(pos.y() - y);
return Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
}

public int getRimX() {
return this.pos.x() - this.WIDTH / 2;
}

public int getRimY() {
return this.pos.y() - this.WIDTH / 2;
}

if (!this.connections.contains(city))
}

public void removeConnection(City city) {
this.connections.remove(city);
}

public boolean contains(City city) {
return this.connections.contains(city);
}

public Pos getPos() {
return this.pos;
}

public void setPos(Pos pos) {
this.pos = pos;
}

public int getId() {
return this.id;
}

public void setId(int id) {
this.id = id;
}

public Color getColor() {
return this.color;
}

public ArrayList<City> getConnections() {
return this.connections;
}
}


The CityList Class

public class CityList extends ArrayList<City> {

private double[][] distances;
private Random r = new Random();

public CityList() {
}

public boolean isOccupied(Pos pos, City marked) {
for (int i = 0; i < this.size(); i++)   {
if(get(i).getPos().equals(pos) && !get(i).equals(marked))
return true;
}
return false;
}

public City getMarked(int x, int y) {
for (int i = size() - 1; i >= 0; i--) {
if (get(i).isMarked(x, y)) {
return get(i);
}
}
return null;
}

public int getDistance(City a, City b) {
int x = Math.abs(a.getPos().x() - b.getPos().x());
int y = Math.abs(a.getPos().y() - b.getPos().y());
double dist = Math.sqrt(Math.pow(x,2) + Math.pow(y,2));
return (int) Math.round(dist / CityPanel.UNIT);
}

while (this.isOccupied(city.getPos(), city)) {
city.setPos(new Pos());
}
}

public boolean remove(City city) {
for (City c : city.getConnections()) {
c.removeConnection(city);
}
boolean b = super.remove(city);
for (int i = 0; i < this.size(); i++) {
this.get(i).setId(i+1);
}
return b;
}
}


You might change from ArrayList to HashMap. That will give you better performance for large numbers of cities (for small numbers of cities, the overhead of using a HashMap can be more than what you gain over using the ArrayList).

I would also suggest adding a new variable to your CityList - a new HashMap that is indexed by Pos. Then your isOccupied function becomes:

public boolean isOccupied(Pos pos, City marked) {
//returns true only if there is a Pos p in the map so p.equals(marked.getPos()) is true.
return posMap.containsKey(marked.getPos());
}


Why?

In CityPanel, paintCities needs to iterate across all cities paintConnections needs to iterate across all connections, i.e. doubly iterate across your cities (this will be O(n^2) in the best case). paintDescriptions will be the same. addCities calls add() once for each city being generated. So it's O(n * complexity of add())

In City, addConnection calls contains() and add() - this will be O(n) because of contains() removeConnection calls remove() on the list of connections. contains is O(n) with an ArrayList.

CityList really only has a problem with isOccupied; it has to iterate through the entire list (so it's O(n)) in order to give an answer. add relies on isOccupied remove calls removeConnection() on every city in the list, i.e. O(n * cost of remove)