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

Generate random Minimal Maximal Matching 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 = MinimalMaximalMatchingCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     seed=42,
... )