Class CyclesAll

java.lang.Object

topics.backtracking.tsp.HamiltonianAll

topics.backtracking.tsp.CyclesAll

public class CyclesAll
extends HamiltonianAll

Simple Cycles of a Node

This class calculates all simple cycles in a graph originating from a specific source node.

*

Pedagogical Note: TSP vs Cycles

• Traveling Salesman: Requires COMPLETE simple cycles (must visit every node exactly once).
• Node Cycles: Accepts SIMPLE cycles of ANY length (visiting a subset of nodes and returning).

Even though it doesn't require complete paths, the worst-case time complexity remains factorial O(N!) for highly connected graphs due to the combinatorial explosion of subsets.

* @author vicegd

Field Summary

Fields inherited from class HamiltonianAll

cost, length, log, mark, n, nsol, path, source, weights

Constructor Summary

Constructors

Constructor	Description
CyclesAll(int n, int source, int[][] weights)

Method Summary

Modifier and Type	Method	Description
protected void	backtrack(int current)	Core backtracking logic following the Choose-Explore-Unchoose paradigm.

Methods inherited from class HamiltonianAll

backtracking, getNumberSolutions

Methods inherited from class Object

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

Constructor Details

CyclesAll

public CyclesAll(int n,
 int source,
 int[][] weights)

Method Details

backtrack

protected void backtrack(int current)

Description copied from class: HamiltonianAll

Core backtracking logic following the Choose-Explore-Unchoose paradigm.

Overrides:

backtrack in class HamiltonianAll

Parameters:

current - The current node being visited.