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 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 Summary

Constructors

Constructor	Description
RandomTourTSP()	Construct with default random number generator
RandomTourTSP(Random rng)	Construct with specified random number generator

Method Summary

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

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RandomTourTSP

public RandomTourTSP()

Construct with default random number generator

RandomTourTSP

public RandomTourTSP(Random rng)

Construct with specified random number generator

Parameters:

rng - The random number generator

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:

IllegalArgumentException - if the graph is not undirected

IllegalArgumentException - if the graph is not complete

IllegalArgumentException - if the graph contains no vertices