path-game/src/pathgame/algorithm/TravellingSalesAlg.java

package pathgame.algorithm;

import pathgame.gameplay.Player;
import pathgame.logging.Logger;
import pathgame.tilemap.TileMap;

import java.util.ArrayList;
import java.util.Collections;

/** Class for calculating an approximation of the travelling salesman problem, using the Christofides algorithm
 *
 */
public class TravellingSalesAlg {
    /** Calculates an approximation of the travelling salesman problem, using the Christofides algorithm
     *
     * @param map the TileMap that the algorithm should be used on
     * @param player that is traversing the map
     * @return
     */
    public static int calcSalesPathLen(TileMap map, Player player) {
        DijkstraMagic dijkstra = new DijkstraMagic(map, player);

        ArrayList<ArrayList<SaleRoute>> salesPitch = dijkstra.getSalesPitch();

        //make minimum spanning tree
        ArrayList<TreeEdge> MSTree = makeMSTree(salesPitch);

        //find pairs-shortest path for verteces with odd degree and add those edges to MSTree
        ArrayList<TreeEdge> oddDegEdges = makeOddDegEdges(MSTree, salesPitch);
        MSTree.addAll(oddDegEdges);

        //finde euler tour
        ArrayList<Integer> eulerTour = getEulerTour(MSTree);

        //cut short
        cutShort(eulerTour);

        Logger.onAlgoDone(salesPitch, eulerTour);

        //calculate the total weight of the tour using the edge table (salesPitch)
        int tourWeight = calcTourWeight(eulerTour, salesPitch);
        System.out.println("min cost: " + tourWeight);
        return tourWeight;

        //brute force
        //return bruteForce(salesPitch);
    }

    private static int calcTourWeight(ArrayList<Integer> tour, ArrayList<ArrayList<SaleRoute>> salesPitch) {
        int totalWeight = 0;

        for(int i = 0; i < tour.size()-1; i++) {
            int startNode, endNode;

            if(tour.get(i) < tour.get(i+1)) {
                startNode = tour.get(i);
                endNode = tour.get(i+1) - startNode - 1;
            }
            else {
                startNode = tour.get(i+1);
                endNode = tour.get(i) - startNode - 1;
            }
            totalWeight += salesPitch.get(startNode).get(endNode).getTotalCost();
        }
        return totalWeight;
    }

    private static void cutShort(ArrayList<Integer> eulerTour) {
        int counter = 2;

        while(counter < eulerTour.size()-1) {
            int current = eulerTour.get(counter);

            boolean found = false;

            for(int i = 0; i < counter; i++) {
                if(eulerTour.get(i) == current) {
                    found = true;
                    break;
                }
            }

            if(found) {
                eulerTour.remove(counter);
            }
            else {
                counter++;
            }
        }
    }

    private static ArrayList<Integer> getEulerTour(ArrayList<TreeEdge> graph) {
        ArrayList<Integer> tour = new ArrayList<>();

        while (graph.size() > 0) {
            if(tour.size() == 0) {
                tour = getSubtour(graph, graph.get(0).getSrc());
            }
            else {
                int start = -1;

                for(int e = 0; e < graph.size(); e++) {
                    TreeEdge edge = graph.get(e);
                    for(int tp = 0; tp < tour.size(); tp++) {
                        if(edge.getSrc() == tour.get(tp)) {
                            start = edge.getSrc();
                            break;
                        }
                        else if(edge.getDest() == tour.get(tp)) {
                            start = edge.getDest();
                            break;
                        }
                    }
                    if(start!= -1) {
                        break;
                    }
                }

                ArrayList<Integer> subTour = getSubtour(graph, start);

                mergeTours(tour, subTour);
            }
        }

        return tour;
    }

    private static ArrayList<Integer> getSubtour(ArrayList<TreeEdge> graph, int start) {
        ArrayList<Integer> tour = new ArrayList<>();
        tour.add(start);

        int pos = nextTourEdgePos(graph, start);
        int next = graph.get(pos).getOtherVertex(start);
        graph.remove(pos);
        tour.add(next);

        while (next != start) {
            pos = nextTourEdgePos(graph, next);
            next = graph.get(pos).getOtherVertex(next);
            graph.remove(pos);
            tour.add(next);
        }

        return tour;
    }

    private static int nextTourEdgePos(ArrayList<TreeEdge> graph, int vertex) {
        for(int i = 0; i < graph.size(); i++) {
            if(graph.get(i).getSrc() == vertex || graph.get(i).getDest() == vertex) {
                return i;
            }
        }

        return -1;
    }

    private static void mergeTours(ArrayList<Integer> tour, ArrayList<Integer> subTour) {
        int mergeTo = subTour.get(0);

        int mergePos = -1;

        for(int i = 0; i < tour.size(); i++) {
            if (tour.get(i) == mergeTo) {
                mergePos = i;
            }
        }

        for(int i = subTour.size()-1; i > 0; i--) {
            tour.add(mergePos+1, subTour.get(i));
        }
    }

