// === Tranche 2 (#10382) : coloration optimale via Google.OrTools CP-SAT ===
#r "nuget: Google.OrTools, 9.11.4210"
using Google.OrTools.Sat;
// Modele CP-SAT : minimiser le nombre de couleurs (miroir de cpsat_coloring cote Python).
// color_vars[v] dans [0, upper-1] ; max_color_var ; color_vars[v] <= max_color_var ;
// aretes (u,v) : color_vars[u] != color_vars[v] ; brisure de symetrie color_vars[0]==0.
(int[] coloring, int nColors, string status, double ms) CpsatColor(Graph g, int upper, int timeLimitS = 8) {
var model = new CpModel();
var colorVars = new IntVar[g.N];
for (int v = 0; v < g.N; v++)
colorVars[v] = model.NewIntVar(0, upper - 1, $"c{v}");
IntVar maxColor = model.NewIntVar(0, upper - 1, "maxColor");
for (int v = 0; v < g.N; v++)
model.Add(colorVars[v] <= maxColor);
for (int v = 0; v < g.N; v++)
foreach (int u in g.Adj[v])
if (u > v) // chaque arete une seule fois
model.Add(colorVars[u] != colorVars[v]);
model.Add(colorVars[0] == 0); // brisure de symetrie
model.Minimize(maxColor);
var solver = new CpSolver();
solver.StringParameters = $"max_time_in_seconds:{timeLimitS}";
var sw = System.Diagnostics.Stopwatch.StartNew();
var result = solver.Solve(model);
sw.Stop();
string status = result.ToString();
int nColors = (result == CpSolverStatus.Optimal || result == CpSolverStatus.Feasible)
? (int)solver.Value(maxColor) + 1 : -1;
int[] coloring = new int[g.N];
if (nColors > 0)
for (int v = 0; v < g.N; v++) coloring[v] = (int)solver.Value(colorVars[v]);
return (coloring, nColors, status, sw.Elapsed.TotalMilliseconds);
}
// --- Validation sur les cas a chi connu (parite avec le backtracking exact §3) ---
Show("--- Tranche 2 : CP-SAT (Google.OrTools 9.11) sur les cas a chi connu ---");
Show($"{"graphe",-10} | {"chi connu",9} | {"CP-SAT",7} | {"statut",9} | {"ms",7}");
foreach (var c in new[] {
("K4", Complete(4), 4), ("K6", Complete(6), 6),
("C5", Cycle(5), 3), ("C6", Cycle(6), 2),
("Petersen", Petersen(), 3), ("K_{3,3}", CompleteBipartite(3,3), 2),
("M_3", MycielskiK(1), 3), ("M_4", MycielskiK(2), 4),
}) {
var (col, nC, st, ms) = CpsatColor(c.Item2, c.Item2.N);
string ok = nC == c.Item3 ? "OK" : "ECHEC";
Show($"{c.Item1,-10} | {c.Item3,9} | {nC,7} | {st,9} | {FI(ms,"F1"),7} {ok}");
}
// --- Prong-B (#3801) : discrimination heuristiques vs CP-SAT sur Erdos-Renyi dense ---
// Sur G(n, p>=0.3), greedy et DSATUR utilisent STRICTEMENT plus de couleurs que chi :
// c'est le cas ou le solveur optimal (CP-SAT) se justifie face aux heuristiques.
Show("");
Show("--- Prong-B : heuristiques vs CP-SAT (chi exact) sur Erdos-Renyi G(25, 0.5) ---");
Show($"{"graphe",-14} | {"Greedy",6} | {"DSATUR",7} | {"CP-SAT",6} | {"statut",9} | {"ms",7}");
foreach (int seed in new[] { 1, 7, 42 }) {
var g = RandomGraph(25, 0.5, seed);
int gd = ColorsUsed(GreedyColor(g, OrderDegreeDesc(g)));
int ds = ColorsUsed(DsaturColor(g));
var (col, chi, st, ms) = CpsatColor(g, 25);
string disc = (gd > chi || ds > chi) ? "<- sub-optimal" : "";
Show($"G(25,0.5,s{seed})".PadRight(14) + " | " + gd.ToString().PadLeft(6) + " | " + ds.ToString().PadLeft(7) + " | " + chi.ToString().PadLeft(6) + " | " + st.PadLeft(9) + " | " + FI(ms,"F0").PadLeft(7) + " " + disc);
}