GreedyHeuristicTSP (JGraphT : a free Java graph library)

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.

Author:

Peter Harman

- Constructor Summary
  
  Constructors
  Constructor Description
  
  GreedyHeuristicTSP()
- 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
  - Methods inherited from class java.lang.Object
    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - GreedyHeuristicTSP
```
public GreedyHeuristicTSP()
```
- 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 undirected
    
    java.lang.IllegalArgumentException - if the graph is not complete
    
    java.lang.IllegalArgumentException - if the graph contains no vertices