# (C) Quantum Computing Inc., 2026.
from typing import Dict, List, Tuple
import numpy as np
import networkx as nx
from .base import NodeModel
[docs]
class MaxCliqueModel(NodeModel):
"""
Maximum clique as an unconstrained quadratic (QUBO) model.
Binary decision variables x_v in {0, 1} indicate whether node v is in
the clique. The Hamiltonian rewards selecting nodes and penalizes
every pair of selected nodes that is NOT joined by an edge of G:
min H(x) = -A * sum_{v in V} x_v
+ B * sum_{(i,j) not in E, i<j} x_i * x_j
With B > A every optimum is a clique: any non-clique vertex in a
candidate set has at least one non-edge to the retained clique, so
deleting it improves the objective. The maximum clique is the largest
such set, which the reward term selects.
Parameters
----------
G : nx.Graph
Undirected simple graph. Self-loops are ignored.
A : float, optional
Reward coefficient per selected node (default 1.0).
B : float, optional
Penalty coefficient per pair of selected non-adjacent nodes.
Defaults to 2 * A, which is strictly above the A < B threshold
required for correctness and gives the solver a small margin.
"""
def __init__(self, G: nx.Graph, A: float = 1.0, B: float = None):
self.A = float(A)
self.B = float(B) if B is not None else 2.0 * float(A)
super(MaxCliqueModel, self).__init__(G)
[docs]
def costFunction(self) -> Tuple[np.ndarray, np.ndarray]:
"""
Build the linear and quadratic operator for the max-clique QUBO.
Returns
--------
C : (n, 1) ndarray -- linear terms
J : (n, n) ndarray -- symmetric quadratic terms
"""
G = self.G
self.node_map = list(G.nodes)
n = len(self.node_map)
node_index = {u: i for i, u in enumerate(self.node_map)}
self.upper_bound = np.ones((n,), dtype=np.float32)
h = np.zeros((n, 1), dtype=np.float32)
J = np.zeros((n, n), dtype=np.float32)
# reward for including a vertex
h[:, 0] -= self.A
# collect existing edges as an index-pair set; ignore self-loops
edge_set = set()
for u, v in G.edges:
if u == v:
continue
i, j = node_index[u], node_index[v]
edge_set.add((min(i, j), max(i, j)))
# penalty for every pair of non-adjacent nodes; split symmetrically
# so x^T J x has coefficient B on each non-edge pair (i,j), i<j.
half_B = self.B / 2.0
for i in range(n):
for j in range(i + 1, n):
if (i, j) not in edge_set:
J[i, j] += half_B
J[j, i] += half_B
return h, J
@property
def J(self) -> np.ndarray:
return self.quad_objective
@property
def C(self) -> np.ndarray:
return self.linear_objective
@property
def H(self):
return self.linear_objective, self.quad_objective
[docs]
def decode(self, solution: np.ndarray) -> np.ndarray:
""" Threshold to a {0, 1} clique-indicator vector. """
return (np.asarray(solution) > 0.5).astype(np.int32)
[docs]
def clique(self, solution: np.ndarray) -> Dict:
""" Map each node to its in-clique indicator (0 or 1). """
decoded = self.decode(solution)
return {self.node_map[i]: int(decoded[i]) for i in range(len(self.node_map))}
[docs]
def getCliqueNodes(self, clique: Dict) -> List:
""" Return the list of nodes selected as part of the clique. """
return [u for u in self.node_map if clique[u] == 1]
[docs]
def getCliqueSize(self, clique: Dict) -> int:
""" Number of nodes in the clique. """
return sum(1 for u in self.node_map if clique[u] == 1)
[docs]
def getMissingEdgeCount(self, clique: Dict) -> int:
""" Count pairs of selected nodes that are NOT connected by an edge. """
nodes = self.getCliqueNodes(clique)
missing = 0
for i in range(len(nodes)):
for j in range(i + 1, len(nodes)):
if not self.G.has_edge(nodes[i], nodes[j]):
missing += 1
return missing
[docs]
def isValidClique(self, clique: Dict) -> bool:
""" True iff every pair of selected nodes is joined by an edge. """
return self.getMissingEdgeCount(clique) == 0