# (C) Quantum Computing Inc., 2026.
from typing import Dict, Tuple
import numpy as np
import networkx as nx
from eqc_models.base.quadratic import ConstrainedQuadraticModel
[docs]
class GraphColoringModel(ConstrainedQuadraticModel):
"""
Graph k-coloring as a constrained quadratic model.
Binary decision variables x_{i,j} indicate that node i is assigned color
j, for i over the m graph nodes and j over k colors. The one-hot
assignment constraint sum_j x_{i,j} = 1 forces each node to take exactly
one color. The objective counts monochromatic edges (edges whose
endpoints share a color):
min sum_{(u,v) in E} sum_{j=0}^{k-1} x_{u,j} * x_{v,j}
A proper k-coloring exists iff the optimal objective value is zero.
"""
_objective = None
def __init__(self, G: nx.Graph, k: int):
self.G = G
self.k = k
if k < 2:
raise ValueError("k must be greater than 1")
A, b = self._build_constraints()
c, J = self.costFunction()
ConstrainedQuadraticModel.__init__(self, c, J, A, b)
n = len(G.nodes) * k
self.upper_bound = np.ones((n,))
[docs]
def decode(self, solution: np.ndarray) -> np.ndarray:
""" Decode a raw solution to a one-hot color assignment per node. """
decoded_solution = np.zeros_like(solution, dtype=np.int32)
k = self.k
G = self.G
for i, u in enumerate(G.nodes):
idx = slice(k * i, k * (i + 1))
spins = solution[idx]
mx = np.max(spins)
for j in range(k):
if spins[j] == mx:
decoded_solution[k * i + j] = 1
break
return decoded_solution
[docs]
def coloring(self, solution: np.ndarray) -> Dict:
""" Return a dictionary mapping each node to its assigned color (1..k). """
k = self.k
G = self.G
color = {}
for i, u in enumerate(G.nodes):
for j in range(k):
if solution[i * k + j] == 1:
color[u] = j + 1
return color
[docs]
def getConflictCount(self, coloring: Dict) -> int:
""" Count edges whose endpoints share a color (monochromatic edges). """
conflicts = 0
for u, v in self.G.edges:
if coloring[u] == coloring[v]:
conflicts += 1
return conflicts
[docs]
def isProperColoring(self, coloring: Dict) -> bool:
""" True iff no edge is monochromatic (a valid k-coloring of G). """
return self.getConflictCount(coloring) == 0
[docs]
def costFunction(self) -> Tuple:
G = self.G
node_map = list(G.nodes)
m = len(G.nodes)
n = self.k * m
# quadratic objective penalizes same-color assignments on every edge;
# linear portion is zero
objective = np.zeros((n, n), dtype=np.float32)
for u, v in G.edges:
i = node_map.index(u)
j = node_map.index(v)
ibase = i * self.k
jbase = j * self.k
for c in range(self.k):
objective[ibase + c, jbase + c] += 1
return (np.zeros((n, 1)), objective)
def _build_constraints(self):
G = self.G
node_map = list(G.nodes)
m = len(G.nodes)
n = self.k * m
# one-hot: exactly one color per node
A = np.zeros((m, n))
b = np.ones((m,))
for u in G.nodes:
i = node_map.index(u)
ibase = i * self.k
A[i, ibase:ibase + self.k] = 1
return A, b
@property
def constraints(self):
""" Return LHS, RHS in numpy matrix format """
return self.lhs, self.rhs
@property
def objective(self):
""" Return the quadratic objective as NxN+1 matrix """
return self._objective