1
\$\begingroup\$

This snippet is about two (brute-force) algorithms for solving the traveling salesman problem. Since there is plenty of boiler-plate code, I arranged a GitHub repository for the entire program, in case someone would like to run it.

But these are the classes I would like to get reviewed:

(Asymmetric means that the arcs between two nodes do not necessarily have the same cost. Even more, some arcs are allowed to be absent as long their absence does not make the graph disconnected; each such missing arc is added to the actual graph with the weight of the shortest path cost between the terminal nodes of the arc.)

AsymmetricTSPSolver.java:

package net.coderodde.graph.tsp;

import java.util.List;
import net.coderodde.graph.DirectedGraph;

/**
 * This interface defines the API for the algorithms solving asymmetric 
 * traveling salesman problem.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 20, 2016)
 */
public abstract class AsymmetricTSPSolver {

    public abstract List<Integer> solve(final DirectedGraph graph);

    public static double getTourCost(final DirectedGraph graph, 
                                     final List<Integer> tour) {
        double cost = 0.0;

        for (int i = 0; i < tour.size(); ++i) {
            cost += graph.getEdgeWeight(tour.get(i), 
                                        tour.get((i + 1) % tour.size()));
        }

        return cost;
    }
}

TSPGraphPreprocessor.java:

package net.coderodde.graph.tsp;

import java.util.List;
import java.util.Set;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.shortestpath.ShortestPathFinder;
import net.coderodde.graph.shortestpath.support.DijkstraShortestPathFinder;

/**
 * This class provides a method for converting a directed graph into a complete
 * directed graph. For each arc that does not appear in the input graph, this
 * class facilities compute a shortest path between the terminal nodes of the 
 * arc, and adds a missing arc with the weight set to the shortest distance.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 21, 2016)
 */
public class TSPGraphPreprocessor {

    public DirectedGraph preprocessGraph(final DirectedGraph graph) {
        final DirectedGraph workGraph = new DirectedGraph();
        final ShortestPathFinder shortestPathFinder = 
                new DijkstraShortestPathFinder();

        for (final Integer node : graph.getAllNodes()) {
            workGraph.addNode(node);
        }

        final Set<Integer> nodeSet = graph.getAllNodes();

        for (final Integer nodeA : nodeSet) {
            for (final Integer nodeB : nodeSet) {
                if (nodeA.equals(nodeB)) {
                    continue;
                }

                if (graph.hasEdge(nodeA, nodeB)) {
                    workGraph.addEdge(nodeA, 
                                      nodeB, 
                                      graph.getEdgeWeight(nodeA, 
                                                          nodeB));
                } else {
                    final List<Integer> shortestPath = 
                            shortestPathFinder.findShortestPath(graph,
                                                                nodeA, 
                                                                nodeB);
                    if (shortestPath.isEmpty()) {
                        throw new IllegalArgumentException(
                                "The input graph is not connected.");
                    }

                    workGraph.addEdge(nodeA, 
                                      nodeB, 
                                      getPathCost(graph, shortestPath));
                }
            }
        }

        return workGraph;
    }

    private double getPathCost(final DirectedGraph graph,
                               final List<Integer> path) {
        double cost = 0.0;

        for (int i = 0; i < path.size() - 1; ++i) {
            cost += graph.getEdgeWeight(path.get(i), path.get(i + 1));
        }

        return cost;
    }
}

DefaultAsymmetricTSPSolver.java:

package net.coderodde.graph.tsp.support;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.tsp.AsymmetricTSPSolver;

/**
 * This class implements a default asymmetric traveling salesman problem solver.
 * It checks to see that the input graph is connected, after which it computes
 * the missing arcs in the graph. Since the graph becomes fully connected, it
 * proceeds to computing the shortest tour over the graph.
 * <p>
 * Note that this class maintains state, so that if you need to run the
 * algorithm in parallel, make sure that each thread constructs its own instance
 * of this class.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 20, 2018)
 */
public final class DefaultAsymmetricTSPSolver extends AsymmetricTSPSolver {

    private DirectedGraph graph;
    private double bestTourLength;
    private double tentativeTourCost;
    private final List<Integer> bestTour      = new ArrayList<>();
    private final Set<Integer> visitedNodeSet = new HashSet<>();
    private final List<Integer> tentativeTour = new ArrayList<>();

    @Override
    public List<Integer> solve(final DirectedGraph graph) {
        Objects.requireNonNull(graph, "The input graph is null.");

        if (graph.size() == 0) {
            throw new IllegalArgumentException("The input graph is empty.");
        }

        return findShortestTour(graph);
    }

    private List<Integer> findShortestTour(final DirectedGraph graph) {
        init(graph);
        findShortestTour();
        return new ArrayList<>(bestTour);
    }

    private void init(final DirectedGraph graph) {
        this.graph = graph;
        bestTour.clear();
        tentativeTour.clear();
        visitedNodeSet.clear();
        bestTourLength = Double.POSITIVE_INFINITY;
        tentativeTourCost = 0.0;
    }

    private void findShortestTour() {
        for (final Integer node : graph.getAllNodes()) {
            if (!visitedNodeSet.contains(node)) {
                double tmp;

                if (visitedNodeSet.size() >= 1) {
                    tmp = graph.getEdgeWeight(lastOf(tentativeTour), node);
                } else {
                    tmp = 0.0;
                }

                tentativeTourCost += tmp;
                visitedNodeSet.add(node);
                tentativeTour.add(node);

                if (visitedNodeSet.size() == graph.size()) {
                    // Add the cost of the last arc that goes from last visited
                    // node to the very first visited node.
                    final double concludingArcWeight = 
                            graph.getEdgeWeight(lastOf(tentativeTour),
                                                firstOf(tentativeTour));

                    tentativeTourCost += concludingArcWeight;

                    if (bestTourLength > tentativeTourCost) {
                        bestTourLength = tentativeTourCost;
                        bestTour.clear();
                        bestTour.addAll(tentativeTour);
                    }

                    tentativeTourCost -= concludingArcWeight;
                } else {
                    findShortestTour();
                }

                visitedNodeSet.remove(node);
                removeLast(tentativeTour);
                tentativeTourCost -= tmp;
            }
        }
    }

    private static <T> T firstOf(final List<T> list) {
        return list.get(0);
    }

    private static <T> T lastOf(final List<T> list) {
        return list.get(list.size() - 1);
    }

    private static <T> void removeLast(final List<T> list) {
        list.remove(list.size() - 1);
    }
}

IterativeAsymmetricTSPSolver.java:

package net.coderodde.graph.tsp.support;

import java.util.ArrayList;
import java.util.List;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.tsp.AsymmetricTSPSolver;

/**
 * This class implements a brute-force nonrecursive algorithm for solving the
 * traveling salesman problem.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 21, 2016)
 */
public class IterativeAsymmetricTSPSolver extends AsymmetricTSPSolver {

    @Override
    public List<Integer> solve(final DirectedGraph graph) {
        final PermutationIterable<Integer> iterable = 
                new PermutationIterable<>(
                        new ArrayList<>(graph.getAllNodes()));

        double bestTourCost = Double.POSITIVE_INFINITY;
        List<Integer> bestTour = new ArrayList<>(graph.getAllNodes());

        for (final List<Integer> tour : iterable) {
            final double currentTourCost = getTourCost(graph, tour);

            if (bestTourCost > currentTourCost) {
                bestTourCost = currentTourCost;
                bestTour = tour;
            }
        }

        return bestTour;
    }
}

Critique request

Please tell me anything that comes to mind.

\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.