TSP

package aps2.tsp;
class Node{
    int id;
    int x;
    int y;
    Node(int x,int y,int id){
        this.id = id;
        this.x = x;
        this.y = y;
    }
}
public class TravellingSalesman {
    int N;
    int[] optimal;
    int added;
    double resDist;
    Node nodes[];
    public TravellingSalesman() {
        N=0;
        nodes = new Node[100];
    }
    /**
     * To solve the travelling salesman problem (TSP) you need to find a shortest
     * tour over all nodes in the graph where each node must be visited exactly
     * once. You need to finish at the origin node.
     *
     * In this task we will consider complete undirected graphs only with
     * Euclidean distances between the nodes.
     */

    /**
     * Adds a node to a graph with coordinates x and y. Assume the nodes are
     * named by the order of insertion.
     *
     * @param x X-coordinate
     * @param y Y-coordinate
     */
    public void addNode(int x, int y){
        Node n = new Node(x,y,N);
        nodes[N] = n;
        N++;
    }

    /**
     * Returns the distance between nodes v1 and v2.
     *
     * @param v1 Identifier of the first node
     * @param v2 Identifier of the second node
     * @return Euclidean distance between the nodes
     */
    public double getDistance(int v1, int v2) {
        return Math.sqrt(Math.pow(nodes[v1].x - nodes[v2].x, 2)+Math.pow(nodes[v1].y - nodes[v2].y, 2));
    }

    /**
     * Finds and returns an optimal shortest tour from the origin node and
     * returns the order of nodes to visit.
     *
     * Implementation note: Avoid exploring paths which are obviously longer
     * than the existing shortest tour.
     *
     * @param start Index of the origin node
     * @return List of nodes to visit in specific order
     */
    void utilCalc(int pos,int count,boolean visited) {
        if(count == N) {

            return;
        }
    }
    public int[] calculateExactShortestTour(int start){
        boolean visited[] = new boolean[N];
        visited[start] = true;
        utilCalc(start);
        return optimal;
    }
    /**
     * Returns an optimal shortest tour and returns its distance given the
     * origin node.
     *
     * @param start Index of the origin node
     * @return Distance of the optimal shortest TSP tour
     */
    public double calculateExactShortestTourDistance(int start){
        //calculateExactShortestTour(start);
        return resDist;
    }

    /**
     * Returns an approximate shortest tour and returns the order of nodes to
     * visit given the origin node.
     *
     * Implementation note: Use a greedy nearest neighbor apporach to construct
     * an initial tour. Then use iterative 2-opt method to improve the
     * solution.
     *
     * @param start Index of the origin node
     * @return List of nodes to visit in specific order
     */
    public int[] calculateApproximateShortestTour(int start){
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Returns an approximate shortest tour and returns its distance given the
     * origin node.
     *
     * @param start Index of the origin node
     * @return Distance of the approximate shortest TSP tour
     */
    public double calculateApproximateShortestTourDistance(int start){
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Constructs a Hamiltonian cycle by starting at the origin node and each
     * time adding the closest neighbor to the path.
     *
     * Implementation note: If multiple neighbors share the same distance,
     * select the one with the smallest id.
     *
     * @param start Origin node
     * @return List of nodes to visit in specific order
     */
    public int[] nearestNeighborGreedy(int start){
        int[] res = new int[N+1];
        boolean visited[] = new boolean[N];
        res[0] = start; visited[start] = true;
        int prev = start;
        for(int i=1;i<N;i++) {
            int next = -1;
            double min = Integer.MAX_VALUE;
            for(int j=0;j<N;j++) {
                double tempDist = getDistance(prev,j);
                if(!visited[j] && tempDist <= min) {
                    min=tempDist;
                    next = j;
                }
            }
            visited[next] = true;
            res[i] = next;
            prev = next;
        }
        res[N] = start;
        return res;
    }

    /**
     * Improves the given route using 2-opt exchange.
     *
     * Implementation note: Repeat the procedure until the route is not
     * improved in the next iteration anymore.
     *
     * @param route Original route
     * @return Improved route using 2-opt exchange
     */
    private int[] twoOptExchange(int[] route) {
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Swaps the nodes i and k of the tour and adjusts the tour accordingly.
     *
     * Implementation note: Consider the new order of some nodes due to the
     * swap!
     *
     * @param route Original tour
     * @param i Name of the first node
     * @param k Name of the second node
     * @return The newly adjusted tour
     */
    public int[] twoOptSwap(int[] route, int i, int k) {
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Returns the total distance of the given tour i.e. the sum of distances
     * of the given path add the distance between the final and initial node.
     *
     * @param tour List of nodes in the given order
     * @return Travelled distance of the tour
     */
    public double calculateDistanceTravelled(int[] tour){
        double distanceTurn = 0;
        for(int i=0;i<N;i++) distanceTurn += getDistance(tour[i],tour[i+1]);
        return distanceTurn;
    }

}