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

package pathgame.algorithm;

import pathgame.gameplay.Player;
import pathgame.tilemap.TileMap;
import java.util.ArrayList;
import java.util.Collections;

public class TravellingSalesAlg {
    public static int calcSalesPathLen(TileMap map, Player player) {
        DijkstraMagic dijkstra = new DijkstraMagic(map, player);
        ArrayList<ArrayList<SaleRoute>> salesPitch = dijkstra.getSalesPitch();
        ArrayList<TreeEdge> MSTree = makeMSTree(salesPitch);
        ArrayList<TreeEdge> oddDegEdges = makeOddDegEdges(MSTree, salesPitch);
        MSTree.addAll(oddDegEdges);
        ArrayList<Integer> eulerTour = getEulerTour(MSTree);
        cutShort(eulerTour);
        int tourWeight = calcTourWeight(eulerTour, salesPitch);
        return tourWeight;
    }

    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.isEmpty()) {
                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++) {
            if(numOfEdges[i] % 2 == 1) {
                oddDegs.add(i);
            }
        }
        Permutation permut = new Permutation(oddDegs.size(), 2);
        calcPairShortest(oddDegs, salesPitch, permut, 0, 0);
        permut.makePermutMinimal();
        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;
            if(newCost < permut.getMinCost()) {
                if(permutPos == permut.size()) {
                    permut.setMinCost(newCost);
                } 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()) {
                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()));
            }
        }
        Collections.sort(allEdges);
        while(msTree.size() < vertNum - 1) {
            if(notCycle(msTree, allEdges.get(0))) {
                msTree.add(allEdges.get(0));
            }
            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);
                    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);
        }
    }
}