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

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 Detail

HamiltonianCycleAlgorithmBase

public HamiltonianCycleAlgorithmBase()

Method Detail

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