Module org.jgrapht.core

Package org.jgrapht.alg.tour

package org.jgrapht.alg.tour

Graph tours and Hamiltonian path related algorithms.

This package groups algorithms for traversing every vertex of a graph exactly once. Two related but distinct problems live here:

• Hamiltonian cycle / tour — closed traversals that return to the start vertex. Implementations include PalmerHamiltonianCycle, HeldKarpTSP, and the various TSP heuristics; they share the HamiltonianCycleAlgorithm interface and the HamiltonianCycleAlgorithmBase helper class.
• Hamiltonian path — open traversals that need not return to the start vertex. Implementations include BacktrackingHamiltonianPath, HeldKarpHamiltonianPath, and DagHamiltonianPath; they share the HamiltonianPathAlgorithm interface and the HamiltonianPathAlgorithmBase helper class.

Deciding whether a Hamiltonian path or cycle exists in a general graph is NP-complete. The exact algorithms in this package run in exponential time in the worst case; the polynomial special cases (such as DagHamiltonianPath) and structural prechecks document their scope individually.

Related Packages

Package	Description
org.jgrapht.alg	Algorithms provided with JGraphT.

Classes

Class	Description
BacktrackingHamiltonianPath<V,E>	Exact backtracking algorithm for the Hamiltonian path problem on directed and undirected graphs.
ChristofidesThreeHalvesApproxMetricTSP<V,E>	A $3/2$-approximation algorithm for the metric TSP problem.
DagHamiltonianPath<V,E>	Polynomial-time Hamiltonian path algorithm for directed acyclic graphs.
FarthestInsertionHeuristicTSP<V,E>	The farthest insertion heuristic algorithm for the TSP problem.
GreedyHeuristicTSP<V,E>	The greedy heuristic algorithm for the TSP problem.
HamiltonianCycleAlgorithmBase<V,E>	Base class for TSP solver algorithms.
HamiltonianPathAlgorithmBase<V,E>	Base class for HamiltonianPathAlgorithm implementations.
HeldKarpHamiltonianPath<V,E>	Dynamic-programming algorithm for the Hamiltonian path problem.
HeldKarpTSP<V,E>	A dynamic programming algorithm for the TSP problem.
NearestInsertionHeuristicTSP<V,E>	The nearest insertion heuristic algorithm for the TSP problem.
NearestNeighborHeuristicTSP<V,E>	The nearest neighbour heuristic algorithm for the TSP problem.
PalmerHamiltonianCycle<V,E>	Palmer's algorithm for computing Hamiltonian cycles in graphs that meet Ore's condition.
RandomTourTSP<V,E>	Generate a random tour.
TwoApproxMetricTSP<V,E>	A 2-approximation algorithm for the metric TSP problem.
TwoOptHeuristicTSP<V,E>	The 2-opt heuristic algorithm for the TSP problem.