"""Generalized Petersen graphs P(n,k): two independent constructors, canonical
edge lists, SHA-256 hashes, invariant tests (T1) and the isomorphism check (P6).

Vertex labelling (canonical, 0-based): u_i -> i, v_i -> n+i for 0 <= i < n.

Constructor A (edge formula): writes the three edge families of definition D1.
Constructor B (circulant adjacency matrix): builds the 2n x 2n matrix
    [[C_n(1), I], [I, C_n(k)]]
where C_n(d)[i][j] = 1 iff j - i = +-d (mod n), and reads the edges off the
matrix. The two paths share no code apart from the labelling convention.
"""
import hashlib
import json
import math
import sys

import common  # noqa: F401  (chdir to run root, sys.path)


def u(i, n):
    return i % n


def v(i, n):
    return n + (i % n)


def edges_formula(n, k):
    """Constructor A. Returns the sorted list of edges (a, b), a < b."""
    E = []
    for i in range(n):
        E.append((u(i, n), u(i + 1, n)))
        E.append((u(i, n), v(i, n)))
        E.append((v(i, n), v(i + k, n)))
    E = [(min(a, b), max(a, b)) for a, b in E]
    return sorted(E)


def edges_circulant(n, k):
    """Constructor B. Builds the block circulant adjacency matrix and extracts edges."""
    N = 2 * n
    M = [[0] * N for _ in range(N)]
    for i in range(n):
        for j in range(n):
            d = (j - i) % n
            if d == 1 or d == n - 1:
                M[i][j] = 1
            if d == k or d == (n - k) % n:
                M[n + i][n + j] = 1
        M[i][n + i] = 1
        M[n + i][i] = 1
    assert all(M[a][b] == M[b][a] for a in range(N) for b in range(N))
    return sorted((a, b) for a in range(N) for b in range(a + 1, N) if M[a][b])


def adjacency(n, k):
    """Adjacency lists (sorted) from constructor A."""
    adj = [[] for _ in range(2 * n)]
    for a, b in edges_formula(n, k):
        adj[a].append(b)
        adj[b].append(a)
    return [sorted(x) for x in adj]


def adjacency_masks(n, k):
    """Bitmask adjacency from constructor A (bit i set in adj[w] iff i ~ w)."""
    adj = [0] * (2 * n)
    for a, b in edges_formula(n, k):
        adj[a] |= 1 << b
        adj[b] |= 1 << a
    return adj


def edge_list_sha256(E):
    return hashlib.sha256(json.dumps([list(e) for e in E], separators=(",", ":")).encode()).hexdigest()


def label(w, n):
    return ("u%d" % w) if w < n else ("v%d" % (w - n))


def labels_to_ids(labels, n):
    out = []
    for s in labels:
        s = s.strip()
        i = int(s[1:])
        out.append(u(i, n) if s[0] == "u" else v(i, n))
    return out


def dihedral_maps(n):
    """The 2n vertex permutations of D_n acting on P(n,k): rotations and reflections.
    Each map is a list perm with perm[w] = image of vertex w."""
    maps = []
    for a in range(n):
        rot = [0] * (2 * n)
        ref = [0] * (2 * n)
        for i in range(n):
            rot[u(i, n)] = u(i + a, n)
            rot[v(i, n)] = v(i + a, n)
            ref[u(i, n)] = u(a - i, n)
            ref[v(i, n)] = v(a - i, n)
        maps.append(rot)
        maps.append(ref)
    return maps


def is_automorphism(perm, Eset):
    return all(((min(perm[a], perm[b]), max(perm[a], perm[b])) in Eset) for a, b in Eset)


def connected(adj):
    N = len(adj)
    seen = [False] * N
    stack = [0]
    seen[0] = True
    while stack:
        w = stack.pop()
        for x in adj[w]:
            if not seen[x]:
                seen[x] = True
                stack.append(x)
    return all(seen)


def inner_cycle_count(n, k):
    """Number of connected components of the inner subgraph (should be gcd(n,k))."""
    adj = adjacency(n, k)
    seen = [False] * n
    comps = 0
    for s in range(n):
        if seen[s]:
            continue
        comps += 1
        stack = [s]
        seen[s] = True
        while stack:
            i = stack.pop()
            for x in adj[n + i]:
                if x >= n and not seen[x - n]:
                    seen[x - n] = True
                    stack.append(x - n)
    return comps


