Skip to content

Hamiltonian Cycle API Reference

Data

Data model for Hamiltonian Cycle use case.

HamiltonianCycleData

Bases: UcData

Data for the Hamiltonian Cycle use case.

Finds a cycle that visits every node exactly once and returns to the start.

Attributes:

Name Type Description
name Literal['hamiltonian_cycle']

Identifier for this data type.
adjacency_matrix BinAdjMatrix

Symmetric binary adjacency matrix.
node_names list[int | str]

Node identifiers.

plot(*, ax: Axes | None = None) -> Axes

Plot the Hamiltonian Cycle graph instance.

Parameters:

Name Type Description Default
ax Axes | None

Matplotlib axes to draw on. Creates a new figure if None.

 None

Returns:

Type Description
Axes

The axes with the plot.

to_string() -> str

Format the data as a human-readable string.

Returns:

Type Description
str

String representation of the data.

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str]) -> HamiltonianCycleData staticmethod

Create HamiltonianCycleData from an adjacency matrix.

Parameters:

Name Type Description Default
adjacency_matrix ndarray

Symmetric binary adjacency matrix.

 required
node_names list[int | str]

List of node identifiers.

 required

Returns:

Type Description
HamiltonianCycleData

The Hamiltonian Cycle data instance.

generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> HamiltonianCycleData staticmethod

Generate a random Hamiltonian Cycle instance.

Parameters:

Name Type Description Default
n_nodes int

Number of nodes, by default 5.

 5
edge_prob float

Probability of an edge between any two nodes, by default 0.5.

 0.5
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
HamiltonianCycleData

A randomly generated data instance.

Examples:

>>> data = HamiltonianCycleData.generate_random(n_nodes=10, seed=42)

Formulation

Formulation for Hamiltonian Cycle use case.

HamiltonianCycleFormulation

Bases: UcFormulation[HamiltonianCycleData, HamiltonianCycleSolution]

Constraint-based formulation for Hamiltonian Cycle.

Mathematical Formulation

Index: i, j -- node indices p -- position index

Decision Variables: x[i,p] in {0, 1} -- 1 if node i is at position p in the cycle.

Objective: minimize 0 (feasibility problem)

Constraints: 1. Each node exactly one position: sum_p x[i,p] == 1 for each i 2. Each position exactly one node: sum_i x[i,p] == 1 for each p 3. Consecutive nodes connected: for each position p, for each non-edge (i,j): x[i,p] + x[j,(p+1)%n] <= 1

to_string(data: HamiltonianCycleData) -> str staticmethod

Format the formulation as a string.

Parameters:

Name Type Description Default
data HamiltonianCycleData

The problem data.

 required

Returns:

Type Description
str

Formatted description of the formulation.

formulate(data: HamiltonianCycleData) -> Model staticmethod

Formulate the Hamiltonian Cycle problem as a constraint-based model.

Parameters:

Name Type Description Default
data HamiltonianCycleData

The problem data containing the graph structure.

 required

Returns:

Type Description
Model

A Luna Model ready to be solved.

interpret(solution: Solution, data: HamiltonianCycleData) -> HamiltonianCycleSolution staticmethod

Extract a Hamiltonian Cycle solution from the solver result.

Parameters:

Name Type Description Default
solution Solution

The solver solution.

 required
data HamiltonianCycleData

The original problem data.

 required

Returns:

Type Description
HamiltonianCycleSolution

Structured solution with cycle and validity.

Raises:

Type Description
NoSolutionFoundError

If the solver did not find any solution.

Solution

Solution model for Hamiltonian Cycle use case.

HamiltonianCycleSolution

Bases: UcSolution

Solution for the Hamiltonian Cycle use case.

Attributes:

Name Type Description
name Literal['hamiltonian_cycle']

Identifier.
cycle list[int | str]

Ordered list of nodes in the cycle.
is_valid bool

Whether the cycle visits every node exactly once, returns to start, and all consecutive edges exist.

plot(data: HamiltonianCycleData | None = None, *, ax: Axes | None = None) -> Axes

Plot the Hamiltonian Cycle solution on the problem graph.

Cycle edges are highlighted in green; other edges are grey.

Parameters:

Name Type Description Default
data HamiltonianCycleData | None

Problem data used to reconstruct the graph. Required -- a ValueError is raised when None.

 None
ax Axes | None

Matplotlib axes to draw on. Creates a new figure if None.

 None

Returns:

Type Description
Axes

The axes with the plot.

Raises:

Type Description
ValueError

If data is None.

to_string() -> str

Format the solution as a human-readable string.

Returns:

Type Description
str

String representation of the solution.

Instance

Instance model for Hamiltonian Cycle use case.

HamiltonianCycleInstance

Bases: UcInstance[HamiltonianCycleData, HamiltonianCycleFormulation, HamiltonianCycleSolution]

Instance combining data and formulation for Hamiltonian Cycle.

Collection

Collection of Hamiltonian Cycle instances.

HamiltonianCycleCollection

Bases: UcInstanceCollection[HamiltonianCycleInstance]

Collection of Hamiltonian Cycle instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

from_random(min_nodes: int, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> HamiltonianCycleCollection classmethod

Generate random Hamiltonian Cycle instances.

Parameters:

Name Type Description Default
min_nodes int

Minimum number of nodes.

 required
max_nodes int

Maximum number of nodes.

 required
edge_prob float

Edge probability, by default 0.5.

 0.5
num_instances int

Number of instances per size, by default 1.

 1
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
HamiltonianCycleCollection

Collection containing generated instances.

Examples:

>>> collection = HamiltonianCycleCollection.from_random(
...     min_nodes=3,
...     max_nodes=6,
...     num_instances=2,
...     seed=42,
... )