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 (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:

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

Create MinimumVertexCoverData from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

Returns:

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:

  • n_nodes (int, default: 5 ) –

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

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MinimumVertexCoverData) -> Model staticmethod

Formulate the Minimum Vertex Cover problem.

Parameters:

Returns:

  • Model –

    The optimization model.

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

Extract a structured solution from the solver result.

Parameters:

Returns:

Raises:

Solution

Solution model for Minimum Vertex Cover use case.

MinimumVertexCoverSolution

Bases: UcSolution

Solution for Minimum Vertex Cover.

Attributes:

  • 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:

  • data (MinimumVertexCoverData | 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 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:

  • min_nodes (int) –

    Minimum number of nodes per instance.

  • max_nodes (int) –

    Maximum number of nodes per instance.

  • edge_prob (float, default: 0.5 ) –

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

  • num_instances (int, default: 1 ) –

    Number of instances per node count, by default 1.

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

    Random seed for reproducibility, by default None.

Returns:

Examples:

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