Package com.jgalgo.alg

Interface HamiltonianPathAlgo

public interface HamiltonianPathAlgo

Hamiltonian path/cycle algorithm.

Given a graph \(G = (V, E)\), a path is a sequence of edges \(e_1, e_2, \ldots, e_k\) such that for each pair of consecutive edges \(e_i, e_{i+1}\), the target of \(e_i\) is the source of \(e_{i+1}\). A cycle is a path where the source of the first edge is the target of the last edge. We says that a path/cycle visits a vertex \(v\) if \(v\) is the source or target of some edge in the path/cycle. A path/cycle is Hamiltonian if it visits each vertex exactly once.

There are few problems related to Hamiltonian paths/cycles:

• Given a graph, find one/all Hamiltonian path/s.
• Given a graph, find one/all Hamiltonian path/s that start and end at two given vertices.
• Given a graph, find one/all Hamiltonian cycle/s.

This interface provides algorithms for solving all the above problems. All of the above problems are NP-complete, so the algorithms provided here are exponential in the worst case, and expect them to be useful on small graphs.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

See Also:

Wikipedia

Method Summary

Modifier and Type	Method	Description
default <V,E> Optional<Path<V,E>>	hamiltonianCycle(Graph<V,E> g)	Find a Hamiltonian cycle in the given graph.
<V,E> Iterator<Path<V,E>>	hamiltonianCyclesIter(Graph<V,E> g)	Iterate over all Hamiltonian cycles in the given graph.
default <V,E> Optional<Path<V,E>>	hamiltonianPath(Graph<V,E> g)	Find a Hamiltonian path in the given graph.
default <V,E> Optional<Path<V,E>>	hamiltonianPath(Graph<V,E> g, V source, V target)	Find a Hamiltonian path in the given graph that start and end at two given vertices.
<V,E> Iterator<Path<V,E>>	hamiltonianPathsIter(Graph<V,E> g)	Iterate over all Hamiltonian paths in the given graph.
<V,E> Iterator<Path<V,E>>	hamiltonianPathsIter(Graph<V,E> g, V source, V target)	Iterate over all Hamiltonian paths in the given graph that start and end at two given vertices.
static <V,E> boolean	isHamiltonianPath(Graph<V,E> g, List<E> path)	Check whether the given path is a Hamiltonian path (or cycle) in the given graph.
static HamiltonianPathAlgo	newInstance()	Create a new Hamiltonian path algorithm.

Method Detail

hamiltonianPath

default <V,E> Optional<Path<V,E>> hamiltonianPath(Graph<V,E> g)

Find a Hamiltonian path in the given graph.

An Hamiltonian path is a path that visits each vertex of the graph exactly once. This method returns an Hamiltonian path if one exists, or Optional.empty() otherwise. The returned path will start and end at two arbitrary vertices.

If the graph has no vertices, this methods return Optional.empty(). If the graph has only one vertex, this method returns an empty path (which is actually a cycle).

If g is IntGraph, the returned path will an instance of IPath.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

Returns:

an Hamiltonian path if one exists, or Optional.empty() otherwise

hamiltonianPath

default <V,E> Optional<Path<V,E>> hamiltonianPath(Graph<V,E> g,
                                                              V source,
                                                              V target)

Find a Hamiltonian path in the given graph that start and end at two given vertices.

An Hamiltonian path is a path that visits each vertex of the graph exactly once. This method returns an Hamiltonian path that start at source and end at target if one exists, or Optional.empty() otherwise.

If the source and target are the same vertex, the return path will actually be an Hamiltonian cycle.

If g is IntGraph, the returned path will an instance of IPath.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

source - the source vertex

target - the target vertex

Returns:

an Hamiltonian path that start at source and end at target if one exists, or Optional.empty() otherwise

Throws:

NoSuchVertexException - if source or target are not vertices in g

hamiltonianPathsIter

