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 | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
to_string() -> str
Format the data as a human-readable string.
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
adjacency_matrix
|
ndarray
|
Symmetric binary adjacency matrix. |
required |
node_names
|
list[int | str]
|
List of node identifiers. |
required |
Returns:
| Type | Description |
|---|---|
MaxCliqueData
|
The Max Clique data instance. |
Raises:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
n_nodes
|
int
|
Number of nodes, by default 5. |
5
|
edge_prob
|
float
|
Probability of an edge between any two nodes, by default 0.5. |
0.5
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
MaxCliqueData
|
A randomly generated data instance. |
Examples:
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MaxCliqueData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
Formatted description of the formulation. |
formulate(data: MaxCliqueData) -> Model
staticmethod
Formulate the Max Clique problem as a constraint-based model.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MaxCliqueData
|
The problem data containing the graph structure. |
required |
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solver solution. |
required |
data
|
MaxCliqueData
|
The original problem data. |
required |
Returns:
| Type | Description |
|---|---|
MaxCliqueSolution
|
Structured solution with clique nodes and validity. |
Raises:
| Type | Description |
|---|---|
NoSolutionFoundError
|
If the solver did not find any solution. |
Solution
Solution model for Max Clique use case.
MaxCliqueSolution
Bases: UcSolution
Solution for the Max Clique use case.
Attributes:
| Name | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MaxCliqueData | None
|
Problem data used to reconstruct the graph. Required --
a |
None
|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
Raises:
| Type | Description |
|---|---|
ValueError
|
If data is |
to_string() -> str
Format the solution as a human-readable string.
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
min_nodes
|
int
|
Minimum number of nodes. |
required |
max_nodes
|
int
|
Maximum number of nodes. |
required |
edge_prob
|
float
|
Edge probability, by default 0.5. |
0.5
|
num_instances
|
int
|
Number of instances per size, by default 1. |
1
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
MaxCliqueCollection
|
Collection containing generated instances. |
Examples: