Skip to content

Minimal Spanning Tree API Reference

Data

Data model for Minimal Spanning Tree use case.

MinimalSpanningTreeData

Bases: UcData

Data for the Minimal Spanning Tree use case.

Finds the minimum-weight spanning tree in a weighted graph.

Attributes:

  • name (Literal['minimal_spanning_tree']) –

    Identifier for this data type.

  • adjacency_matrix (NumPyArray) –

    Symmetric weighted adjacency matrix. Zero means no edge.

  • node_names (list[int | str]) –

    Node identifiers.

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

Plot the Minimal Spanning Tree 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]) -> MinimalSpanningTreeData staticmethod

Create MinimalSpanningTreeData from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric weighted adjacency matrix. Zero means no edge.

  • node_names (list[int | str]) –

    List of node identifiers.

Returns:

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

Generate a random Minimal Spanning Tree instance.

The generated graph is guaranteed to be connected. A random spanning tree is first created, and then additional edges are added with probability edge_prob.

Parameters:

  • n_nodes (int, default: 5 ) –

    Number of nodes, by default 5.

  • edge_prob (float, default: 0.5 ) –

    Probability of additional edges beyond the spanning tree, by default 0.5.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

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

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> data = MinimalSpanningTreeData.generate_random(n_nodes=10, seed=42)

Formulation

Formulation for Minimal Spanning Tree use case.

MinimalSpanningTreeFormulation

Bases: UcFormulation[MinimalSpanningTreeData, MinimalSpanningTreeSolution]

Constraint-based flow formulation for Minimal Spanning Tree.

Mathematical Formulation

Indices and Sets: V = {0, 1, ..., n-1} -- set of nodes (node 0 is the root) E = {(i,j) : i < j, adjacency_matrix[i,j] != 0} -- set of undirected edges (upper triangle only) n = |V| -- number of nodes

    Decision Variables:
y_{i,j} in {0, 1}
    for each (i,j) in E.
    y_{i,j} = 1 if undirected edge {i,j} is selected for the spanning tree,
    y_{i,j} = 0 otherwise.

f_{i,j} in {0, 1, ..., n-1}
    for each (i,j) in E and for each (j,i) in E (i.e., both directions).
    f_{i,j} = amount of flow routed from node i to node j along edge {i,j}.
    The flow is directed even though the underlying graph is undirected;
    at most one of f_{i,j} and f_{j,i} will be nonzero in any feasible solution.

Objective: minimize sum_{(i,j) in E} adjacency_matrix[i,j] * y_{i,j}

Minimises the total weight of selected edges.

Constraints: 1. Exactly n-1 edges selected (1 constraint): sum_{(i,j) in E} y_{i,j} == n - 1 A spanning tree on n nodes has exactly n-1 edges.

2. Flow conservation at each non-root node v in V \\ {0}
   (n-1 constraints, one per non-root node):
       sum_{(u,v) in E}  f_{u,v}  -  sum_{(v,w) in E}  f_{v,w}  ==  1
   Each non-root node must receive exactly 1 unit of net flow.
   Together with constraint 4 this guarantees that every node is
   reachable from the root, i.e. the selected edges form a connected graph.

3. Flow capacity: flow only on selected edges
   (|E| constraints, one per undirected edge):
       f_{i,j} + f_{j,i}  <=  (n-1) * y_{i,j}   for all (i,j) in E
   If edge {i,j} is not selected (y_{i,j} = 0) no flow can cross it
   in either direction.  If it is selected (y_{i,j} = 1) the combined
   flow in both directions is bounded by n-1 (the maximum possible
   flow any single edge could carry in a tree on n nodes).

4. Root sends exactly n-1 units of flow (1 constraint):
       sum_{j : (0,j) in E}  f_{0,j}  -  sum_{j : (j,0) in E}  f_{j,0}  ==  n - 1
   The root (node 0) is the sole source of flow; it emits one unit
   for each of the n-1 non-root nodes.

5. Flow variable bounds (4*|E| constraints):
       0  <=  f_{i,j}  <=  n-1   for all directed pairs (i,j)
   Explicit lower and upper bounds on the integer flow variables.

Connectivity argument: Constraints 2 and 4 together ensure that the root can reach every other node via the selected edges: if any node v were unreachable from the root, the net inflow to v would be 0, violating constraint 2. Combined with constraint 1 (exactly n-1 edges), connectivity implies the selected edges form a tree (a connected acyclic graph on n nodes with n-1 edges is always a tree).

to_string(data: MinimalSpanningTreeData) -> str staticmethod

Format the formulation as a human-readable string.

Summarises the sizes of the index sets, the decision variables, the objective, and the constraint groups for a given problem instance.

Parameters:

  • data (MinimalSpanningTreeData) –

    The problem data. Relevant fields: - data.node_names : list of length n with a name for each node. - data.adjacency_matrix: n×n weight matrix; entry [i,j] is the edge weight for {i,j}, or 0 if the edge does not exist.

Returns:

  • str –

    Multi-line string describing the formulation dimensions and constraint groups for the given instance.

formulate(data: MinimalSpanningTreeData) -> Model staticmethod

Formulate the MST problem as a mixed-integer programming (MIP) model.

Uses a flow-based formulation to enforce connectivity without exponential subtour elimination constraints. The key insight is that routing one unit of flow from a designated root to every other node is equivalent to requiring that those nodes are reachable from the root — i.e. the selected edges span the graph.

Variable naming convention

Binary edge variables: y_{i}_{j} where i < j and (i,j) in E. The indices i and j are the 0-based positions of the two endpoints in data.node_names.

Integer flow variables (one per directed arc): f_{i}_{j} for the arc from node i to node j. f_{j}_{i} for the arc from node j to node i. Again, i < j to match the edge set E; both directions are created for each undirected edge.

Constraint naming convention

n_minus_1_edges -- constraint 1 (exactly n-1 edges). flow_conservation_{v} -- constraint 2 for node v (v != 0). flow_capacity_{i}_{j} -- constraint 3 for edge (i,j). root_flow -- constraint 4 (root net outflow = n-1). flow_lb_{i}_{j} -- lower bound f_{i,j} >= 0. flow_ub_{i}_{j} -- upper bound f_{i,j} <= n-1. (similarly flow_lb_{j}_{i} / flow_ub_{j}_{i} for the reverse arc)

Parameters:

  • data (MinimalSpanningTreeData) –

    The problem data. Relevant fields: - data.node_names : list of n node labels (strings or ints). The index of a label in this list is the node index used throughout the model. Node at index 0 is the root. - data.adjacency_matrix: n×n numpy array. Entry [i, j] is the weight of edge {i, j}; 0 means the edge does not exist. The matrix is assumed to be symmetric; only the upper triangle (i < j) is read.

Returns:

  • Model –

    A Luna Model ready to be solved. The model name encodes a hash of the input data so that repeated calls with identical data reuse cached results where possible.

interpret(solution: Solution, data: MinimalSpanningTreeData) -> MinimalSpanningTreeSolution staticmethod

Extract a Minimal Spanning Tree solution from the solver result.

Reads the binary edge-selection variables y_{i}_{j} from the best sample returned by the solver and reconstructs the list of selected tree edges in terms of the original node names (rather than their 0-based indices).

Variable lookup: The solver stores each variable under its string name. For a binary edge variable between nodes at indices i and j (i < j) the name is "y_{i}_{j}". A value above BINARY_DIVIDER (0.5) is rounded to 1 (edge selected); at or below it is rounded to 0 (not selected).

Index-to-name mapping: data.node_names[i] gives the original label for node index i. Selected edges are therefore reported as (data.node_names[i], data.node_names[j]).

Parameters:

  • solution (Solution) –

    The solver solution object. solution.best() returns a list of samples; sample.sample is a dict mapping variable name (str) to its value in that sample.

  • data (MinimalSpanningTreeData) –

    The original problem data. Used to: - determine n = len(data.node_names), - reconstruct the edge list E (same upper-triangle enumeration used in formulate), - look up edge weights via data.adjacency_matrix[i, j], - map node indices back to node names via data.node_names.

Returns:

  • MinimalSpanningTreeSolution –

    Structured solution with: - tree_edges : list of (name_i, name_j) pairs for selected edges. - total_weight : sum of weights of selected edges (float). - is_valid : True iff the selected edges form a valid spanning tree.

Raises:

  • NoSolutionFoundError –

    If the solver did not find any feasible solution (solution.best() returns None).

Solution

Solution model for Minimal Spanning Tree use case.

MinimalSpanningTreeSolution

Bases: UcSolution

Solution for the Minimal Spanning Tree use case.

Attributes:

  • name (Literal['minimal_spanning_tree']) –

    Identifier.

  • tree_edges (list[tuple[int | str, int | str]]) –

    Edges in the spanning tree.

  • total_weight (float) –

    Total weight of the spanning tree.

  • is_valid (bool) –

    Whether the solution is a valid spanning tree (n-1 edges, connected, all edges exist in the graph).

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

Plot the Minimal Spanning Tree solution on the problem graph.

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

Parameters:

  • data (MinimalSpanningTreeData | 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 Minimal Spanning Tree use case.

MinimalSpanningTreeInstance

Bases: UcInstance[MinimalSpanningTreeData, MinimalSpanningTreeFormulation, MinimalSpanningTreeSolution]

Instance combining data and formulation for Minimal Spanning Tree.

Collection

Collection of Minimal Spanning Tree instances.

MinimalSpanningTreeCollection

Bases: UcInstanceCollection[MinimalSpanningTreeInstance]

Collection of Minimal Spanning Tree 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, max_weight: float = 10.0, num_instances: int = 1, *, seed: int | None = None) -> MinimalSpanningTreeCollection classmethod

Generate random Minimal Spanning Tree instances.

Parameters:

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

  • edge_prob (float, default: 0.5 ) –

    Additional edge probability beyond the spanning tree, by default 0.5.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

  • 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 = MinimalSpanningTreeCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     seed=42,
... )