Module org.jgrapht.core

Package org.jgrapht.alg.interfaces

Interface HamiltonianPathAlgorithm<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Known Implementing Classes:

BacktrackingHamiltonianPath, DagHamiltonianPath, HamiltonianPathAlgorithmBase, HeldKarpHamiltonianPath

public interface HamiltonianPathAlgorithm<V,E>

An algorithm solving the Hamiltonian path problem.

A Hamiltonian path is a path in an undirected or directed graph that visits every vertex exactly once. Unlike a Hamiltonian cycle, a Hamiltonian path is not required to return to the start vertex. The path's endpoints may be any pair of vertices (or a single vertex if the graph has only one vertex).

Deciding whether a Hamiltonian path exists in a general graph is NP-complete. Implementations of this interface are therefore expected to use exact, exponential-time algorithms (possibly with pruning) or specialised polynomial-time algorithms for restricted graph classes. Callers should consult each implementation's JavaDoc for complexity and recommended graph sizes.

This interface is the path-specific counterpart of HamiltonianCycleAlgorithm. It is intentionally separate because the path problem does not require a return edge from the last visited vertex to the first, and because the existing cycle / tour APIs often assume tour or complete-graph semantics that are not appropriate for Hamiltonian paths.

Author:

seilat

Method Summary

Modifier and Type	Method	Description
HamiltonianPathSearchResult<V,E>	getPath(Graph<V,E> graph)	Computes a Hamiltonian path in the given graph and returns a tri-state HamiltonianPathSearchResult.

Method Details

getPath

HamiltonianPathSearchResult<V,E> getPath(Graph<V,E> graph)

Computes a Hamiltonian path in the given graph and returns a tri-state HamiltonianPathSearchResult.

The return value distinguishes:

• HamiltonianPathSearchResult.Status.PATH_FOUND — the algorithm produced a Hamiltonian path; it is accessible via HamiltonianPathSearchResult.getPath().
• HamiltonianPathSearchResult.Status.PROVEN_ABSENT — the algorithm ran to completion (or was rejected by a sound precheck) and proved that no Hamiltonian path exists.
• HamiltonianPathSearchResult.Status.ABORTED — the algorithm performed a bounded search that hit its limit before completing. Whether a Hamiltonian path exists in the graph is unknown.

Unbounded implementations only return PATH_FOUND or PROVEN_ABSENT. Implementations that accept an execution budget (e.g. a maximum state count) may also return ABORTED; such bounded variants must never report PROVEN_ABSENT for a search that was stopped early.

Parameters:

graph - the input graph

Returns:

a HamiltonianPathSearchResult describing the search outcome