"""Reproducible MVP for metric-parallel SNF Cayley positional coordinates."""
from collections import deque
from dataclasses import dataclass, asdict
import json
import numpy as np
import sympy as sp
from sympy.matrices.normalforms import smith_normal_form
from sympy.polys.domains import ZZ

@dataclass
class Result:
    name: str; vertices: int; edges: int; classes: int
    cycle_rank: int; snf_torsion: list; free_rank: int
    path_checks: int; path_failures: int; edge_checks: int; edge_failures: int
    raw_dim: int; quotient_dim: int; compression_ratio: float

def cycle_graph(n): return list(range(n)), [(i,(i+1)%n) for i in range(n)]
def torus_graph(m):
    v=[(i,j) for i in range(m) for j in range(m)]; e=[]
    for i,j in v: e += [((i,j),((i+1)%m,j)),((i,j),(i,(j+1)%m))]
    return v,e
def petersen_graph():
    v=list(range(10)); e=[]
    for i in range(5): e += [(i,(i+1)%5),(i,5+i),(5+i,5+(i+2)%5)]
    return v,e

def distances(v,e):
    a={x:[] for x in v}
    for x,y in e: a[x].append(y); a[y].append(x)
    out={}
    for s in v:
        d={s:0}; q=deque([s])
        while q:
            x=q.popleft()
            for y in a[x]:
                if y not in d: d[y]=d[x]+1; q.append(y)
        out[s]=d
    return out

def phi_classes(v,e):
    """Connected components of the paper's undirected metric-parallel relation."""
    d=distances(v,e); p=list(range(len(e)))
    def f(x):
        while p[x]!=x: p[x]=p[p[x]]; x=p[x]
        return x
    def u(x,y):
        x,y=f(x),f(y)
        if x!=y: p[y]=x
    for i,(a,b) in enumerate(e):
        for j in range(i):
            x,y=e[j]
            if (d[a][x]==d[b][y] and d[a][y]==d[b][x]) or (d[a][y]==d[b][x] and d[a][x]==d[b][y]): u(i,j)
    roots={}; cls=[]
    for i in range(len(e)):
        r=f(i); roots.setdefault(r,len(roots)); cls.append(roots[r])
    return cls

def spanning_tree(v,e):
    idx={x:i for i,x in enumerate(v)}; a=[[] for _ in v]
    for ei,(x,y) in enumerate(e):
        a[idx[x]].append((idx[y],ei,1)); a[idx[y]].append((idx[x],ei,-1))
    seen={0}; parent={}; tree=set(); q=deque([0])
    while q:
        x=q.popleft()
        for y,ei,s in a[x]:
            if y not in seen: seen.add(y); parent[y]=(x,ei,s); tree.add(ei); q.append(y)
    return idx,parent,tree

def path_edges(a, b, parent):
    """Edges on the directed tree path from vertex a to vertex b."""
    up_a=[]; x=a
    while x != 0:
        par,ei,s = parent[x]
        up_a.append((x,par,ei,s)); x=par
    up_b=[]; x=b
    while x != 0:
        par,ei,s = parent[x]
        up_b.append((x,par,ei,s)); x=par
    anc_a={x:i for i,(x,_,_,_) in enumerate(up_a)}; anc_a[0]=len(up_a)
    lca=next((x for x,_,_,_ in up_b if x in anc_a), 0)
    if lca not in anc_a: lca=0
    out=[]; x=a
    while x != lca:
        par,ei,s=parent[x]; out.append((ei,-s)); x=par
    down=[]; x=b
    while x != lca:
        par,ei,s=parent[x]; down.append((ei,s)); x=par
    out.extend(reversed(down))
    return out

def cycle_matrix(v,e,cls):
    idx,parent,tree=spanning_tree(v,e); k=max(cls)+1; cols=[]
    for ei,(x,y) in enumerate(e):
        if ei in tree: continue
        c=[0]*k; c[cls[ei]]+=1
        for te,s in path_edges(idx[y],idx[x],parent): c[cls[te]]+=s
        cols.append(c)
    return sp.Matrix(k,len(cols),lambda i,j: cols[j][i]) if cols else sp.zeros(k,0),idx,parent,tree

def run(name, v, e):
    cls=phi_classes(v,e); B,idx,parent,tree=cycle_matrix(v,e,cls); k=max(cls)+1
    D=smith_normal_form(B,domain=ZZ); tors=[]
    for i in range(min(D.rows,D.cols)):
        q=abs(int(D[i,i]))
        if q>1: tors.append(q)
    rank=sum(1 for i in range(min(D.rows,D.cols)) if D[i,i]!=0)
    free=k-rank; quotient=len(tors)+free
    # Exact certificate: every fundamental cycle is a lattice generator.
    # Also verify every edge increment against the tree-integrated labels.
    checks=0; fail=0; edgefail=0
    tree_cols={}
    non_tree=list(ei for ei in range(len(e)) if ei not in tree)
    for j,ei in enumerate(non_tree):
        checks += 1
        fail += int(any(not z.is_Integer for z in B[:,j]))
        tree_cols[ei]=j
    # Tree integration gives z; non-tree edge discrepancies must equal its
    # fundamental cycle (up to the fixed orientation convention).
    labels={v[0]:np.zeros(k,dtype=int)}; q=deque([v[0]]) ; adj={x:[] for x in v}
    for ei,(a,b) in enumerate(e): adj[a].append((b,ei,1)); adj[b].append((a,ei,-1))
    while q:
        x=q.popleft()
        for y,ei,sgn in adj[x]:
            if y not in labels:
                labels[y]=labels[x].copy(); labels[y][cls[ei]]+=sgn; q.append(y)
    for ei,(a,b) in enumerate(e):
        delta=labels[b]-labels[a]; sigma=np.zeros(k,dtype=int); sigma[cls[ei]]=1
        if ei in tree:
            edgefail += int(np.any(delta-sigma))
        else:
            # The discrepancy is a signed fundamental cycle; test either sign.
            col=np.array(B[:,tree_cols[ei]],dtype=int).ravel()
            edgefail += int(not (np.array_equal(delta-sigma,col) or np.array_equal(delta-sigma,-col)))
    return Result(name,len(v),len(e),k,B.cols,tors,free,checks,fail,len(e),edgefail,k,quotient,round(k/quotient,3) if quotient else None)

def main():
    cases=[('C5',*cycle_graph(5)),('C6',*cycle_graph(6)),('Torus3',*torus_graph(3)),('Petersen',*petersen_graph())]
    out=[asdict(run(n,v,e)) for n,v,e in cases]
    print(json.dumps(out,indent=2))
    assert all(x['path_failures']==0 and x['edge_failures']==0 for x in out)

if __name__=='__main__': main()