Package com.jgalgo.alg.shortestpath

Class TspAbstract

java.lang.Object

com.jgalgo.alg.shortestpath.TspAbstract

All Implemented Interfaces:

Tsp

Direct Known Subclasses:

TspMetricMatchingAppx, TspMetricMstAppx

public abstract class TspAbstract
extends Object
implements Tsp

Abstract class for computing the shortest tour that visit all vertices in a graph.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
TspAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> Optional<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

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

Constructor Detail

TspAbstract

public TspAbstract()

Default constructor.

Method Detail

computeShortestTour

public <V,E> Optional<Path<V,E>> computeShortestTour(Graph<V,E> g,
                                                                 WeightFunction<E> w)

Description copied from interface: Tsp

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, an optional of IPath is returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

Specified by:

computeShortestTour in interface Tsp

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

Returns:

an optional of the tour calculated, or an empty optional if no such path was found