Package org.jgrapht.alg.tour
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 typeE
- 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 Summary
Constructors Constructor Description RandomTourTSP()
Construct with default random number generatorRandomTourTSP(java.util.Random rng)
Construct with specified random number generator
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description GraphPath<V,E>
getTour(Graph<V,E> graph)
Computes a tour using the greedy heuristic.-
Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
checkGraph, edgeSetToTour, getSingletonTour, vertexListToTour
-
-
-
-
Method Detail
-
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 undirectedjava.lang.IllegalArgumentException
- if the graph is not completejava.lang.IllegalArgumentException
- if the graph contains no vertices
-
-