Module org.jgrapht.core

Package org.jgrapht.alg.tour

Class DagHamiltonianPath<V,E>

java.lang.Object

org.jgrapht.alg.tour.HamiltonianPathAlgorithmBase<V,E>

org.jgrapht.alg.tour.DagHamiltonianPath<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

HamiltonianPathAlgorithm<V,E>

public class DagHamiltonianPath<V,E>
extends HamiltonianPathAlgorithmBase<V,E>

Polynomial-time Hamiltonian path algorithm for directed acyclic graphs.

Hamiltonian path existence in a directed acyclic graph (DAG) reduces to deciding whether the longest directed path covers all vertices. This implementation computes a topological order, runs the standard longest-path-in-DAG dynamic program over that order, and reconstructs a Hamiltonian path when the longest path's length equals the vertex count.

The longest-path-in-DAG DP is a textbook reduction; see for example CLRS, "Introduction to Algorithms" (4th ed.), section on single-source shortest paths in DAGs, which dualises to longest-path by negating edge weights, and the MIT 6.s078 lecture notes (lecture 17 on dynamic programming, MIT 6.s078, Spring 2022) for the Hamiltonian-path framing.

Total complexity is O(|V| + |E|) time and O(|V|) space.

This class only accepts directed acyclic graphs. Passing a directed graph that contains a cycle causes an IllegalArgumentException wrapping the NotDirectedAcyclicGraphException thrown by TopologicalOrderIterator when the topological pass discovers the cycle; passing an undirected graph or null also fails with an IllegalArgumentException (or NullPointerException respectively). To solve the Hamiltonian path problem on cyclic directed graphs, use BacktrackingHamiltonianPath or HeldKarpHamiltonianPath.

In multigraphs, parallel edges between the same vertex pair do not change the result. The returned path uses an arbitrary representative edge selected via Graph.getEdge(V, V) and is not weight-optimised across parallel edges.

Author:

seilat

Constructor Summary

Constructors

Constructor	Description
DagHamiltonianPath()	Constructs a new instance.

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.

Methods inherited from class org.jgrapht.alg.tour.HamiltonianPathAlgorithmBase

buildAdjacency, requireNotEmpty, singletonPath, vertexListToPath

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

DagHamiltonianPath

public DagHamiltonianPath()

Constructs a new instance.

Method Details

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:

• 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