 java.lang.Object

 org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>

 org.jgrapht.alg.tour.PalmerHamiltonianCycle<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,E>
public class PalmerHamiltonianCycle<V,E> extends HamiltonianCycleAlgorithmBase<V,E>
Palmer's algorithm for computing Hamiltonian cycles in graphs that meet Ore's condition. Ore gave a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilton cycle. Specifically, Ore's theorem considers the sum of the degrees of pairs of nonadjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196).
This is an implementation of the CRISSCROSS algorithm described by E. M. Palmer in his paper. The algorithm takes a simple graph that meets Ore's condition (see
GraphTests.hasOreProperty(Graph)
) and returns a Hamiltonian cycle. The algorithm runs in $O(V^3)$ time and uses $O(V)$ space. In contrast to the most other algorithms in this package this algorithm does only attempt to find any Hamiltonian cycle in the graph and does not attempt to find the shortest cycle. The advantage of this algorithm is that accepted graphs only need to meet Ore's condition which is less strict than the completeness requirement of most of the other algorithms.The original algorithm is described in: Palmer, E. M. (1997), "The hidden algorithm of Ore's theorem on Hamiltonian cycles", Computers & Mathematics with Applications, 34 (11): 113–119, doi:10.1016/S08981221(97)002253 See wikipedia for a short description of Ore's theorem and Palmer's algorithm.
 Author:
 Alexandru Valeanu, Hannes Wellmann


Constructor Summary
Constructors Constructor Description PalmerHamiltonianCycle()

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description GraphPath<V,E>
getTour(Graph<V,E> graph)
Computes a Hamiltonian tour.
Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour

