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 LunaModel 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 | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, max_weight: float = 10.0, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> MinimalSpanningTreeCollection classmethod

Generate random Minimal Spanning Tree 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 ) –

    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.

  • 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 = MinimalSpanningTreeCollection.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: