TspMetricMSTAppx (JGAlgo - Parent 0.4.0 API)

java.lang.Object
- com.jgalgo.alg.TspMetricMSTAppx

All Implemented Interfaces:

TspMetric
```
public class TspMetricMSTAppx
extends Object
```
TSP \(2\)-approximation using MST.
An MST of a graph weight is less or equal to the optimal TSP tour. By doubling each edge in such MST and finding an Eulerian tour on these edges a tour was found with weight at most \(2\) times the optimal TSP tour. In addition, shortcuts are used if vertices are repeated in the initial Eulerian tour - this is possible only in the metric special case.
The running of this algorithm is \(O(n^2)\) and it achieve \(2\)-approximation to the optimal TSP solution.

Author:

Barak Ugav

Constructor Summary

Constructors
Constructor Description

TspMetricMSTAppx()
Create a new TSP \(2\)-approximation algorithm.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`<V,E> Path<V,E>`	`computeShortestTour(Graph<V,E> g, WeightFunction<E> w)`	Compute the shortest tour that visit all vertices.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - TspMetricMSTAppx
```
public TspMetricMSTAppx()
```
    Create a new TSP \(2\)-approximation algorithm.
- Method Detail
  - computeShortestTour
```
public <V,E> Path<V,E> computeShortestTour(Graph<V,E> g,
                                                       WeightFunction<E> w)
```
    Description copied from interface: TspMetric
    
    Compute the shortest tour that visit all vertices.
    Note that this problem is NP-hard and therefore the result is only the best approximation the implementation could find. If g is an IntGraph, a IPath object is returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.
    
    Specified by:
    
    computeShortestTour in interface TspMetric
    
    Type Parameters:
    
    V - the vertices type
    
    E - the edges type
    
    Parameters:
    
    g - a graph containing all the vertices the tour must visit, using its edges
    
    w - an edge weight function. In the metric world every three vertices \(u,v,w\) should satisfy \(w((u,v)) + w((v,w)) \leq w((u,w))$
    
    Returns:
    
    a result object containing the list of the \(n\) vertices ordered by the calculated path. If the graph contains no vertices, null is returned