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 Details

    • TspAbstract

      public TspAbstract()
      Default constructor.

  • Method Details

    • 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