Class PalmerHamiltonianCycle<V,E>
 java.lang.Object

 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 Object implements HamiltonianCycleAlgorithm<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 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^2)$ time and uses $O(V)$ space.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


Constructor Summary
Constructors Constructor Description PalmerHamiltonianCycle()
Construct a new instance

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.



Method Detail

getTour
public GraphPath<V,E> getTour(Graph<V,E> graph)
Computes a Hamiltonian tour. Specified by:
getTour
in interfaceHamiltonianCycleAlgorithm<V,E>
 Parameters:
graph
 the input graph Returns:
 a Hamiltonian tour
 Throws:
IllegalArgumentException
 if the graph doesn't meet Ore's condition See Also:
GraphTests.hasOreProperty(Graph)

