1"""Generalized Petersen graphs P(n,k): two independent constructors, canonical2edge lists, SHA-256 hashes, invariant tests (T1) and the isomorphism check (P6).34Vertex labelling (canonical, 0-based): u_i -> i, v_i -> n+i for 0 <= i < n.56Constructor A (edge formula): writes the three edge families of definition D1.7Constructor B (circulant adjacency matrix): builds the 2n x 2n matrix8 [[C_n(1), I], [I, C_n(k)]]9where C_n(d)[i][j] = 1 iff j - i = +-d (mod n), and reads the edges off the10matrix. The two paths share no code apart from the labelling convention.11"""12import hashlib13import json14import math15import sys1617import common # noqa: F401 (chdir to run root, sys.path)181920def u(i, n):21 return i % n222324def v(i, n):25 return n + (i % n)262728def edges_formula(n, k):29 """Constructor A. Returns the sorted list of edges (a, b), a < b."""30 E = []31 for i in range(n):32 E.append((u(i, n), u(i + 1, n)))33 E.append((u(i, n), v(i, n)))34 E.append((v(i, n), v(i + k, n)))35 E = [(min(a, b), max(a, b)) for a, b in E]36 return sorted(E)373839def edges_circulant(n, k):40 """Constructor B. Builds the block circulant adjacency matrix and extracts edges."""41 N = 2 * n42 M = [[0] * N for _ in range(N)]43 for i in range(n):44 for j in range(n):45 d = (j - i) % n46 if d == 1 or d == n - 1:47 M[i][j] = 148 if d == k or d == (n - k) % n:49 M[n + i][n + j] = 150 M[i][n + i] = 151 M[n + i][i] = 152 assert all(M[a][b] == M[b][a] for a in range(N) for b in range(N))53 return sorted((a, b) for a in range(N) for b in range(a + 1, N) if M[a][b])545556def adjacency(n, k):57 """Adjacency lists (sorted) from constructor A."""58 adj = [[] for _ in range(2 * n)]59 for a, b in edges_formula(n, k):60 adj[a].append(b)61 adj[b].append(a)62 return [sorted(x) for x in adj]636465def adjacency_masks(n, k):66 """Bitmask adjacency from constructor A (bit i set in adj[w] iff i ~ w)."""67 adj = [0] * (2 * n)68 for a, b in edges_formula(n, k):69 adj[a] |= 1 << b70 adj[b] |= 1 << a71 return adj727374def edge_list_sha256(E):75 return hashlib.sha256(json.dumps([list(e) for e in E], separators=(",", ":")).encode()).hexdigest()767778def label(w, n):79 return ("u%d" % w) if w < n else ("v%d" % (w - n))808182def labels_to_ids(labels, n):83 out = []84 for s in labels:85 s = s.strip()86 i = int(s[1:])87 out.append(u(i, n) if s[0] == "u" else v(i, n))88 return out899091def dihedral_maps(n):92 """The 2n vertex permutations of D_n acting on P(n,k): rotations and reflections.93 Each map is a list perm with perm[w] = image of vertex w."""94 maps = []95 for a in range(n):96 rot = [0] * (2 * n)97 ref = [0] * (2 * n)98 for i in range(n):99 rot[u(i, n)] = u(i + a, n)100 rot[v(i, n)] = v(i + a, n)101 ref[u(i, n)] = u(a - i, n)102 ref[v(i, n)] = v(a - i, n)103 maps.append(rot)104 maps.append(ref)105 return maps106107108def is_automorphism(perm, Eset):109 return all(((min(perm[a], perm[b]), max(perm[a], perm[b])) in Eset) for a, b in Eset)110111112def connected(adj):113 N = len(adj)114 seen = [False] * N115 stack = [0]116 seen[0] = True117 while stack:118 w = stack.pop()119 for x in adj[w]:120 if not seen[x]:121 seen[x] = True122 stack.append(x)123 return all(seen)124125126def inner_cycle_count(n, k):127 """Number of connected components of the inner subgraph (should be gcd(n,k))."""128 adj = adjacency(n, k)129 seen = [False] * n130 comps = 0131 for s in range(n):132 if seen[s]:133 continue134 comps += 1135 stack = [s]136 seen[s] = True137 while stack:138 i = stack.pop()139 for x in adj[n + i]:140 if x >= n and not seen[x - n]:141 seen[x - n] = True142 stack.append(x - n)143 return comps144145146def invariants(n, k):147 """Test T1 for one (n,k). Returns a dict of booleans and values."""148 EA = edges_formula(n, k)149 EB = edges_circulant(n, k)150 adj = adjacency(n, k)151 Eset = set(EA)152 out = {153 "n": n,154 "k": k,155 "constructors_agree": EA == EB,156 "num_vertices": 2 * n,157 "num_edges": len(EA),158 "edges_ok": len(EA) == 3 * n and len(Eset) == 3 * n,159 "no_loops": all(a != b for a, b in EA),160 "cubic": all(len(x) == 3 for x in adj),161 "connected": connected(adj),162 "inner_cycles": inner_cycle_count(n, k),163 "inner_cycles_ok": inner_cycle_count(n, k) == math.gcd(n, k),164 "dihedral_automorphisms": all(is_automorphism(p, Eset) for p in dihedral_maps(n)),165 "sha256": edge_list_sha256(EA),166 }167 out["all_ok"] = all(out[key] for key in ("constructors_agree", "edges_ok", "no_loops", "cubic",168 "connected", "inner_cycles_ok", "dihedral_automorphisms"))169 return out170171172def isomorphism_P6(n, k):173 """P6: if gcd(n,k)=1 and k*l = 1 (mod n), psi(v_{jk}) = u_j, psi(u_{jk}) = v_j is an174 isomorphism P(n,k) -> P(n,l'), l' = min(l, n-l). Returns (l', True/False)."""175 if math.gcd(n, k) != 1:176 return None, None177 l = pow(k, -1, n)178 lp = min(l, n - l)179 psi = [0] * (2 * n)180 for j in range(n):181 psi[v(j * k, n)] = u(j, n)182 psi[u(j * k, n)] = v(j, n)183 target = set(edges_formula(n, lp))184 ok = all(((min(psi[a], psi[b]), max(psi[a], psi[b])) in target) for a, b in edges_formula(n, k))185 return lp, ok186187188def export_json(n, k, path):189 E = edges_formula(n, k)190 with open(path, "w") as f:191 json.dump({"n": n, "k": k, "labels": [label(w, n) for w in range(2 * n)],192 "edges": E, "sha256": edge_list_sha256(E)}, f)193194195def export_graphml(n, k, path):196 E = edges_formula(n, k)197 with open(path, "w") as f:198 f.write('<?xml version="1.0" encoding="UTF-8"?>\n')199 f.write('<graphml xmlns="http://graphml.graphdrawing.org/xmlns">\n')200 f.write('<graph id="P(%d,%d)" edgedefault="undirected">\n' % (n, k))201 for w in range(2 * n):202 f.write('<node id="%s"/>\n' % label(w, n))203 for a, b in E:204 f.write('<edge source="%s" target="%s"/>\n' % (label(a, n), label(b, n)))205 f.write('</graph>\n</graphml>\n')206207208if __name__ == "__main__":209 # T1 over n = 11..48 (k = 5), plus the Petersen graph P(5,2).210 k = int(sys.argv[1]) if len(sys.argv) > 1 else 5211 nmax = int(sys.argv[2]) if len(sys.argv) > 2 else 48212 rows = []213 allok = True214 for n in list(range(2 * k + 1, nmax + 1)):215 r = invariants(n, k)216 lp, ok = isomorphism_P6(n, k)217 r["P6_partner"] = lp218 r["P6_isomorphism_ok"] = ok219 rows.append(r)220 allok &= r["all_ok"] and (ok is None or ok)221 print(n, k, "ok" if r["all_ok"] else "FAIL", "|E|=%d" % r["num_edges"], "inner cycles=%d" % r["inner_cycles"],222 "P6 partner=%s iso=%s" % (lp, ok), r["sha256"][:16])223 pet = invariants(5, 2)224 print("P(5,2) Petersen", "ok" if pet["all_ok"] else "FAIL", pet["sha256"][:16])225 rows.append(pet)226 print("ALL T1 OK" if allok and pet["all_ok"] else "T1 FAILURES PRESENT")227 with open("results/t1_graph_invariants.json", "w") as f:228 json.dump(rows, f, indent=1)229