"""Exact exhaustive small-case battery for Graffiti 290 (n <= 7)
plus named-graph battery for 290 and numeric triage sweep for 295.

290: -lambda_{n-1}(A) <= m / mean_Gr   (lambda_{n-1} = second SMALLEST adjacency eig)
295: (# positive distance-matrix eigenvalues) <= n / mean_Gr

Exact method for 290: mean_Gr is rational; condition -l2min <= R  <=>
  at most ONE root of charpoly(A) lies in (-oo, -R). Counted with Sturm via
  sympy count_roots on exact rationals.
"""
from fractions import Fraction
import itertools
import networkx as nx
import numpy as np
import sympy as sp

def girth_ok(G):
    try:
        g = nx.girth(G)
        return g >= 5
    except Exception:
        return True  # forest => infinite girth

def mean_gravity_frac(G):
    nodes = sorted(G.nodes())
    n = len(nodes)
    deg = {v: G.degree(v) for v in nodes}
    dist = dict(nx.all_pairs_shortest_path_length(G))
    s = Fraction(0)
    for u in nodes:
        for v in nodes:
            if u != v:
                s += Fraction(deg[u] * deg[v], (n - 1) * dist[u][v])
    return s / (n * n)

def check_290_exact(G):
    nodes = sorted(G.nodes())
    n = len(nodes)
    m = G.number_of_edges()
    mg = mean_gravity_frac(G)
    R = Fraction(m, 1) / mg          # rational RHS
    A = sp.Matrix(nx.to_numpy_array(G, nodelist=nodes, dtype=int))
    lam = sp.symbols('lam')
    p = sp.Poly(A.charpoly(lam).as_expr(), lam)
    Rq = sp.Rational(R.numerator, R.denominator)
    # eigenvalues strictly below -R  (bound magnitude by n so interval is finite)
    cnt = p.count_roots(-sp.Integer(n + 1), -Rq)
    # count_roots on (a,b] includes b; subtract roots exactly at -R? count in [-n-1,-R]
    # if second-smallest >= -R then at most one root < -R. Roots AT -R are fine (<=).
    cnt_at = p.count_roots(-Rq, -Rq)
    strictly_below = cnt - cnt_at
    return strictly_below <= 1, strictly_below, float(R)

# ---- exhaustive n <= 7 over the graph atlas ----
from networkx.generators.atlas import graph_atlas_g
tested = 0
worst = None
for G in graph_atlas_g():
    n = G.number_of_nodes()
    if n < 2 or n > 7:
        continue
    if not nx.is_connected(G):
        continue
    if not girth_ok(G):
        continue
    ok, cnt, R = check_290_exact(G)
    tested += 1
    assert ok, f"VIOLATION n={n} edges={sorted(G.edges())}"
print(f"290 exhaustive: all {tested} connected girth>=5 graphs with 2<=n<=7 PASS (exact)")

# ---- named graphs, exact 290 + numeric margins for 290/295 ----
named = {
    'C5': nx.cycle_graph(5), 'C6': nx.cycle_graph(6), 'C7': nx.cycle_graph(7),
    'Petersen': nx.petersen_graph(), 'Heawood': nx.heawood_graph(),
    'Pappus': nx.pappus_graph(), 'Desargues': nx.desargues_graph(),
    'MoebiusKantor': nx.moebius_kantor_graph(),
    'Dodecahedral': nx.dodecahedral_graph(),
    'HoffmanSingleton': nx.hoffman_singleton_graph(),
    'P10path': nx.path_graph(10), 'Star9': nx.star_graph(9),
    'Spider333': nx.Graph([(0,1),(1,2),(2,3),(0,4),(4,5),(5,6),(0,7),(7,8),(8,9)]),
}
print()
print(f"{'graph':<18}{'n':>4}{'m':>5}  {'-l2min':>9} {'m/meanG':>10} {'290 marg':>10} | {'#posD':>6} {'n/meanG':>9} {'295 marg':>9}")
for name, G in named.items():
    if not girth_ok(G) or not nx.is_connected(G):
        continue
    nodes = sorted(G.nodes()); n = len(nodes); m = G.number_of_edges()
    mg = mean_gravity_frac(G)
    R290 = float(Fraction(m,1)/mg); R295 = float(Fraction(n,1)/mg)
    A = nx.to_numpy_array(G, nodelist=nodes, dtype=float)
    eigA = np.sort(np.linalg.eigvalsh(A))
    l2min = eigA[1]
    D = np.zeros((n,n))
    dl = dict(nx.all_pairs_shortest_path_length(G))
    for i,ui in enumerate(nodes):
        for j,vj in enumerate(nodes):
            D[i,j] = dl[ui][vj]
    eigD = np.linalg.eigvalsh(D)
    npos = int((eigD > 1e-8).sum())
    m290 = R290 - (-l2min)   # positive = satisfied
    m295 = R295 - npos
    flag = '' if (m290 > 0 and m295 > 0) else '  <<< VIOLATION?'
    print(f"{name:<18}{n:>4}{m:>5}  {-l2min:>9.4f} {R290:>10.3f} {m290:>10.3f} | {npos:>6} {R295:>9.3f} {m295:>9.3f}{flag}")

# ---- random regular girth>=5 sweep for 295 (numeric triage) ----
print()
print("295 random-regular sweep (worst margins):")
rng_worst = []
import random
for nn in range(10, 61, 5):
    for d in (3, 4, 5):
        if nn*d % 2: continue
        for s in range(6):
            try:
                G = nx.random_regular_graph(d, nn, seed=1000+nn*17+d*3+s)
            except Exception:
                continue
            if not nx.is_connected(G):
                continue
            try:
                if nx.girth(G) < 5: continue
            except Exception:
                continue
            nodes = sorted(G.nodes()); n2 = len(nodes)
            mg = mean_gravity_frac(G)
            R295 = float(Fraction(n2,1)/mg)
            D = np.zeros((n2,n2))
            dl = dict(nx.all_pairs_shortest_path_length(G))
            for i,ui in enumerate(nodes):
                for j,vj in enumerate(nodes):
                    D[i,j] = dl[ui][vj]
            npos = int((np.linalg.eigvalsh(D) > 1e-8).sum())
            rng_worst.append((R295 - npos, f"RR(n={n2},d={d})#{s}", npos, R295))
rng_worst.sort()
for marg, name, npos, R in rng_worst[:8]:
    print(f"  {name:<18} #posD={npos:<4} n/meanG={R:<10.3f} margin={marg:.3f}")
print()
print("smallest 295 margin in sweep:", f"{rng_worst[0][0]:.3f}" if rng_worst else "n/a")