# === VISUALISATION — trois figures sur les mesures des cellules 2 et 4 ===
#
# Toutes les grandeurs tracées ici sont MESURÉES dans cette cellule : aucune n'est recopiée de
# la prose. Le squelette de Beck-Fiala est rejoué phase par phase sur une instance choisie, et la
# recherche aléatoire est rejouée avec la même graine que la cellule 4 (le dernier point de la
# courbe doit donc valoir `rnd_discs[0]` — c'est vérifié juste après le calcul).
#
# figure 1 : distribution des discrépances BF-squelette contre random best-50, et les bornes
# figure 2 : trace de convergence — phases du squelette, tirages de la recherche aléatoire
# figure 3 : matrice de signes de la coloration finale (une ligne = une partie de F)
import matplotlib.pyplot as plt
from matplotlib.colors import BoundaryNorm, ListedColormap
def discrepance_arrondie(F, c):
"""Discrépance de la coloration courante, arrondie par signe (`c[x] >= 0` donne `+1`)."""
return discrepancy_int(F, {x: (1 if c[x] >= 0 else -1) for x in c})
def beck_fiala_trace(F, k, max_iter=100, seed=7):
"""Rejoue la boucle de `beck_fiala` en conservant la trace, phase par phase.
Renvoie `(disc, flottants, figes)` : discrépance de la coloration arrondie, nombre de
flottants restants et nombre de sommets figés, avant la première phase puis après chacune.
La graine est fixée, car `rounding_pass` tire son pas dans `random.uniform`.
"""
random.seed(seed)
universe = set().union(*F) if F else set()
if not universe:
return [], [], []
c = {x: 0.0 for x in universe}
X = set(universe)
disc, flottants, figes = [discrepance_arrondie(F, c)], [len(X)], [0]
for _ in range(max_iter):
danger = [S for S in F if len(S & X) > k]
if not danger:
break
c, X, _, progress = rounding_pass(F, k, c, X, danger)
disc.append(discrepance_arrondie(F, c))
flottants.append(len(X))
figes.append(len(universe) - len(X))
if not progress or not X:
break
return disc, flottants, figes
def courbe_recherche_aleatoire(F, n_sommets, n_restarts=50, seed=2000):
"""Meilleure discrépance atteinte après `n` tirages aléatoires (`n` de 1 à 50)."""
rng = random.Random(seed)
meilleur, courbe = None, []
for _ in range(n_restarts):
d = discrepancy_int(F, random_coloring(n_sommets, rng))
meilleur = d if meilleur is None else min(meilleur, d)
courbe.append(meilleur)
return courbe
# --- Instance E7 : la première instance de la cellule 4 (`seed=1000`), rejouée pour la trace. ---
E7 = random_hypergraph(10, 15, 2, seed=1000)
E7_MAXDEG = max_degree(E7)
e7_disc, e7_flottants, e7_figes = beck_fiala_trace(E7, 2)
e7_courbe = courbe_recherche_aleatoire(E7, 10)
e7_color = beck_fiala(E7, 2)[0]
E7_SOMMETS = sorted(set().union(*E7))
print(f"Instance E7 (n=10, m=15, k_max=2, seed=1000) : |F|={len(E7)}, maxDegree={E7_MAXDEG}")
print(f" trace du squelette : disc={e7_disc} flottants={e7_flottants} figes={e7_figes}")
print(f" recherche aleatoire : meilleure disc apres 50 tirages = {e7_courbe[-1]}")
print(f" coherence cellule 4 : e7_courbe[-1] == rnd_discs[0] -> {e7_courbe[-1] == rnd_discs[0]}")
print(f" coloration finale : {sorted(set(e7_color.values()))} (sommets a +1 : "
f"{sum(1 for x in e7_color if e7_color[x] == 1)} / {len(e7_color)})")
# --- Figure 1 : distribution des discrépances, BF-squelette contre random best-50. ---
fig1, (f1a, f1b) = plt.subplots(1, 2, figsize=(11.0, 4.0))
valeurs = sorted(set(bf_discs) | set(rnd_discs))
demi = 0.38
f1a.bar([v - demi for v in valeurs], [bf_discs.count(v) for v in valeurs], 2 * demi,
color="#d62728", label="BF-squelette")
f1a.bar([v + demi for v in valeurs], [rnd_discs.count(v) for v in valeurs], 2 * demi,
color="#1f77b4", label="random best-50")
f1a.axvline(2 * kmax - 1, color="black", linestyle="--", linewidth=1.2,
label=f"borne naive 2*k_max-1 = {2 * kmax - 1} (precondition violee 40/40)")
f1a.axvline(statistics.mean(max_degrees) * 2 - 1, color="gray", linestyle=":", linewidth=1.6,
label=f"borne effective moyenne = "
f"{statistics.mean(2 * d - 1 for d in max_degrees):.2f}")
f1a.set_xlabel("discrepance")
f1a.set_ylabel("nombre d'instances (sur 40)")
f1a.set_title("Les deux supports ne se recouvrent pas")
f1a.legend(fontsize=8)
f1a.grid(axis="y", alpha=0.3)
f1b.step(range(1, len(bf_discs) + 1), bf_discs, where="mid", color="#d62728",
label="BF-squelette")
f1b.step(range(1, len(rnd_discs) + 1), rnd_discs, where="mid", color="#1f77b4",
label="random best-50")
f1b.set_xlabel("instance (1 a 40)")
f1b.set_ylabel("discrepance")
f1b.set_title("Instance par instance : BF perd 40 fois sur 40")
f1b.legend(fontsize=8)
f1b.grid(alpha=0.3)
fig1.tight_layout()
plt.show()
# --- Figure 2 : trace de convergence, squelette contre recherche aléatoire. ---
fig2, (f2a, f2b) = plt.subplots(1, 2, figsize=(11.0, 4.0))
phases = list(range(len(e7_disc)))
f2a.step(phases, e7_disc, where="post", marker="o", color="#d62728",
label="discrepance du squelette apres chaque phase")
f2a.step(phases, e7_flottants, where="post", marker="s", color="#7f7f7f", linestyle="-.",
label="flottants restants |X|")
f2a.axhline(2 * kmax - 1, color="black", linestyle="--", linewidth=1.2,
label=f"borne naive 2*k_max-1 = {2 * kmax - 1} (non applicable)")
f2a.axhline(2 * E7_MAXDEG - 1, color="gray", linestyle=":", linewidth=1.6,
label=f"borne effective 2*maxDegree(E7)-1 = {2 * E7_MAXDEG - 1}")
f2a.set_xlabel("phase (0 = depart)")
f2a.set_xticks(phases)
f2a.set_ylabel("valeur")
f2a.set_title(f"Squelette sur E7 : plate ({e7_figes[-1]} fige, arret par `not progress`)")
f2a.legend(fontsize=7, loc="center right")
f2a.grid(alpha=0.3)
f2b.plot(range(1, len(e7_courbe) + 1), e7_courbe, marker=".", color="#1f77b4",
label="meilleure discrepance apres n tirages")
f2b.axhline(2 * kmax - 1, color="black", linestyle="--", linewidth=1.2,
label=f"borne naive 2*k_max-1 = {2 * kmax - 1} (non applicable)")
f2b.axhline(2 * E7_MAXDEG - 1, color="gray", linestyle=":", linewidth=1.6,
label=f"borne effective 2*maxDegree(E7)-1 = {2 * E7_MAXDEG - 1}")
f2b.set_xlabel("nombre de tirages aléatoires")
f2b.set_ylabel("discrepance")
f2b.set_title("Recherche aleatoire sur la meme instance : elle descend vraiment")
f2b.legend(fontsize=7, loc="upper right")
f2b.grid(alpha=0.3)
fig2.tight_layout()
plt.show()
# --- Figure 3 : matrice de signes de la coloration finale. ---
CMAP = ListedColormap(["#ff7f0e", "#eaeaea", "#1f77b4"])
NORM = BoundaryNorm([-1.5, -0.5, 0.5, 1.5], 3)
def dessine_matrice(ax, F, coloring, sommets, titre, k):
"""Une ligne par partie de `F`, une colonne par sommet ; la case vaut `c[x]` si `x in S`."""
m = [[coloring[x] if x in S else 0 for x in sommets] for S in F]
ax.imshow(m, cmap=CMAP, norm=NORM, aspect="auto")
etiquettes = []
for i, S in enumerate(F):
danger = "dangereuse" if len(S) > k else "sure"
etiquettes.append(f"L{i + 1:02d} |S|={len(S)} somme={sum(m[i]):+d} {danger}")
ax.set_yticks(range(len(F)))
ax.set_yticklabels(etiquettes, fontsize=5)
for tick, S in zip(ax.get_yticklabels(), F):
tick.set_color("#b00000" if len(S) > k else "black")
ax.set_xticks(range(len(sommets)))
ax.set_xticklabels([f"x{x}" for x in sommets], fontsize=6)
ax.set_title(titre)
ax.set_xlabel("sommet (bleu : +1, orange : -1, gris : x hors de S)")
fig3, (f3a, f3b) = plt.subplots(1, 2, figsize=(12.0, 5.6))
dessine_matrice(f3a, E7, e7_color, E7_SOMMETS,
f"E7 : {len(E7)} parties x {len(E7_SOMMETS)} sommets, k={kmax}", kmax)
dessine_matrice(f3b, triples_6, coloring6, list(range(n6)),
f"triples de [n={n6}] : {len(triples_6)} parties x {n6} sommets, k={k6}", k6)
fig3.tight_layout()
plt.show()
print(f"Lectures : la coloration finale de E7 ne contient que {sorted(set(e7_color.values()))} ; "
f"les sommes par ligne valent donc les cardinalites |S| elles-memes.")
print(f" E7 : disc = {discrepancy_int(E7, e7_color)} = max |S| = {max(len(S) for S in E7)}")
print(f" triples_6 : disc = {discrepancy_int(triples_6, coloring6)} = max |S| = "
f"{max(len(S) for S in triples_6)}")
