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 java.lang.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 Summary

    Constructors 
    Constructor Description
    HamiltonianCycleAlgorithmBase()  

  • Method Summary

    Modifier and Type Method Description
    protected void checkGraph​(Graph<V,​E> graph)
    Checks that graph is undirected, complete, and non-empty
    protected GraphPath<V,​E> closedVertexListToTour​(java.util.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.
    protected GraphPath<V,​E> edgeSetToTour​(java.util.Set<E> tour, Graph<V,​E> graph)
    Transform from a Set representation to a graph path.
    protected GraphPath<V,​E> getSingletonTour​(Graph<V,​E> graph)
    Creates a tour for a graph with 1 vertex
    protected void requireNotEmpty​(Graph<V,​E> graph)
    Checks that graph is not empty
    protected GraphPath<V,​E> vertexListToTour​(java.util.List<V> tour, Graph<V,​E> graph)
    Transform from a List representation to a graph path.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.jgrapht.alg.interfaces.HamiltonianCycleAlgorithm

    getTour

  • Constructor Details

  • Method Details

    • vertexListToTour

      protected GraphPath<V,​E> vertexListToTour​(java.util.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​(java.util.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​(java.util.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:
      java.lang.IllegalArgumentException - if graph is not undirected
      java.lang.IllegalArgumentException - if graph is not complete
      java.lang.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:
      java.lang.IllegalArgumentException - if graph contains no vertices