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 Luna Model 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, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> LongestPathCollection classmethod

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