org.jgrapht.alg.tour

Class PalmerHamiltonianCycle<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - 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 non-adjacent 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/S0898-1221(97)00225-3 See wikipedia for a short description of Ore's theorem and Palmer's algorithm.

Author:

Alexandru Valeanu

Constructor Summary

Constructors

Constructor and Description
PalmerHamiltonianCycle() Construct a new instance

Method Summary

Modifier and Type	Method and Description
GraphPath<V,E>	getTour(Graph<V,E> graph) Computes a Hamiltonian tour.

Methods inherited from class java.lang.Object

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

Constructor Detail

PalmerHamiltonianCycle

public PalmerHamiltonianCycle()

Construct a new instance

Method Detail

getTour

public GraphPath<V,E> getTour(Graph<V,E> graph)

Computes a Hamiltonian tour.

Specified by:

getTour in interface HamiltonianCycleAlgorithm<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)