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 | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
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]) -> MinimalMaximalMatchingData
staticmethod
Create data from an adjacency matrix.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
adjacency_matrix
|
ndarray
|
Symmetric binary adjacency matrix. |
required |
node_names
|
list[int | str]
|
List of node identifiers. |
required |
Returns:
| Type | Description |
|---|---|
MinimalMaximalMatchingData
|
The data instance. |
generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> MinimalMaximalMatchingData
staticmethod
Generate a random 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
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
MinimalMaximalMatchingData
|
A randomly generated data instance. |
Examples:
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MinimalMaximalMatchingData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
Formatted description of the formulation. |
formulate(data: MinimalMaximalMatchingData) -> Model
staticmethod
Formulate the Minimal Maximal Matching problem.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MinimalMaximalMatchingData
|
The problem data containing the graph structure. |
required |
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solver solution. |
required |
data
|
MinimalMaximalMatchingData
|
The original problem data. |
required |
Returns:
| Type | Description |
|---|---|
MinimalMaximalMatchingSolution
|
Structured solution with matching edges and validity. |
Raises:
| Type | Description |
|---|---|
NoSolutionFoundError
|
If the solver did not find any solution. |
Solution
Solution model for Minimal Maximal Matching use case.
MinimalMaximalMatchingSolution
Bases: UcSolution
Solution for the Minimal Maximal Matching use case.
Attributes:
| Name | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MinimalMaximalMatchingData | None
|
Problem data. Required. |
None
|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
Raises:
| Type | Description |
|---|---|
ValueError
|
If data is |
to_string() -> str
Format the solution as a human-readable string.
Returns:
| Type | Description |
|---|---|
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:
| 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 |
|---|---|
MinimalMaximalMatchingCollection
|
Collection containing generated instances. |
Examples: