| import json, collections |
|
|
| def reach(edges, src): |
| adj = collections.defaultdict(list) |
| for a, b in edges: adj[a].append(b) |
| seen, q = {src}, [src] |
| while q: |
| u = q.pop() |
| for v in adj[u]: |
| if v not in seen: seen.add(v); q.append(v) |
| return seen |
|
|
| def dist_from(edges, src): |
| adj = collections.defaultdict(list) |
| for a, b in edges: adj[a].append(b) |
| d = {src: 0}; q = collections.deque([src]) |
| while q: |
| u = q.popleft() |
| for v in adj[u]: |
| if v not in d: d[v] = d[u] + 1; q.append(v) |
| return d |
|
|
| for flavor in ("coconut", "bfs"): |
| d = json.load(open(f"data/star_2arm_L6_valid_fo_{flavor}.json")) |
| L = 6; bad = 0; front_sizes = set() |
| for s in d: |
| R = s["root"]; rset = reach(s["edges"], R) |
| fd = dist_from(s["edges"], R) |
| nd = dist_from(s["edges"], s["neg_root"]) |
| if s["target"] not in rset or s["neg_target"] in rset: bad += 1; continue |
| for k in range(1, L + 1): |
| nk = s["neighbor_k"][str(k)]; gk = s["neg_neighbor_k"][str(k)] |
| front_sizes.add(len(nk)) |
| |
| if any(x not in rset or fd.get(x) != k for x in nk): bad += 1; break |
| |
| if any(x in rset or nd.get(x) != k for x in gk): bad += 1; break |
| print(f"{flavor}: {len(d)-bad}/{len(d)} valid | neighbor_k frontier sizes seen: {sorted(front_sizes)} | keys: {sorted(int(k) for k in d[0]['neighbor_k'])}") |
|
|