def invariants(n, k):
    """Test T1 for one (n,k). Returns a dict of booleans and values."""
    EA = edges_formula(n, k)
    EB = edges_circulant(n, k)
    adj = adjacency(n, k)
    Eset = set(EA)
    out = {
        "n": n,
        "k": k,
        "constructors_agree": EA == EB,
        "num_vertices": 2 * n,
        "num_edges": len(EA),
        "edges_ok": len(EA) == 3 * n and len(Eset) == 3 * n,
        "no_loops": all(a != b for a, b in EA),
        "cubic": all(len(x) == 3 for x in adj),
        "connected": connected(adj),
        "inner_cycles": inner_cycle_count(n, k),
        "inner_cycles_ok": inner_cycle_count(n, k) == math.gcd(n, k),
        "dihedral_automorphisms": all(is_automorphism(p, Eset) for p in dihedral_maps(n)),
        "sha256": edge_list_sha256(EA),
    }
    out["all_ok"] = all(out[key] for key in ("constructors_agree", "edges_ok", "no_loops", "cubic",
                                               "connected", "inner_cycles_ok", "dihedral_automorphisms"))
    return out


def isomorphism_P6(n, k):
    """P6: if gcd(n,k)=1 and k*l = 1 (mod n), psi(v_{jk}) = u_j, psi(u_{jk}) = v_j is an
    isomorphism P(n,k) -> P(n,l'), l' = min(l, n-l). Returns (l', True/False)."""
    if math.gcd(n, k) != 1:
        return None, None
    l = pow(k, -1, n)
    lp = min(l, n - l)
    psi = [0] * (2 * n)
    for j in range(n):
        psi[v(j * k, n)] = u(j, n)
        psi[u(j * k, n)] = v(j, n)
    target = set(edges_formula(n, lp))
    ok = all(((min(psi[a], psi[b]), max(psi[a], psi[b])) in target) for a, b in edges_formula(n, k))
    return lp, ok


def export_json(n, k, path):
    E = edges_formula(n, k)
    with open(path, "w") as f:
        json.dump({"n": n, "k": k, "labels": [label(w, n) for w in range(2 * n)],
                   "edges": E, "sha256": edge_list_sha256(E)}, f)


def export_graphml(n, k, path):
    E = edges_formula(n, k)
    with open(path, "w") as f:
        f.write('<?xml version="1.0" encoding="UTF-8"?>\n')
        f.write('<graphml xmlns="http://graphml.graphdrawing.org/xmlns">\n')
        f.write('<graph id="P(%d,%d)" edgedefault="undirected">\n' % (n, k))
        for w in range(2 * n):
            f.write('<node id="%s"/>\n' % label(w, n))
        for a, b in E:
            f.write('<edge source="%s" target="%s"/>\n' % (label(a, n), label(b, n)))
        f.write('</graph>\n</graphml>\n')


if __name__ == "__main__":
    # T1 over n = 11..48 (k = 5), plus the Petersen graph P(5,2).
    k = int(sys.argv[1]) if len(sys.argv) > 1 else 5
    nmax = int(sys.argv[2]) if len(sys.argv) > 2 else 48
    rows = []
    allok = True
    for n in list(range(2 * k + 1, nmax + 1)):
        r = invariants(n, k)
        lp, ok = isomorphism_P6(n, k)
        r["P6_partner"] = lp
        r["P6_isomorphism_ok"] = ok
        rows.append(r)
        allok &= r["all_ok"] and (ok is None or ok)
        print(n, k, "ok" if r["all_ok"] else "FAIL", "|E|=%d" % r["num_edges"], "inner cycles=%d" % r["inner_cycles"],
              "P6 partner=%s iso=%s" % (lp, ok), r["sha256"][:16])
    pet = invariants(5, 2)
    print("P(5,2) Petersen", "ok" if pet["all_ok"] else "FAIL", pet["sha256"][:16])
    rows.append(pet)
    print("ALL T1 OK" if allok and pet["all_ok"] else "T1 FAILURES PRESENT")
    with open("results/t1_graph_invariants.json", "w") as f:
        json.dump(rows, f, indent=1)