# 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

    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)

        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

        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)

        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))}

        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]

        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)

        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

        def isValidClique(self, clique: Dict) -> bool:
            """ True iff every pair of selected nodes is joined by an edge. """
            return self.getMissingEdgeCount(clique) == 0