# Source code for eqc_models.graph.vertexcover

    # (C) Quantum Computing Inc., 2026.
    from typing import Dict, List, Tuple
    import numpy as np
    import networkx as nx
    from eqc_models.base.quadratic import ConstrainedQuadraticModel

    class VertexCoverModel(ConstrainedQuadraticModel):
        """
        Minimum vertex cover as a constrained quadratic model.

        Binary decision variables x_v in {0, 1} indicate whether node v is in
        the cover. The objective minimizes the cover size:

            min  sum_{v in V} x_v

        For every edge (u, v) in E, the cover requirement x_u + x_v >= 1 ensures
        at least one endpoint is in the cover. Each inequality is converted to an
        equality with a binary slack variable s_e per edge e = (u, v):

            x_u + x_v - s_e = 1,   s_e in {0, 1}

        A valid vertex cover exists iff all edge constraints can be satisfied;
        the optimum minimizes the number of selected nodes.
        """

        def __init__(self, G: nx.Graph):
            self.G = G
            self.node_map = list(G.nodes)
            self.edge_map = list(G.edges)
            n = len(self.node_map)
            m = len(self.edge_map)
            N = n + m

            # constraints: x_u + x_v - s_e = 1 for each edge e
            A = np.zeros((m, N), dtype=np.float32)
            b = np.ones((m,), dtype=np.float32)
            node_index = {u: i for i, u in enumerate(self.node_map)}
            for k, (u, v) in enumerate(self.edge_map):
                A[k, node_index[u]] = 1.0
                A[k, node_index[v]] = 1.0
                A[k, n + k] = -1.0

            # objective: linear cardinality on x variables; slacks have weight 0
            h = np.zeros((N,), dtype=np.float32)
            h[:n] = 1.0
            J = np.zeros((N, N), dtype=np.float32)

            ConstrainedQuadraticModel.__init__(self, h, J, A, b)
            self.upper_bound = np.ones((N,), dtype=np.float32)

        @property
        def variables(self) -> List[str]:
            """ Variable names: x_<node> for each node, then s_<edge_index> per edge. """
            names = [f"x_{u}" for u in self.node_map]
            names.extend([f"s_{k}" for k in range(len(self.edge_map))])
            return names

        def decode(self, solution: np.ndarray) -> np.ndarray:
            """ Threshold the first n entries to obtain a binary cover indicator vector. """
            n = len(self.node_map)
            decoded = np.zeros_like(solution, dtype=np.int32)
            decoded[:n] = (np.asarray(solution[:n]) > 0.5).astype(np.int32)
            return decoded

        def cover(self, solution: np.ndarray) -> Dict:
            """ Return a dictionary mapping each node to its cover indicator (0 or 1). """
            n = len(self.node_map)
            return {self.node_map[i]: int(solution[i] > 0.5) for i in range(n)}

        def getCoverNodes(self, cover: Dict) -> List:
            """ Return the list of nodes selected in the cover. """
            return [u for u in self.node_map if cover[u] == 1]

        def getCoverSize(self, cover: Dict) -> int:
            """ Number of nodes in the cover. """
            return sum(1 for u in self.node_map if cover[u] == 1)

        def getUncoveredEdgeCount(self, cover: Dict) -> int:
            """ Count edges with neither endpoint in the cover. """
            return sum(1 for u, v in self.G.edges if cover[u] == 0 and cover[v] == 0)

        def isValidCover(self, cover: Dict) -> bool:
            """ True iff every edge has at least one endpoint in the cover. """
            return self.getUncoveredEdgeCount(cover) == 0

        def costFunction(self) -> Tuple[np.ndarray, np.ndarray]:
            """ Return the linear and quadratic pieces of the cardinality objective. """
            return self.linear_objective, self.quad_objective

        @property
        def constraints(self):
            """ Return LHS, RHS in numpy matrix format. """
            return self.lhs, self.rhs

        @property
        def objective(self):
            """ Linear objective vector (cardinality on x, zeros on slacks). """
            return self.linear_objective