[Proposal] Endpoint-constrained Hamiltonian path search (follow-up to #1346)

[Shai Eilat]

Hi all,

Since the exact Hamiltonian path solvers from #1346 landed, I'd like to do a small, focused follow-up before the larger ones: endpoint-constrained search on BacktrackingHamiltonianPath.

Branch (one commit, off current master):

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

The gap

BacktrackingHamiltonianPath.getPath(graph) finds some Hamiltonian path, with arbitrary endpoints. A common need is to fix one or both ends: "a Hamiltonian path that starts at s", "...that ends at t", or "...from s to t" (the directed s–t case in particular). Today callers can only post-filter, which is wasteful since the constraint can prune the search directly.

The proposal

Four methods on BacktrackingHamiltonianPath, no new interface, no new package:

HamiltonianPathSearchResult<V, E> getPathFrom(Graph<V, E> graph, V source);

HamiltonianPathSearchResult<V, E> getPathTo(Graph<V, E> graph, V target);

HamiltonianPathSearchResult<V, E> getPathBetween(Graph<V, E> graph, V source, V target);

// bounded counterpart of the existing searchWithStateLimit(graph, maxStates)

HamiltonianPathSearchResult<V, E> searchWithStateLimitBetween(

Graph<V, E> graph, V source, V target, long maxStates);

They reuse the same exact search already in the class. A required source restricts the DFS to start there; a required target is withheld from every search position except the last. The reachability and MRV pruning are unchanged, so the search stays exact and none of the constraints can cause a false negative. The existing tri-state HamiltonianPathSearchResult (PATH_FOUND / PROVEN_ABSENT / ABORTED) is preserved, so searchWithStateLimitBetween distinguishes a budget abort from a proven negative exactly as searchWithStateLimit does.

Edge cases are handled consistently with the merged code: a single-vertex graph matches only if the endpoint constraints name that vertex; source == target on more than one vertex is PROVEN_ABSENT (a Hamiltonian path has two distinct ends); endpoints not in the graph throw IllegalArgumentException.

One small performance cleanup rides along: the reachability BFS now reuses per-search scratch buffers instead of allocating a boolean[] and an int[] at every DFS node.

Tests

• BacktrackingHamiltonianPathEndpointTest — deterministic cases on path / cycle / complete / directed-chain graphs (constrained start, end, pair; source == target; not-in-graph; null), plus a target-withholding regression: a graph where the target is adjacent to the start but the only Hamiltonian path places the target last, so the solver must withhold it rather than grabbing it early and reporting a false absence.
• BacktrackingHamiltonianPathEndpointRandomTest — an endpoint-aware brute-force permutation oracle over random directed and undirected graphs (n ≤ 6); every from / to / between constraint is cross-checked for both existence and exact endpoints.
• BacktrackingHamiltonianPathBoundedTest — extended with bounded-between cases (found, proven-absent on infeasible endpoints, ABORTED on a tiny budget, argument validation).

The full FastTestSuite is green and checkstyle:check -P checkstyle is clean. (I've left the HISTORY entry out — happy for a committer to add it on merge.)

Open questions

1. Method shape. I went with getPathFrom / getPathTo / getPathBetween for readability and to avoid null-as-wildcard. An alternative that parallels ShortestPathAlgorithm.getPath(source, sink) would be an overload getPath(graph, source, target). Preference?

2. Bounded variants. I added only searchWithStateLimitBetween, since the fixed-pair case is where a budget matters most. I can add ...From / ...To for symmetry, or leave them out to keep the surface minimal.

3. Scope. This intentionally excludes the weighted (path-TSP), longest-simple-path, enumeration, and cost-ranked "nearest endpoint" work I have on a separate branch — I'll send a separate roadmap heads-up for those so this one stays a clean, reviewable follow-up. Does keeping them split match how you'd like to take this?

If the direction looks right I'll open the PR.

Thanks, Shai

[John Sichi]

Answers below.

1) The method names are good as proposed.

2) Makes sense to keep it minimal.

3) This split is good.

--
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/e438d3d8-4e62-4ae4-970e-2dcc8408aabdn%40googlegroups.com.