Source code for eqc_models.graph.maxclique

# (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