Travelling Salesman Problem- Drawing graphics

[kal_crazy]

This is the code that I have done so far:

import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;

class TSP extends JPanel{

    int weight[][],n,tour[],optDist;
    final int INF=1000;

public TSP(){

    Scanner s=new Scanner(System.in);
    Random r = new Random();
    System.out.println("Enter no. of Cities:=>");
    n=s.nextInt();
    weight=new int[n][n];
    tour=new int[n-1];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j){
                //System.out.print("Enter weight of "+(i+1)+" to "+(j+1)+":=>");
                weight[i][j]=1+r.nextInt(100);
            }
        }
}
    System.out.println();
    System.out.println("Starting node assumed to be node 1.");
    eval();
}

public int DIST(int currentNode,int inputSet[],int setSize){

    if(setSize==0)
        return weight[currentNode][0];
    int min=INF,minindex=0;
    int setToBePassedOnToNextCallOfDIST[]=new int[n-1];
    for(int i=0;i<setSize;i++){
        int k=0;//initialise new set
        for(int j=0;j<setSize;j++){
            if(inputSet[i]!=inputSet[j])
                setToBePassedOnToNextCallOfDIST[k++]=inputSet[j];
            }
            int temp=DIST(inputSet[i],setToBePassedOnToNextCallOfDIST,setSize-1);
            if((weight[currentNode][inputSet[i]]+temp) < min){
                min=weight[currentNode][inputSet[i]]+temp;
                minindex=inputSet[i];
            }
        }
        return min;
}

public int MIN(int currentNode,int inputSet[],int setSize){
    if(setSize==0)
        return weight[currentNode][0];

    int min=INF,minindex=0;
    int setToBePassedOnToNextCallOfCOST[]=new int[n-1];
    for(int i=0;i<setSize;i++){//considers each node of inputSet
        int k=0;
        for(int j=0;j<setSize;j++){
            if(inputSet[i]!=inputSet[j])
                setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];
        }
        int temp=DIST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);
        if((weight[currentNode][inputSet[i]]+temp) < min){
            min=weight[currentNode][inputSet[i]]+temp;
            minindex=inputSet[i];
        }
    }
    return minindex;
}

public void eval(){
    int dummySet[]=new int[n-1];
    for(int i=1;i<n;i++)
        dummySet[i-1]=i;
    optDist=DIST(0,dummySet,n-1);
    constructTour();
}

public void constructTour(){
    int previousSet[]=new int[n-1];
    int nextSet[]=new int[n-2]; 
    for(int i=1;i<n;i++)
        previousSet[i-1]=i;
    int setSize=n-1;
    tour[0]=MIN(0,previousSet,setSize);
    for(int i=1;i<n-1;i++){
        int k=0;
        for(int j=0;j<setSize;j++){
            if(tour[i-1]!=previousSet[j])
                nextSet[k++]=previousSet[j];
        }
        --setSize;
        tour[i]=MIN(tour[i-1],nextSet,setSize);
        for(int j=0;j<setSize;j++)
            previousSet[j]=nextSet[j];
    }
    display();
}

public void display(){
    System.out.println();
    System.out.print("The tour is 1-");
    for(int i=0;i<n-1;i++)
        System.out.print((tour[i]+1)+"-");
        System.out.print("1");
        System.out.println();
        System.out.println("The optimal distance is "+optDist);
    }


}



}

This code is able to output the correct tour with the optimal distance.

Output example:

Enter no. of Cities:=>
9

Starting node assumed to be node 1.

The tour is 1-5-4-2-6-9-3-8-7-1
The optimal distance is 186

Now I have to draw the Optimal tour on a graphics window using Java Swing.

I tried using this code:

    public void paintComponent(Graphics g){
        super.paintComponent(g);
        this.setBackground(Color.WHITE);

        g.setColor(Color.BLACK);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
             Dimension size = getSize();
             Insets insets = getInsets();

             int w = size.width - insets.left - insets.right;
             int h = size.height - insets.top - insets.bottom;

             //Random r = new Random();
             //int x = Math.abs(1+r.nextInt(100)) % w;
             //int y = Math.abs(1+r.nextInt(100)) % h;
             int x=weight[0][j];
             int y=weight[i][0];

            g.fillOval(x, y, 6, 6);
            }

        }

However, it is not able to show the optimal tour.

Example of required graphical window

Click Here

By the way this is the first time I am doing projects in Java Language.

[JamesCherrill]

Do you understand what that code does? Have you been able to use it to draw some ovals or anything else? Do you have any data that defines the position/location of each Node?

[kal_crazy]

I was able to get some ovals but they are all scrunched up all in one corner of the window.

Actually the weight[][] is suppose to hold the co-ordinates/ position of the cities.

I changed the paintComponent method so now the cities are aligning in one diagonal line.

Any suggestions?

[JamesCherrill]

That's a good start! At least we don't have to striggle with basic Swing concepts!
It looked to me like the weight array holds the distance/cost bewteen each pair of cities, yes? (It's size is n^2). I was looking for some data that holds an x and a y coordinate for each city (size 2*n). You need that to know where to draw each city because your paint routine needs to look something like this (pseudocode):

for each city
   draw a small box (or circle etc) at the x,y coordinates of the city
for each step in the tour
   draw a line from (x,y coords of the city at the start of this step) to (x,y coords of the city at the destination of this step)

[kal_crazy]

Thank you sir. The program is able to show the cities now.

And I tried implementing the drawLine method but the lines are joining to only one city from other cities which does not show the appropriate tour taken.

I am not sure how should I use the tour[] to draw a line.

Any suggestions?

[JamesCherrill]

I assume your tour[] array just contains the city numbers in the right order, yes?

so the first line to draw is from (the x,y coords of the city identified in tour[0]) to (the x,y coords of the city identified in tour[1]). The second line is from (... tour[1]) to (... tour[2]) etc ... I'm sure you can see the pattern there and how to code that loop?

ps please don't call me "sir"
!

[kal_crazy]

Thank You again JamesCherrill. The program is now able to connect the cities with the path.

I used the drawPolyLines method. However, it does not return to city number 1.

[JamesCherrill]

You can replace your drawPolyLines with a drawPolygon if you want the path to be closed.

[kal_crazy]

What I had done was:
After drawPolyLines i wrote drawLine from n-1(last city) to n(city 1) in the tour[]. This way also worked but i think it drew many lines from n-1 to n.

drawPolygon works perfectly.