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 (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:

  • ax (Axes | None, default: None ) –

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

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Format the data as a human-readable string.

Returns:

  • 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:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    List of node identifiers.

Returns:

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

Generate a random Hamiltonian Cycle instance.

Parameters:

  • n_nodes (int, default: 5 ) –

    Number of nodes, by default 5.

  • edge_prob (float, default: 0.5 ) –

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

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

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:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: HamiltonianCycleData) -> Model staticmethod

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

Parameters:

Returns:

  • 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:

  • solution (Solution) –

    The solver solution.

  • data (HamiltonianCycleData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for Hamiltonian Cycle use case.

HamiltonianCycleSolution

Bases: UcSolution

Solution for the Hamiltonian Cycle use case.

Attributes:

  • 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:

  • data (HamiltonianCycleData | None, default: None ) –

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

  • ax (Axes | None, default: None ) –

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

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Format the solution as a human-readable string.

Returns:

  • 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:

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

  • edge_prob (float, default: 0.5 ) –

    Edge probability, by default 0.5.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

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