Skip to content

Minimum Dominating Set API Reference

Data

Data model for Minimum Dominating Set use case.

MdsData

Bases: UcData

Data for the Minimum Dominating Set use case.

Finds a minimum-size set of nodes such that every node is either in the set or adjacent to a member of the set.

Attributes:

  • name (Literal['minimum_dominating_set']) –

    Identifier for this data type.

  • adjacency_matrix (BinAdjMatrix) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

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

Plot the Minimum Dominating Set 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]) -> MdsData staticmethod

Create MdsData from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    List of node identifiers.

Returns:

  • MdsData –

    The Minimum Dominating Set data instance.

Raises:

  • ValueError –

    If the node_names length doesn't match the matrix, or if node_names contains duplicates.

from_graph(graph: nx.Graph) -> MdsData staticmethod

Create MdsData from a NetworkX graph.

Parameters:

  • graph (Graph) –

    A NetworkX graph.

Returns:

  • MdsData –

    The Minimum Dominating Set data instance.

generate_random(n_nodes: int = 6, edge_prob: float = 0.4, seed: int | None = None) -> MdsData staticmethod

Generate a random Minimum Dominating Set instance.

Parameters:

  • n_nodes (int, default: 6 ) –

    Number of nodes, by default 6.

  • edge_prob (float, default: 0.4 ) –

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

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

    Random seed for reproducibility, by default None.

Returns:

  • MdsData –

    A randomly generated data instance.

Examples:

>>> data = MdsData.generate_random(n_nodes=8, seed=42)

Formulation

Formulation for Minimum Dominating Set use case.

MdsFormulation

Bases: UcFormulation[MdsData, MdsSolution]

Constraint-based formulation for Minimum Dominating Set.

Mathematical Formulation 
Symbols:
    n -- number of nodes in the graph.
    N(i) -- the set of neighbours of node i (nodes j with an edge to i).

Decision Variables:
    x_i in {0, 1} -- 1 if node i is in the dominating set, 0 otherwise.

Objective:
    minimize sum_i x_i

Constraints:
    For each node i: x_i + sum_{j in N(i)} x_j >= 1
    (every node must be selected or adjacent to a selected node).

to_string(data: MdsData) -> str staticmethod

Format the formulation as a string.

Parameters:

  • data (MdsData) –

    The problem data.

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MdsData) -> Model staticmethod

Formulate the Minimum Dominating Set problem as a constraint model.

Parameters:

  • data (MdsData) –

    The problem data containing the graph structure.

Returns:

  • Model –

    A Luna Model ready to be solved.

interpret(solution: Solution, data: MdsData) -> MdsSolution staticmethod

Extract a Minimum Dominating Set solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (MdsData) –

    The original problem data.

Returns:

  • MdsSolution –

    Structured solution with the dominating set and validity.

Raises:

Solution

Solution model for Minimum Dominating Set use case.

MdsSolution

Bases: UcSolution

Solution for the Minimum Dominating Set use case.

Attributes:

  • name (Literal['minimum_dominating_set']) –

    Identifier.

  • dominating_set (list[int | str]) –

    Nodes in the dominating set.

  • set_size (int) –

    Size of the dominating set.

  • is_valid (bool) –

    Whether every node is selected or adjacent to a selected node.

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

Plot the Minimum Dominating Set solution on the problem graph.

Selected nodes are highlighted in green; other nodes are grey.

Parameters:

  • data (MdsData | 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 Dominating Set use case.

MdsInstance

Bases: UcInstance[MdsData, MdsFormulation, MdsSolution]

Instance combining data and formulation for Minimum Dominating Set.

Collection

Collection of Minimum Dominating Set instances.

MdsCollection

Bases: UcInstanceCollection[MdsInstance]

Collection of Minimum Dominating Set 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.4, num_instances: int = 1, *, seed: int | None = None) -> MdsCollection classmethod

Generate random Minimum Dominating Set instances.

Parameters:

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

  • edge_prob (float, default: 0.4 ) –

    Edge probability, by default 0.4.

  • 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 = MdsCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     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: