Class RandomTourTSP<V,​E>

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

public class RandomTourTSP<V,​E>
extends HamiltonianCycleAlgorithmBase<V,​E>
Generate a random tour.

This class generates a random Hamiltonian Cycle. This is a simple unoptimised solution to the Travelling Salesman Problem, or more usefully is a starting point for optimising a tour using TwoOptHeuristicTSP.

Author:
Peter Harman, Dimitrios Michail
  • Constructor Details

    • RandomTourTSP

      public RandomTourTSP()
      Construct with default random number generator
    • RandomTourTSP

      public RandomTourTSP​(java.util.Random rng)
      Construct with specified random number generator
      Parameters:
      rng - The random number generator
  • 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:
      java.lang.IllegalArgumentException - if the graph is not undirected
      java.lang.IllegalArgumentException - if the graph is not complete
      java.lang.IllegalArgumentException - if the graph contains no vertices