Module org.jgrapht.core

Package org.jgrapht.alg.interfaces

Interface HamiltonianPathSearchResult<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public interface HamiltonianPathSearchResult<V,E>

Tri-state result of a HamiltonianPathAlgorithm search.

A Hamiltonian path search can terminate in three distinct ways:

• HamiltonianPathSearchResult.Status.PATH_FOUND — a Hamiltonian path was discovered. The path is available via getPath().
• HamiltonianPathSearchResult.Status.PROVEN_ABSENT — the search ran to completion (or was rejected by a sound precheck) and proved that no Hamiltonian path exists.
• HamiltonianPathSearchResult.Status.ABORTED — the search hit a configured limit before completing. Whether a Hamiltonian path exists in the input graph is unknown.

Callers must consult getStatus() before interpreting an empty getPath(): an empty path may mean either HamiltonianPathSearchResult.Status.PROVEN_ABSENT or HamiltonianPathSearchResult.Status.ABORTED, and the two have very different semantic implications.

Instances are obtained either from a HamiltonianPathAlgorithm implementation or via the found(GraphPath, long), provenAbsent(long), and aborted(long) static factory methods on this interface, which return a default immutable implementation.

Author:

seilat

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static enum	HamiltonianPathSearchResult.Status	Termination state of a Hamiltonian path search.

Method Summary

Modifier and Type	Method	Description
static <V, E> HamiltonianPathSearchResult<V,E>	aborted(long statesExpanded)	Creates a result for a search that was stopped by a state limit before completing.
static <V, E> HamiltonianPathSearchResult<V,E>	found(GraphPath<V,E> path, long statesExpanded)	Creates a result for a successful search.
Optional<GraphPath<V,E>>	getPath()	Returns the Hamiltonian path if the search found one.
long	getStatesExpanded()	Returns the number of DFS / DP states the search explored.
HamiltonianPathSearchResult.Status	getStatus()	Returns the termination status of this search.
static <V, E> HamiltonianPathSearchResult<V,E>	provenAbsent(long statesExpanded)	Creates a result for an exhaustive search that proved no Hamiltonian path exists.

Method Details

getStatus

HamiltonianPathSearchResult.Status getStatus()

Returns the termination status of this search.

Returns:

the search status

getPath

Optional<GraphPath<V,E>> getPath()

Returns the Hamiltonian path if the search found one.

Returns:

the discovered path, or Optional.empty() for HamiltonianPathSearchResult.Status.PROVEN_ABSENT and HamiltonianPathSearchResult.Status.ABORTED

getStatesExpanded

long getStatesExpanded()

Returns the number of DFS / DP states the search explored. The exact counting semantics are implementation-defined; consult the JavaDoc of the producing algorithm for details.

Returns:

states explored during this search

found

static <V,
E> HamiltonianPathSearchResult<V,E> found(GraphPath<V,E> path,
 long statesExpanded)

Creates a result for a successful search.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

path - the Hamiltonian path that was found (must not be null)

statesExpanded - the number of states the search explored

Returns:

a HamiltonianPathSearchResult.Status.PATH_FOUND result holding the given path

provenAbsent

static <V,
E> HamiltonianPathSearchResult<V,E> provenAbsent(long statesExpanded)

Creates a result for an exhaustive search that proved no Hamiltonian path exists.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

statesExpanded - the number of states the search explored before concluding

Returns:

a HamiltonianPathSearchResult.Status.PROVEN_ABSENT result with no path

aborted

static <V,
E> HamiltonianPathSearchResult<V,E> aborted(long statesExpanded)

Creates a result for a search that was stopped by a state limit before completing.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

statesExpanded - the number of states the search explored before aborting

Returns:

an HamiltonianPathSearchResult.Status.ABORTED result with no path