<V,E> Iterator<Path<V,E>> hamiltonianPathsIter(Graph<V,E> g)

Iterate over all Hamiltonian paths in the given graph.

An Hamiltonian path is a path that visits each vertex of the graph exactly once. This method returns an iterator that iterate over all Hamiltonian paths in the graph. Each returned path will start and end at two arbitrary vertices.

If the graph has no vertices, this methods returns an empty iterator. If the graph has only one vertex, this method returns an iterator that iterate over a single empty path (which is actually a cycle).

If g is IntGraph, the returned iterator will iterate over IPath objects.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

Returns:

an iterator that iterate over all Hamiltonian paths in the graph

hamiltonianPathsIter

<V,E> Iterator<Path<V,E>> hamiltonianPathsIter(Graph<V,E> g,
                                                           V source,
                                                           V target)

Iterate over all Hamiltonian paths in the given graph that start and end at two given vertices.

An Hamiltonian path is a path that visits each vertex of the graph exactly once. This method returns an iterator that iterate over all Hamiltonian paths in the graph that start at source and end at target.

If the source and target are the same vertex, the returned iterator will iterate over all Hamiltonian cycles in the graph.

If g is IntGraph, the returned iterator will iterate over IPath objects.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

source - the source vertex

target - the target vertex

Returns:

an iterator that iterate over all Hamiltonian paths in the graph that start at source and end at target

Throws:

NoSuchVertexException - if source or target are not vertices in g

hamiltonianCycle

default <V,E> Optional<Path<V,E>> hamiltonianCycle(Graph<V,E> g)

Find a Hamiltonian cycle in the given graph.

An Hamiltonian cycle is a cycle that visits each vertex of the graph exactly once. This method returns an Hamiltonian cycle if one exists, or Optional.empty() otherwise.

If the graph has no vertices, this methods return Optional.empty(). If the graph has only one vertex, this method returns an empty cycle.

If g is IntGraph, the returned cycle will an instance of IPath.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

Returns:

an Hamiltonian cycle if one exists, or Optional.empty() otherwise

hamiltonianCyclesIter

<V,E> Iterator<Path<V,E>> hamiltonianCyclesIter(Graph<V,E> g)

Iterate over all Hamiltonian cycles in the given graph.

An Hamiltonian cycle is a cycle that visits each vertex of the graph exactly once. This method returns an iterator that iterate over all Hamiltonian cycles in the graph.

If the graph has no vertices, this methods returns an empty iterator. If the graph has only one vertex, this method returns an iterator that iterate over a single empty cycle.

If g is IntGraph, the returned iterator will iterate over IPath objects.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

Returns:

an iterator that iterate over all Hamiltonian cycles in the graph

isHamiltonianPath

static <V,E> boolean isHamiltonianPath(Graph<V,E> g,
                                             List<E> path)

Check whether the given path is a Hamiltonian path (or cycle) in the given graph.

Given a graph \(G = (V, E)\), a path is a sequence of edges \(e_1, e_2, \ldots, e_k\) such that for each pair of consecutive edges \(e_i, e_{i+1}\), the target of \(e_i\) is the source of \(e_{i+1}\). A path is Hamiltonian if it visits each vertex exactly once. An hamiltonian cycle is a path with \(|V|\) edges that visit every vertex exactly once, but return to the first vertex with the last edge to form a cycle.

This methods accept a graph and list of edges, and check whether the list of edges is a Hamiltonian path in the graph. It first validate that the list of edges is a valid path in the graph, and then check whether the path is Hamiltonian.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

path - a list of edges in the graph

Returns:

true if the list of edges is a Hamiltonian path (or cycle) in the graph, false if the list of edges is not a valid path in the graph or if the path is not Hamiltonian

newInstance

static HamiltonianPathAlgo newInstance()

Create a new Hamiltonian path algorithm.

This is the recommended way to instantiate a new HamiltonianPathAlgo object.

Returns:

a default implementation of HamiltonianPathAlgo