Skip to content

Minimal Maximal Matching API Reference

Data

Data model for Minimal Maximal Matching use case.

MinimalMaximalMatchingData

Bases: UcData

Data for the Minimal Maximal Matching use case.

Finds a maximal matching with the minimum number of edges. A matching is maximal if no more edges can be added without violating the matching property (no shared vertices).

Attributes:

  • name (Literal['minimal_maximal_matching']) –

    Identifier for this data type.

  • adjacency_matrix (NumPyArray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

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

Plot the 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]) -> MinimalMaximalMatchingData staticmethod

Create data from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    List of node identifiers.

Returns:

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

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

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

    Random seed for reproducibility, by default None.

Returns:

Examples:

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

Formulation

Formulation for Minimal Maximal Matching use case.

MinimalMaximalMatchingFormulation

Bases: UcFormulation[MinimalMaximalMatchingData, MinimalMaximalMatchingSolution]

Constraint-based formulation for Minimal Maximal Matching.

Mathematical Formulation 
Decision Variables:
    y_e ∈ {0, 1} -- 1 if edge e is in the matching.

Objective:
    minimize Σ_e y_e

Constraints:
    1. Matching: for each node v: Σ_{e incident to v} y_e ≤ 1
    2. Maximal: for each edge (u,v): y_(u,v) + Σ_{e≠(u,v) incident to u} y_e
       + Σ_{e≠(u,v) incident to v} y_e ≥ 1

to_string(data: MinimalMaximalMatchingData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MinimalMaximalMatchingData) -> Model staticmethod

Formulate the Minimal Maximal Matching problem.

Parameters:

Returns:

  • Model –

    A LunaModel ready to be solved.

interpret(solution: Solution, data: MinimalMaximalMatchingData) -> MinimalMaximalMatchingSolution staticmethod

Extract a Minimal Maximal Matching solution from the solver result.

Parameters:

Returns:

Raises:

Solution

Solution model for Minimal Maximal Matching use case.

MinimalMaximalMatchingSolution

Bases: UcSolution

Solution for the Minimal Maximal Matching use case.

Attributes:

  • name (Literal['minimal_maximal_matching']) –

    Identifier.

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

    Edges in the matching.

  • matching_size (int) –

    Number of edges in the matching.

  • is_valid (bool) –

    Whether the matching is valid (no shared vertices) and maximal.

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

Plot the solution on the problem graph.

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

Parameters:

  • data (MinimalMaximalMatchingData | None, default: None ) –

    Problem data. Required.

  • 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 Maximal Matching use case.

MinimalMaximalMatchingInstance

Bases: UcInstance[MinimalMaximalMatchingData, MinimalMaximalMatchingFormulation, MinimalMaximalMatchingSolution]

Instance combining data and formulation for Minimal Maximal Matching.

Collection

Collection of Minimal Maximal Matching instances.

MinimalMaximalMatchingCollection

Bases: UcInstanceCollection[MinimalMaximalMatchingInstance]

Collection of Minimal Maximal Matching instances.

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) -> MinimalMaximalMatchingCollection classmethod

Generate random Minimal Maximal Matching 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 = MinimalMaximalMatchingCollection.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: