Module org.jgrapht.core
Package org.jgrapht.alg.tour

Class HamiltonianCycleAlgorithmBase<V,E>

java.lang.Object
org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,E>
Direct Known Subclasses:
ChristofidesThreeHalvesApproxMetricTSP, GreedyHeuristicTSP, HeldKarpTSP, NearestInsertionHeuristicTSP, NearestNeighborHeuristicTSP, PalmerHamiltonianCycle, RandomTourTSP, TwoApproxMetricTSP, TwoOptHeuristicTSP
public abstract class HamiltonianCycleAlgorithmBase<V,E> extends Object implements HamiltonianCycleAlgorithm<V,E>
Base class for TSP solver algorithms.

This class provides implementations of utilities for TSP solver classes.

Author:
Peter Harman, Hannes Wellmann

  • Constructor Details

    • HamiltonianCycleAlgorithmBase

      public HamiltonianCycleAlgorithmBase()

  • Method Details

    • vertexListToTour

      protected GraphPath<V,E> vertexListToTour(List<V> tour, Graph<V,E> graph)
      Transform from a List representation to a graph path.
      Parameters:
      tour - a list containing the vertices of the tour (is modified)
      graph - the graph
      Returns:
      a graph path

    • closedVertexListToTour

      protected GraphPath<V,E> closedVertexListToTour(List<V> tour, Graph<V,E> graph)
      Transform from a closed List representation (first and last vertex element are the same) to a graph path.
      Parameters:
      tour - a closed list containing the vertices of the tour
      graph - the graph
      Returns:
      a graph path

    • edgeSetToTour

      protected GraphPath<V,E> edgeSetToTour(Set<E> tour, Graph<V,E> graph)
      Transform from a Set representation to a graph path.
      Parameters:
      tour - a set containing the edges of the tour
      graph - the graph
      Returns:
      a graph path

    • getSingletonTour

      protected GraphPath<V,E> getSingletonTour(Graph<V,E> graph)
      Creates a tour for a graph with 1 vertex
      Parameters:
      graph - The graph
      Returns:
      A tour with a single vertex

    • checkGraph

      protected void checkGraph(Graph<V,E> graph)
      Checks that graph is undirected, complete, and non-empty
      Parameters:
      graph - the graph
      Throws:
      IllegalArgumentException - if graph is not undirected
      IllegalArgumentException - if graph is not complete
      IllegalArgumentException - if graph contains no vertices

    • requireNotEmpty

      protected void requireNotEmpty(Graph<V,E> graph)
      Checks that graph is not empty
      Parameters:
      graph - the graph
      Throws:
      IllegalArgumentException - if graph contains no vertices