6
\$\begingroup\$

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);
        this.addMouseListener(this);
        this.addMouseMotionListener(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

    public void addCities(int number) {
        this.cityList.clear();
        for (int i = 1; i <= number; i++) {
            this.cityList.add(new City(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++) {
                this.cityList.get(i).addConnection(this.cityList.get(k));
                this.cityList.get(k).addConnection(this.cityList.get(i));
            }
        }
        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);
            this.bestTrail.add(temp.get(r));
            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)   {
                city.addConnection(this.marked);
                this.marked.addConnection(city);
            }
        }
        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;
    }

    public void addConnection(City city) {
        if (!this.connections.contains(city))
            this.connections.add(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);
    }

    public boolean add(City city) {
        while (this.isOccupied(city.getPos(), city)) {
            city.setPos(new Pos());
        }
        return super.add(city);
    }

    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;
    }
}
\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

Thank you for the answer. I have added a new HashMap indexed by Pos as you have explained and also changed the function isOccupied. But since I do not have more than 144 cities to deal with, I think this isn't necessary. I have made a little performance test to compare both possibilities of isOccupied and there was no time difference. So I think to change the CityList to a 'CityMap' is also not necessary for the same reasons.

Please correct me if I am wrong or if i have missed something.

And what about the realization of the connections. Do have ideas to improve this or maybe a complete new possibility?

\$\endgroup\$
  • 1
    \$\begingroup\$ If you'd like further review on updated code, please post it as a new question. Also, as the OP, you are able to add comments on answers to your own questions. The answers section is reserved for answers only. \$\endgroup\$ – Jamal Jan 4 '14 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.