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

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

Create LongestPathData from an adjacency matrix.

Parameters:

Name Type Description Default
adjacency_matrix ndarray

Weighted adjacency matrix.

 required
node_names list[int | str]

List of node identifiers.

 required
start_node int | str

Node where the path begins.

 required
terminal_node int | str

Node where the path ends.

 required
path_length int

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

 required

Returns:

Type Description
LongestPathData

The Longest Path data instance.

Raises:

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

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
path_length int

Number of nodes in the path, by default 3.

 3
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
LongestPathData

A randomly generated data instance.

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:

Name Type Description Default
data LongestPathData

The problem data.

 required

Returns:

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

Name Type Description Default
data LongestPathData

The problem data containing the graph structure.

 required

Returns:

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

Name Type Description Default
solution Solution

The solver solution.

 required
data LongestPathData

The original problem data.

 required

Returns:

Type Description
LongestPathSolution

Structured solution with path, weight, and validity.

Raises:

Type Description
NoSolutionFoundError

If the solver did not find any solution.

Solution

Solution model for Longest Path use case.

LongestPathSolution

Bases: UcSolution

Solution for the Longest Path use case.

Attributes:

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

Name Type Description Default
data LongestPathData | 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 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:

Name Type Description Default
min_nodes int

Minimum number of nodes.

 required
max_nodes int

Maximum number of nodes.

 required
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

Returns:

Type Description
LongestPathCollection

Collection containing generated instances.

Examples:

>>> collection = LongestPathCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     seed=42,
... )