    private static ArrayList<TreeEdge> makeOddDegEdges(ArrayList<TreeEdge> msTree, ArrayList<ArrayList<SaleRoute>> salesPitch) {
        int numOfEdges[] = new int[salesPitch.size()];

        for (int i = 0; i < msTree.size(); i++) {
            numOfEdges[msTree.get(i).getSrc()]++;
            numOfEdges[msTree.get(i).getDest()]++;
        }

        OddDegreeList oddDegs = new OddDegreeList();

        for (int i = 0; i < numOfEdges.length; i++) {
            //System.out.println(numOfEdges[i]);
            if (numOfEdges[i] % 2 == 1) {
                oddDegs.add(i);
            }
        }

        Permutation permut = new Permutation(oddDegs.size(), 2);

        calcPairShortest(oddDegs, salesPitch, permut, 0, 0);
        permut.makePermutMinimal();

        //System.out.println(permut.tempCounter1);
        //System.out.println(permut.tempCounter2);
        //System.out.println("min cost: " + permut.getMinCost());
        //permut.printPermut();

        ArrayList<TreeEdge> oddEdges = new ArrayList<>();
        oddDegs.resetUsed();
        for(int i = 0; i < permut.size(); i++) {
            int offSet = permut.getValAtPos(i);

            addOddEdge(oddEdges, oddDegs, salesPitch, offSet);
        }

        addOddEdge(oddEdges, oddDegs, salesPitch, 0);

        return oddEdges;
    }

    private static void addOddEdge(ArrayList<TreeEdge> oddEdges, OddDegreeList oddDegs, ArrayList<ArrayList<SaleRoute>> salesPitch, int offSet) {
        int orig = oddDegs.getUnused(0);
        oddDegs.makeOffsetUsed(0);
        int dest = oddDegs.getUnused(offSet);
        oddDegs.makeOffsetUsed(offSet);

        oddEdges.add(new TreeEdge(orig, dest, salesPitch.get(orig).get(dest - orig - 1).getTotalCost()));
    }

    private static void calcPairShortest(OddDegreeList oddDegs, ArrayList<ArrayList<SaleRoute>> salesPitch, Permutation permut, int permutPos, int costSoFar) {
        while(true) {
            int offSet;

            if(permutPos == permut.size()) {
                offSet = 0;
            }
            else {
                offSet = permut.getValAtPos(permutPos);
            }

            int orig = oddDegs.getUnused(0);
            int dest = oddDegs.getUnused(1 + offSet);

            int edgeWeight = salesPitch.get(orig).get(dest - orig - 1).getTotalCost();
            int newCost = costSoFar + edgeWeight;
            //permut.tempCounter1++;

            /*System.out.println();
            System.out.println("permut pos: " + permutPos);
            System.out.println(orig + " : " + dest);
            System.out.println("newCost: " + newCost);
            permut.printPermut();*/

            if(newCost < permut.getMinCost()) {
                if(permutPos == permut.size()) {
                    permut.setMinCost(newCost);
                    /*System.out.println();
                    System.out.println("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
                    System.out.println("New Min: " + newCost);
                    System.out.println("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");*/
                }
                else {
                    int used1 = oddDegs.makeOffsetUsed(0);
                    int used2 = oddDegs.makeOffsetUsed(offSet);
                    calcPairShortest(oddDegs, salesPitch, permut, permutPos+1, costSoFar+edgeWeight);
                    oddDegs.makeUnused(used1);
                    oddDegs.makeUnused(used2);
                }
            }

            if(permutPos == permut.size()) {
                //permut.tempCounter2++;
                break;
            }
            if(permut.isPosAtMax(permutPos)) {
                break;
            }

            permut.increaseAtPos(permutPos);
        }
    }

    private static ArrayList<TreeEdge> makeMSTree(ArrayList<ArrayList<SaleRoute>> salesPitch) {
        ArrayList<TreeEdge> allEdges = new ArrayList<>();
        ArrayList<TreeEdge> msTree = new ArrayList<>();

        int vertNum = salesPitch.size();

        for (int orig = 0; orig < salesPitch.size(); orig++) {
            for (int dest = 0; dest < salesPitch.get(orig).size(); dest++) {
                allEdges.add(new TreeEdge(orig, dest + 1 + orig, salesPitch.get(orig).get(dest).getTotalCost()));
                //System.out.println(edge.getSrc() + " " + edge.getDest() + " " + edge.getWeight());
                //System.out.println(salesPitch.get(orig).get(dest).getTotalCost());
            }
        }

        //System.out.println(vertNum);

        Collections.sort(allEdges);

        while (msTree.size() < vertNum - 1) {

            if (notCycle(msTree, allEdges.get(0))) {
                msTree.add(allEdges.get(0));
                //System.out.println(allEdges.get(0).getSrc() + " " + allEdges.get(0).getDest() + " " + allEdges.get(0).getWeight());
            }
            allEdges.remove(0);
        }

        return msTree;
    }

    private static void qEdges(ArrayList<TreeEdge> tree, ArrayList<TreeEdge> edgeQ, int vertex) {
        for(int i = 0; i < tree.size(); i++) {
            TreeEdge edge = tree.get(i);
            if(edge.getSrc() == vertex || edge.getDest() == vertex) {
                if(!edge.isChecked()) {
                    edgeQ.add(edge);
                    //System.out.println("src: " + edge.getSrc() + "; dest: " + edge.getDest());
                    edge.setChecked(true);
                }
            }
        }
    }

    private static boolean notCycle(ArrayList<TreeEdge> tree, TreeEdge additon) {
        ArrayList<TreeEdge> edgeQ = new ArrayList<>();
        int dest = additon.getDest();
        resetEdges(tree);

        qEdges(tree, edgeQ, additon.getSrc());

        while(edgeQ.size() > 0) {
            TreeEdge edge = edgeQ.get(0);
            edgeQ.remove(0);
            if(edge.getSrc() == dest || edge.getDest() == dest) {
                return false;
            }
            else {
                qEdges(tree, edgeQ, edge.getSrc());
                qEdges(tree, edgeQ, edge.getDest());
            }
        }

        return true;
    }

    private static void resetEdges(ArrayList<TreeEdge> tree) {
        for(int i = 0; i < tree.size(); i++) {
            tree.get(i).setChecked(false);
        }
    }
}