Skip to content

Max Clique API Reference

Data

Data model for Max Clique use case.

MaxCliqueData

Bases: UcData

Data for the Max Clique use case.

Finds the largest complete subgraph (clique) in a graph.

Attributes:

  • name (Literal['max_clique']) –

    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 Max Clique 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]) -> MaxCliqueData staticmethod

Create MaxCliqueData from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    List of node identifiers.

Returns:

Raises:

  • ValueError –

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

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

Generate a random Max Clique instance.

Parameters:

  • n_nodes (int, default: 5 ) –

    Number of nodes, 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 = MaxCliqueData.generate_random(n_nodes=10, seed=42)

Formulation

Formulation for Max Clique use case.

MaxCliqueFormulation

Bases: UcFormulation[MaxCliqueData, MaxCliqueSolution]

Constraint-based formulation for Max Clique.

Mathematical Formulation

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

Objective: maximize sum_i x_i

Constraints: For each non-edge (i, j): x_i + x_j <= 1

to_string(data: MaxCliqueData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MaxCliqueData) -> Model staticmethod

Formulate the Max Clique problem as a constraint-based model.

Parameters:

  • data (MaxCliqueData) –

    The problem data containing the graph structure.

Returns:

  • Model –

    A Luna Model ready to be solved.

interpret(solution: Solution, data: MaxCliqueData) -> MaxCliqueSolution staticmethod

Extract a Max Clique solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (MaxCliqueData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for Max Clique use case.

MaxCliqueSolution

Bases: UcSolution

Solution for the Max Clique use case.

Attributes:

  • name (Literal['max_clique']) –

    Identifier.

  • clique_nodes (list[int | str]) –

    Nodes in the clique.

  • clique_size (int) –

    Size of the clique.

  • is_valid (bool) –

    Whether all pairs in clique are adjacent.

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

Plot the Max Clique solution on the problem graph.

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

Parameters:

  • data (MaxCliqueData | 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 Max Clique use case.

MaxCliqueInstance

Bases: UcInstance[MaxCliqueData, MaxCliqueFormulation, MaxCliqueSolution]

Instance combining data and formulation for Max Clique.

Collection

Collection of Max Clique instances.

MaxCliqueCollection

Bases: UcInstanceCollection[MaxCliqueInstance]

Collection of Max Clique 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) -> MaxCliqueCollection classmethod

Generate random Max Clique instances.

Parameters:

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

  • edge_prob (float, default: 0.5 ) –

    Edge probability, by default 0.5.

  • 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 = MaxCliqueCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     seed=42,
... )