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 LunaModel 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 | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> HamiltonianCycleCollection classmethod

Generate random Hamiltonian Cycle instances.

Parameters:

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

    Minimum number of nodes.

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

    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.

  • sizes (Sequence[int] | None, default: None ) –

    Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_nodes/max_nodes, by default None.

Returns:

Examples:

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

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • list[bool] –

    Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises: