Skip to content

Minimum Vertex Cover API Reference

Data

Data model for Minimum Vertex Cover use case.

MinimumVertexCoverData

Bases: UcData

Data for the Minimum Vertex Cover use case.

Finds the smallest set of vertices such that every edge has at least one endpoint in the set.

Attributes:

Name Type Description
name Literal['minimum_vertex_cover']

Identifier.
adjacency_matrix BinAdjMatrix

Symmetric binary adjacency matrix.
node_names list[int | str]

Node identifiers.

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

Plot the Minimum Vertex Cover graph instance.

Parameters:

Name Type Description Default
ax Axes | None

Matplotlib axes to draw on. Creates a new figure if None.

 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: NDArray[np.float64], node_names: list[int | str]) -> MinimumVertexCoverData staticmethod

Create MinimumVertexCoverData from an adjacency matrix.

Parameters:

Name Type Description Default
adjacency_matrix ndarray

Symmetric binary adjacency matrix.

 required
node_names list[int | str]

Node identifiers.

 required

Returns:

Type Description
MinimumVertexCoverData

The Minimum Vertex Cover data instance.

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

Generate a random Minimum Vertex Cover instance.

Parameters:

Name Type Description Default
n_nodes int

Number of nodes in the graph, 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
MinimumVertexCoverData

A randomly generated data instance.

Examples:

>>> data = MinimumVertexCoverData.generate_random(n_nodes=5, seed=42)

Formulation

Formulation for Minimum Vertex Cover use case.

MinimumVertexCoverFormulation

Bases: UcFormulation[MinimumVertexCoverData, MinimumVertexCoverSolution]

Constraint-based formulation for Minimum Vertex Cover.

Mathematical Formulation

Decision Variables: x_i in {0, 1} -- node i is in the cover

Objective: minimize sum_i x_i

Constraints: For each edge (i, j): x_i + x_j >= 1

to_string(data: MinimumVertexCoverData) -> str staticmethod

Format the formulation as a string.

Parameters:

Name Type Description Default
data MinimumVertexCoverData

The problem data.

 required

Returns:

Type Description
str

Formatted description of the formulation.

formulate(data: MinimumVertexCoverData) -> Model staticmethod

Formulate the Minimum Vertex Cover problem.

Parameters:

Name Type Description Default
data MinimumVertexCoverData

The problem data containing the graph structure.

 required

Returns:

Type Description
Model

The optimization model.

interpret(solution: Solution, data: MinimumVertexCoverData) -> MinimumVertexCoverSolution staticmethod

Extract a structured solution from the solver result.

Parameters:

Name Type Description Default
solution Solution

The solver solution.

 required
data MinimumVertexCoverData

The problem data.

 required

Returns:

Type Description
MinimumVertexCoverSolution

Structured solution with cover nodes and validity.

Raises:

Type Description
NoSolutionFoundError

If no feasible solution was found.

Solution

Solution model for Minimum Vertex Cover use case.

MinimumVertexCoverSolution

Bases: UcSolution

Solution for Minimum Vertex Cover.

Attributes:

Name Type Description
name Literal['minimum_vertex_cover']

Identifier.
cover_nodes list[int | str]

Nodes in the cover.
cover_size int

Number of nodes in the cover.
is_valid bool

Every edge has at least one endpoint in cover.

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

Plot the Minimum Vertex Cover solution on the problem graph.

Nodes in the cover are highlighted in a different color.

Parameters:

Name Type Description Default
data MinimumVertexCoverData | None

Problem data used to reconstruct the graph. Required -- a ValueError is raised when None.

 None
ax Axes | None

Matplotlib axes to draw on. Creates a new figure if None.

 None

Returns:

Type Description
Axes

The axes with the plot.

Raises:

Type Description
ValueError

If data is None.

to_string() -> str

Format the solution as a human-readable string.

Returns:

Type Description
str

String representation of the solution.

Instance

Instance model for Minimum Vertex Cover use case.

MinimumVertexCoverInstance

Bases: UcInstance[MinimumVertexCoverData, MinimumVertexCoverFormulation, MinimumVertexCoverSolution]

Instance combining data and formulation for Minimum Vertex Cover.

Collection

Collection of Minimum Vertex Cover instances.

MinimumVertexCoverCollection

Bases: UcInstanceCollection[MinimumVertexCoverInstance]

Collection of Minimum Vertex Cover 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, num_instances: int = 1, *, seed: int | None = None) -> MinimumVertexCoverCollection classmethod

Generate random Minimum Vertex Cover instances.

Parameters:

Name Type Description Default
min_nodes int

Minimum number of nodes per instance.

 required
max_nodes int

Maximum number of nodes per instance.

 required
edge_prob float

Probability of an edge between any two nodes, by default 0.5.

 0.5
num_instances int

Number of instances per node count, by default 1.

 1
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
MinimumVertexCoverCollection

Collection containing generated instances.

Examples:

>>> collection = MinimumVertexCoverCollection.from_random(
...     min_nodes=4,
...     max_nodes=6,
...     num_instances=2,
...     seed=42,
... )