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

Generate random Minimum Vertex Cover instances.

Parameters:

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

    Minimum number of nodes per instance.

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

    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.

  • 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 = MinimumVertexCoverCollection.from_random(
...     min_nodes=4,
...     max_nodes=6,
...     num_instances=2,
...     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: