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 Details

    • HamiltonianPathAlgoAbstract

      public HamiltonianPathAlgoAbstract()
      Default constructor.

  • Method Details

    • 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