Skip to content

Max Independent Set API Reference

Data

Data model for Max Independent Set use case.

MaxIndependentSetData

Bases: UcData

Data for the Max Independent Set use case.

Finds the largest set of vertices with no two adjacent.

Attributes:

  • name (Literal['max_independent_set']) –

    Identifier.

  • adjacency_matrix (BinAdjMatrix) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

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

Plot the Max Independent 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 string.

Returns:

  • str –

    String representation of the data.

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str]) -> MaxIndependentSetData staticmethod

Create a MaxIndependentSetData instance from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix representing the graph.

  • node_names (list[int | str]) –

    Node identifiers. Length must match the number of nodes.

Returns:

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

Generate a random graph 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 = MaxIndependentSetData.generate_random(n_nodes=5, seed=42)

Formulation

Formulation for Max Independent Set use case.

MaxIndependentSetFormulation

Bases: UcFormulation[MaxIndependentSetData, MaxIndependentSetSolution]

Constraint-based formulation for Max Independent Set.

Decision Variables: x[i] in {0,1} Objective: maximize sum_i x[i] Constraints: For each edge (i,j): x[i] + x[j] <= 1

to_string(data: MaxIndependentSetData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MaxIndependentSetData) -> Model staticmethod

Formulate the Max Independent Set problem as a constraint model.

Parameters:

Returns:

  • Model –

    The optimization model ready to be solved.

interpret(solution: Solution, data: MaxIndependentSetData) -> MaxIndependentSetSolution staticmethod

Extract solution from solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (MaxIndependentSetData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for Max Independent Set use case.

MaxIndependentSetSolution

Bases: UcSolution

Solution for Max Independent Set.

Attributes:

  • name (Literal['max_independent_set']) –

    Identifier.

  • independent_set (list[int | str]) –

    Nodes in the independent set.

  • set_size (int) –

    Size of the set.

  • is_valid (bool) –

    No two nodes in set are adjacent.

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

Plot the Max Independent Set solution on the problem graph.

Nodes in the independent set are highlighted.

Parameters:

  • data (MaxIndependentSetData | 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 string.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for Max Independent Set use case.

MaxIndependentSetInstance

Bases: UcInstance[MaxIndependentSetData, MaxIndependentSetFormulation, MaxIndependentSetSolution]

Instance combining data and formulation for Max Independent Set.

Collection

Collection of Max Independent Set instances.

MaxIndependentSetCollection

Bases: UcInstanceCollection[MaxIndependentSetInstance]

Collection of Max Independent Set instances.

from_random(min_nodes: int, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> MaxIndependentSetCollection classmethod

Generate random Max Independent Set instances.

Parameters:

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

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