TwoApproxMetricTSP (JGraphT : a free Java graph library)

java.lang.Object
- org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
- - org.jgrapht.alg.tour.TwoApproxMetricTSP<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

HamiltonianCycleAlgorithm<V,E>
```
public class TwoApproxMetricTSP<V,E>
extends HamiltonianCycleAlgorithmBase<V,E>
```
A 2-approximation algorithm for the metric 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?". In the metric TSP, the intercity distances satisfy the triangle inequality.
This is an implementation of the folklore algorithm which returns a depth-first ordering of the minimum spanning tree. The algorithm is a 2-approximation assuming that the instance satisfies the triangle inequality. The implementation requires the input graph to be undirected and complete. The running time is $O(|V|^2 \log |V|)$.
See wikipedia for more details.

Author:

Dimitrios Michail

- Constructor Summary
  
  Constructors
  Constructor Description
  
  TwoApproxMetricTSP()
- Method Summary
  
  All Methods Instance Methods Concrete Methods
  Modifier and Type Method Description
  
  GraphPath<V,E> getTour(Graph<V,E> graph)
  Computes a 2-approximate tour.
  - Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
    checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
  - Methods inherited from class java.lang.Object
    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - TwoApproxMetricTSP
```
public TwoApproxMetricTSP()
```
- Method Detail
  - getTour
```
public GraphPath<V,E> getTour(Graph<V,E> graph)
```
    Computes a 2-approximate tour.
    
    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