Package com.jgalgo.alg.hamilton

Class HamiltonianPathAlgoAbstract

java.lang.Object

com.jgalgo.alg.hamilton.HamiltonianPathAlgoAbstract

All Implemented Interfaces:

HamiltonianPathAlgo

Direct Known Subclasses:

HamiltonianPathAlgoAbstractBasedCycle

public abstract class HamiltonianPathAlgoAbstract
extends Object
implements HamiltonianPathAlgo

Abstract class for computing Hamiltonian cycles/paths in graphs.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
HamiltonianPathAlgoAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> Iterator<Path<V,E>>	hamiltonianCyclesIter(Graph<V,E> g)	Iterate over all Hamiltonian cycles in the given graph.
<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.

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.jgalgo.alg.hamilton.HamiltonianPathAlgo

hamiltonianCycle, hamiltonianPath, hamiltonianPath

Constructor Detail

HamiltonianPathAlgoAbstract

public HamiltonianPathAlgoAbstract()

Default constructor.

Method Detail

hamiltonianPathsIter

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

Description copied from interface: HamiltonianPathAlgo

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.

Specified by:

hamiltonianPathsIter in interface HamiltonianPathAlgo

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

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

Description copied from interface: HamiltonianPathAlgo

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.

Specified by:

hamiltonianPathsIter in interface HamiltonianPathAlgo

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

hamiltonianCyclesIter

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

Description copied from interface: HamiltonianPathAlgo

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.

Specified by:

hamiltonianCyclesIter in interface HamiltonianPathAlgo

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