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

Name	Type	Description	Default
`min_nodes`	`int \| None`	Minimum number of nodes.	`None`
`max_nodes`	`int \| None`	Maximum number of nodes.	`None`
`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`
`sizes`	`Sequence[int] \| None`	Explicit sizes to generate, e.g. `[10, 50, 100]`, instead of a range. Mutually exclusive with `min_nodes`/`max_nodes`, 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,
... )

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

Name	Type	Description	Default
`max_runtime`	`float`	SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.	`3600`
`quiet`	`bool`	Suppress the SCIP solver output.	`True`

Returns:

Type	Description
`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:

Type	Description
`ValueError`	If `max_runtime` is not positive.

Hamiltonian Cycle API Reference

Data

HamiltonianCycleData

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

to_string() -> str

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

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

Formulation

HamiltonianCycleFormulation

to_string(data: HamiltonianCycleData) -> str staticmethod

formulate(data: HamiltonianCycleData) -> Model staticmethod

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

Solution

HamiltonianCycleSolution

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

to_string() -> str

Instance

HamiltonianCycleInstance

Collection

HamiltonianCycleCollection

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

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

`HamiltonianCycleData`

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

`to_string() -> str`

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

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

`HamiltonianCycleFormulation`

`to_string(data: HamiltonianCycleData) -> str` `staticmethod`

`formulate(data: HamiltonianCycleData) -> Model` `staticmethod`

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

`HamiltonianCycleSolution`

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

`to_string() -> str`

`HamiltonianCycleInstance`

`HamiltonianCycleCollection`

`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`

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