1"""Zero-forcing closure oracle (definition D3) with complete chronology, replay,2and the order-independence test T2 (empirical companion of Proposition P1).34A coloring is a set of black vertices. A black vertex b with exactly one white5neighbour w may force w. closure() performs forces until none is available and6returns (final_black_set, chronology); the chronology is the list of forces7(b, w) in the order performed. The scan order used to pick the next force is a8parameter (fixed increasing order, or a seeded random permutation at every9step); by P1 the final set does not depend on it.10"""11import json12import random13import sys1415import common # noqa: F40116from graph_constructor import adjacency, label, labels_to_ids171819def closure(adj, S, order="fixed", rng=None):20 """adj: adjacency lists; S: iterable of vertex ids.21 order: 'fixed' (lowest-index available force first) or 'random' (a fresh22 random permutation of the candidate black vertices at every step, using rng)."""23 N = len(adj)24 black = [False] * N25 for w in S:26 black[w] = True27 chron = []28 while True:29 candidates = range(N) if order == "fixed" else rng.sample(range(N), N)30 forced = False31 for b in candidates:32 if not black[b]:33 continue34 white = [x for x in adj[b] if not black[x]]35 if len(white) == 1:36 w = white[0]37 black[w] = True38 chron.append((b, w))39 forced = True40 break # restart the scan: 'fixed' order is then deterministic41 if not forced:42 break43 final = {w for w in range(N) if black[w]}44 return final, chron454647def closure_fast(adjmask, Smask):48 """Bitmask closure (same rule); used by solvers for speed. Returns final mask."""49 B = Smask50 N = len(adjmask)51 changed = True52 while changed:53 changed = False54 rest = B55 while rest:56 low = rest & -rest57 b = low.bit_length() - 158 rest ^= low59 white = adjmask[b] & ~B60 if white and (white & (white - 1)) == 0:61 B |= white62 changed = True63 return B646566def is_zero_forcing(adj, S):67 final, _ = closure(adj, S)68 return len(final) == len(adj)697071def replay(adj, S, chron):72 """Replays a chronology, checking legality of every force. Returns73 (ok, final_black_set, first_bad_index)."""74 N = len(adj)75 black = [False] * N76 for w in S:77 black[w] = True78 for idx, (b, w) in enumerate(chron):79 if not black[b] or black[w]:80 return False, {x for x in range(N) if black[x]}, idx81 white = [x for x in adj[b] if not black[x]]82 if white != [w]:83 return False, {x for x in range(N) if black[x]}, idx84 black[w] = True85 return True, {x for x in range(N) if black[x]}, None868788def order_independence_test(n, k, seeds_per_n=200, orders_per_seed=20, sizes=(3, 8), seed=20261030):89 """T2: for random S, compare the final black set over random force orders."""90 adj = adjacency(n, k)91 N = 2 * n92 rng = random.Random(seed * 1000 + n)93 passed = 094 total = 095 for _ in range(seeds_per_n):96 s = rng.randint(sizes[0], sizes[1])97 S = rng.sample(range(N), s)98 ref, _ = closure(adj, S)99 finals = set()100 for _ in range(orders_per_seed):101 fin, _ = closure(adj, S, order="random", rng=rng)102 finals.add(frozenset(fin))103 total += 1104 if len(finals) == 1 and frozenset(ref) in finals:105 passed += 1106 return passed, total107108109if __name__ == "__main__":110 k = 5111 report = []112 allok = True113 for n in range(11, 17):114 p, t = order_independence_test(n, k)115 print("T2 n=%d: %d/%d seed sets had an order-independent closure" % (n, p, t))116 report.append({"n": n, "k": k, "passed": p, "total": t})117 allok &= p == t118 print("T2 ALL OK" if allok else "T2 FAILURE")119 with open("results/t2_order_independence.json", "w") as f:120 json.dump(report, f, indent=1)121