Hamiltonian path solver — feedback before opening a PR?

[Shai Eilat]

Hi all,

I have a feature branch on my fork that adds exact Hamiltonian path algorithms to JGraphT, as a sibling to the existing Hamiltonian cycle / tour APIs:

https://github.com/seilat/jgrapht/tree/feat/hamiltonian-path

Before opening a PR, I'd like to check whether the scope, package placement, and API shape look right.

JGraphT already has HamiltonianCycleAlgorithm, PalmerHamiltonianCycle, HeldKarpTSP, and the alg.tour package, but those are cycle/tour-oriented. A Hamiltonian path is not closed, may have arbitrary endpoints, and does not require complete-graph or weighted-tour semantics. I therefore treated it as a separate path-existence / path-construction problem rather than extending the tour APIs.

The proposed API is:

public interface HamiltonianPathAlgorithm<V, E> {

    GraphPath<V, E> getPath(Graph<V, E> graph);

}

This mirrors HamiltonianCycleAlgorithm.getTour(Graph), including call-time graph style and null for "no path exists".

The branch currently includes three implementations:

1. BacktrackingHamiltonianPath — practical exact DFS solver with structural prechecks, reachability pruning, and MRV-style candidate ordering. It also has an opt-in bounded method, searchWithStateLimit(graph, maxStates), which returns PATH_FOUND, PROVEN_ABSENT, or ABORTED so callers do not confuse a budget abort with a proven negative.

2. HeldKarpHamiltonianPath — exact O(n² · 2ⁿ) DP solver, capped at n <= 20. This is mostly useful as a deterministic small-graph solver and test oracle.

3. DagHamiltonianPath — polynomial-time special case for directed acyclic graphs using longest-path-in-DAG DP. It rejects cyclic input with IllegalArgumentException.

I also added a small demo, JavaDoc, tests, performance smoke/baseline drivers, and a HISTORY entry.

Current test coverage is 58 test methods, including deterministic cases, self-loop / multigraph behavior, bounded-search behavior, bridge/cut/SCC pruning regressions, brute-force random-oracle cross-validation, Held-Karp tests, and DAG cross-validation.

A bounded JMH benchmark covers seven deterministic graph families at n ∈ {8, 12, 16}. The main takeaway is the intended role split: BacktrackingHamiltonianPath is the practical default, while HeldKarpHamiltonianPath is a deterministic small-graph DP / oracle. The benchmark report is available separately if useful.

The design choices I'd especially like feedback on are:

1. Is a new org.jgrapht.alg.hamiltonian package acceptable, or would you prefer these classes under alg.tour?

2. Is HamiltonianPathAlgorithm in alg.interfaces, mirroring HamiltonianCycleAlgorithm, the right API shape?

3. Should the bounded-execution API land in the first PR, or would you prefer the first PR to include only the unbounded getPath(Graph) API and leave bounded search for a follow-up?

If this direction looks reasonable, I'll open the PR. If you'd prefer changes before that, I'm happy to revise the branch first.

Thanks, Shai

[John Sichi]

Makes sense.  My answers:

1.  I prefer putting everything in alg.tour, despite it then becoming a slight misnomer.  Putting it in a separate hamiltonian package would be confusing given that the existing Hamiltonian cycle classes are in tour.

2.  Yes, that's fine.

3.  You can include everything in the first PR.

--
You received this message because you are subscribed to the Google Groups "jgrapht-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jgrapht-dev...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/jgrapht-dev/bd0c310d-17da-40e0-b7db-605aa7a5347an%40googlegroups.com.