Class GreedyHeuristicTSP<V,E>

java.lang.Object
org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
org.jgrapht.alg.tour.GreedyHeuristicTSP<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,E>

public class GreedyHeuristicTSP<V,E> extends HamiltonianCycleAlgorithmBase<V,E>
The greedy heuristic algorithm for the TSP problem.

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?".

The Greedy heuristic gradually constructs a tour by repeatedly selecting the shortest edge and adding it to the tour as long as it doesn’t create a cycle with less than N edges, or increases the degree of any node to more than 2. We must not add the same edge twice of course.

The implementation of this class is based on:
Nilsson, Christian. "Heuristics for the traveling salesman problem." Linkoping University 38 (2003)

The runtime complexity of this class is $O(V^2 log(V))$.

This algorithm requires that the graph is complete.

  • Constructor Details

    • GreedyHeuristicTSP

      public GreedyHeuristicTSP()
  • Method Details

    • getTour

      public GraphPath<V,E> getTour(Graph<V,E> graph)
      Computes a tour using the greedy heuristic.
      Parameters:
      graph - the input graph
      Returns:
      a tour
      Throws:
      IllegalArgumentException - if the graph is not undirected
      IllegalArgumentException - if the graph is not complete
      IllegalArgumentException - if the graph contains no vertices
    • canAddEdge

      private boolean canAddEdge(Map<V,Integer> vertexDegree, UnionFind<V> tourSet, V vertex1, V vertex2, boolean lastEdge)
      Tests if an edge can be added. Returns false if it would increase the degree of a vertex to more than 2. Returns false if a cycle is created and we are not at the last edge, or false if we do not create a cycle and are at the last edge.
      Parameters:
      vertexDegree - A Map tracking the degree of each vertex in the tour
      tourSet - A UnionFind tracking the connectivity of the tour
      vertex1 - First vertex of proposed edge
      vertex2 - Second vertex of proposed edge
      lastEdge - true if we are looking for the last edge
      Returns:
      true if this edge can be added