Package com.jgalgo.alg.hamilton

Class HamiltonianPathRubin

java.lang.Object

com.jgalgo.alg.hamilton.HamiltonianPathAlgoAbstract

com.jgalgo.alg.hamilton.HamiltonianPathAlgoAbstractBasedCycle

com.jgalgo.alg.hamilton.HamiltonianPathRubin

All Implemented Interfaces:

HamiltonianPathAlgo

public class HamiltonianPathRubin
extends HamiltonianPathAlgoAbstractBasedCycle

Frank Rubin's algorithm for finding Hamiltonian paths in directed and undirected graphs.

The algorithm perform a depth-first search on the graph, maintaining a path of edges that is extended by a single edge in each step. The algorithm maintains a set of edges that are required to be in the path, and a set of edges that are not allowed to be in the path.

Based on 'A Search Procedure for Hamilton Paths and Circuits ' by Frank Rubin, 1974. Some improvements, such as sorting edges extending the current path by their degree, are taken from 'Backtracking (the) Algorithms on the Hamiltonian Cycle Problem' by J. SleegersD. V. D. Berg, 2021.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
HamiltonianPathRubin()	Create a new Hamiltonian path algorithm.

Method Summary

Methods inherited from class com.jgalgo.alg.hamilton.HamiltonianPathAlgoAbstract

hamiltonianCyclesIter, hamiltonianPathsIter, hamiltonianPathsIter

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 Details

HamiltonianPathRubin

public HamiltonianPathRubin()

Create a new Hamiltonian path algorithm.

Please prefer using HamiltonianPathAlgo.newInstance() to get a default implementation for the HamiltonianPathAlgo interface.