Skip to content

Longest Path API Reference

Data

Data model for Longest Path use case.

LongestPathData

Bases: UcData

Data for the Longest Path use case.

Finds the longest weighted path between two nodes in a graph, visiting exactly path_length nodes.

Attributes:

  • name (Literal['longest_path']) –

    Identifier for this data type.

  • adjacency_matrix (SymMatrix) –

    Weighted adjacency matrix. Entry (i, j) is the edge weight between nodes i and j, or 0 if there is no edge.

  • node_names (list[int | str]) –

    Node identifiers.

  • start_node (int | str) –

    Node where the path must begin.

  • terminal_node (int | str) –

    Node where the path must end.

  • path_length (int) –

    Number of nodes in the path (including start and end).

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

Plot the Longest Path 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], start_node: int | str, terminal_node: int | str, path_length: int) -> LongestPathData staticmethod

Create LongestPathData from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Weighted adjacency matrix.

  • node_names (list[int | str]) –

    List of node identifiers.

  • start_node (int | str) –

    Node where the path begins.

  • terminal_node (int | str) –

    Node where the path ends.

  • path_length (int) –

    Number of nodes in the path (including start and end).

Returns:

Raises:

  • ValueError –

    If the matrix is not square, not symmetric, has a non-zero diagonal, or if node_names length doesn't match the matrix, node_names contains duplicates, or start/terminal nodes are not in node_names.

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

Generate a random Longest Path 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.

  • path_length (int, default: 3 ) –

    Number of nodes in the path, by default 3.

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

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> data = LongestPathData.generate_random(n_nodes=6, seed=42)

Formulation

Formulation for Longest Path use case.

LongestPathFormulation

Bases: UcFormulation[LongestPathData, LongestPathSolution]

Constraint-based formulation for Longest Path.

Mathematical Formulation 
Decision Variables:
    x[i, p] in {0, 1} -- 1 if node i is at position p in the path.
    Note: x[start, 0] and x[terminal, L-1] are treated as constants (= 1)
    and are not added as model variables.

Objective:
    maximize sum over p in 0..L-2 of sum over edges (i,j) of
    w_ij * x[i,p] * x[j,p+1]

Constraints:
    1. Each position has exactly one node: sum_i x[i,p] == 1 for all p.
    2. Each node is used at most once: sum_p x[i,p] <= 1 for all i.
    3. Consecutive nodes must be connected:
       for non-edges (i,j): x[i,p] + x[j,p+1] <= 1 for all p.

Note: The start and terminal constraints are eliminated by substitution:
x[start, 0] = 1 and x[terminal, L-1] = 1 are treated as constants,
reducing the number of variables by 2 and removing 2 equality constraints.

to_string(data: LongestPathData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: LongestPathData) -> Model staticmethod

Formulate the Longest Path problem as a constraint-based model.

Start and terminal nodes are treated as constants (x[start, 0] = 1 and x[terminal, L-1] = 1) and are not added as model variables. This reduces the number of variables by 2 and eliminates 2 equality constraints.

Variables

x[i, p] : binary 1 if node i occupies position p in the path, 0 otherwise. i : int Node index in range [0, n-1], where n is the total number of nodes. p : int Position index in range [0, L-1], where L is the fixed path length. j : int Secondary node index, used when iterating over potential edges (i -> j).

Parameters:

  • data (LongestPathData) –

    The problem data containing the graph structure.

Returns:

  • Model –

    A LunaModel ready to be solved.

interpret(solution: Solution, data: LongestPathData) -> LongestPathSolution staticmethod

Extract a Longest Path solution from the solver result.

Since x[start, 0] and x[terminal, L-1] are not model variables, their values are inferred directly from the problem data rather than read from the solution sample.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (LongestPathData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for Longest Path use case.

LongestPathSolution

Bases: UcSolution

Solution for the Longest Path use case.

Attributes:

  • name (Literal['longest_path']) –

    Identifier.

  • path (list[int | str]) –

    Ordered nodes in the longest path.

  • total_weight (float) –

    Sum of edge weights along the path.

  • is_valid (bool) –

    Whether the path is valid (connected, respects start/end, correct length).

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

Plot the Longest Path solution on the problem graph.

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

Parameters:

  • data (LongestPathData | 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 Longest Path use case.

LongestPathInstance

Bases: UcInstance[LongestPathData, LongestPathFormulation, LongestPathSolution]

Instance combining data and formulation for Longest Path.

Collection

Collection of Longest Path instances.

LongestPathCollection

Bases: UcInstanceCollection[LongestPathInstance]

Collection of Longest Path 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) -> LongestPathCollection classmethod

Generate random Longest Path 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 = LongestPathCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     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: