Module org.jgrapht.core
Package org.jgrapht.alg.tour

Class HeldKarpHamiltonianPath<V,E>

java.lang.Object
org.jgrapht.alg.tour.HamiltonianPathAlgorithmBase<V,E>
org.jgrapht.alg.tour.HeldKarpHamiltonianPath<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
HamiltonianPathAlgorithm<V,E>
public class HeldKarpHamiltonianPath<V,E> extends HamiltonianPathAlgorithmBase<V,E>
Dynamic-programming algorithm for the Hamiltonian path problem.

The implementation follows the classic Held-Karp subset DP, adapted to find a Hamiltonian path rather than a Hamiltonian cycle. The state dp[subset][v] is true when there exists a simple path that visits exactly the vertices in subset and whose last vertex is v. The transition extends a path ending at v by a new vertex u whenever the edge (v, u) exists and u is not yet in the subset. A Hamiltonian path exists if and only if dp[fullMask][v] is true for some v.

The subset-DP formulation is due to Held and Karp, "A Dynamic Programming Approach to Sequencing Problems", J. SIAM 10(1), 1962, and independently to Bellman, "Dynamic Programming Treatment of the Travelling Salesman Problem", J. ACM 9(1), 1962. The Hamiltonian-path variant (where the DP does not need a closing edge back to the start) is a standard textbook adaptation; see for example CLRS, "Introduction to Algorithms" (4th ed.), the dynamic-programming chapter, and the MIT 6.s078 lecture notes on advanced algorithms (lecture 17).

Complexity is O(n^2 * 2^n) time and O(n * 2^n) space, where n is the number of vertices. Because the running time and memory grow exponentially in n, this class refuses graphs with more than getMaxVertices() vertices by throwing IllegalArgumentException. The default ceiling is DEFAULT_MAX_VERTICES; the single-argument constructor lets callers opt in to a higher ceiling up to HARD_MAX_VERTICES when they have the memory headroom. Callers handling larger graphs should use BacktrackingHamiltonianPath instead and accept the lack of polynomial-bound guarantees.

The algorithm is exact and deterministic. It supports directed and undirected graphs and tolerates parallel edges and self-loops (self-loops are ignored because they cannot extend a simple path). In multigraphs, parallel edges between the same vertex pair collapse to a single DP transition; the returned path uses an arbitrary representative edge selected via Graph.getEdge(V, V) and is not weight-optimised across parallel edges.

Author:
seilat

  • Field Details

    • DEFAULT_MAX_VERTICES

      public static final int DEFAULT_MAX_VERTICES
      Default ceiling on the number of vertices. With n = 20 the DP table requires roughly 20 * 2^20 = ~20M entries; the constant is chosen to keep memory and runtime within practical limits.
      See Also:

    • HARD_MAX_VERTICES

      public static final int HARD_MAX_VERTICES
      Hard upper bound on the number of vertices, fixed by the algorithm's use of a int subset bitmask. Above n = 30 the bitmask space overflows Integer.MAX_VALUE; in practice memory is the dominant constraint well before this ceiling.
      See Also:

  • Constructor Details

    • HeldKarpHamiltonianPath

      public HeldKarpHamiltonianPath()
      Constructs a new instance with the default vertex ceiling (DEFAULT_MAX_VERTICES).

    • HeldKarpHamiltonianPath

      public HeldKarpHamiltonianPath(int maxVertices)
      Constructs a new instance that accepts graphs with up to maxVertices vertices.
      Parameters:
      maxVertices - upper bound on the number of vertices the algorithm will accept; must be at least 1 and at most HARD_MAX_VERTICES
      Throws:
      IllegalArgumentException - if maxVertices is outside the allowed range

  • Method Details

    • getMaxVertices

      public int getMaxVertices()
      Returns the maximum number of vertices this instance will accept.
      Returns:
      configured vertex ceiling

    • getStatesExpanded

      public long getStatesExpanded()
      Returns the number of DP states (predecessor cells initialised) the algorithm filled during the most recent call to getPath(Graph). Intended for diagnostics; the exact counting semantics may change if the implementation changes.
      Returns:
      DP states filled during the last search

    • getPath

      public HamiltonianPathSearchResult<V,E> getPath(Graph<V,E> graph)
      Description copied from interface: HamiltonianPathAlgorithm
      Computes a Hamiltonian path in the given graph and returns a tri-state HamiltonianPathSearchResult.

      The return value distinguishes:

      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