Package com.jgalgo.alg.hamilton

Interface HamiltonianPathAlgo

All Known Implementing Classes:
HamiltonianPathAlgoAbstract, HamiltonianPathAlgoAbstractBasedCycle, HamiltonianPathRubin
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:

  • Method Details

    • 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