File size: 5,261 Bytes
a07f822 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | """Corollary 1: parametric max-flow computation of the whole nested sequence,
certified against brute force, then timed. Replaces 2^n enumeration."""
import time, json, math, numpy as np
from collections import deque
EPS = 1e-9; INF = float("inf")
class Dinic:
def __init__(s, N):
s.N=N; s.to=[]; s.cap=[]; s.head=[-1]*N; s.nxt=[]; s.radj=[[] for _ in range(N)]; s.ops=0
def add(s,u,v,c):
s.to.append(v); s.cap.append(c); s.nxt.append(s.head[u]); s.head[u]=len(s.to)-1
s.radj[v].append((u,len(s.to)-1))
s.to.append(u); s.cap.append(0.0); s.nxt.append(s.head[v]); s.head[v]=len(s.to)-1
s.radj[u].append((v,len(s.to)-1))
def bfs(s,src,snk):
s.lv=[-1]*s.N; s.lv[src]=0; q=deque([src])
while q:
u=q.popleft(); e=s.head[u]
while e!=-1:
s.ops+=1; v=s.to[e]
if s.cap[e]>EPS and s.lv[v]<0: s.lv[v]=s.lv[u]+1; q.append(v)
e=s.nxt[e]
return s.lv[snk]>=0
def dfs(s,u,snk,f):
if u==snk: return f
while s.it[u]!=-1:
e=s.it[u]; v=s.to[e]; s.ops+=1
if s.cap[e]>EPS and s.lv[v]==s.lv[u]+1:
d=s.dfs(v,snk,min(f,s.cap[e]))
if d>EPS: s.cap[e]-=d; s.cap[e^1]+=d; return d
s.it[u]=s.nxt[e]
return 0.0
def maxflow(s,src,snk):
fl=0.0
while s.bfs(src,snk):
s.it=s.head[:]
while True:
f=s.dfs(src,snk,INF)
if f<=EPS: break
fl+=f
return fl
def reach_t(s,snk):
seen=[False]*s.N; seen[snk]=True; q=deque([snk])
while q:
v=q.popleft()
for u,eid in s.radj[v]:
if not seen[u] and s.cap[eid]>EPS: seen[u]=True; q.append(u)
return seen
def solve(n, edges, w, lam, stats):
"""maximal minimizer of |S| - lam*w(S), via max-closure min-cut."""
m=len(edges); s=n+m; t=n+m+1; g=Dinic(n+m+2)
for j,e in enumerate(edges):
g.add(s,n+j,lam*float(w[j]))
for v in e: g.add(n+j,v,INF)
for v in range(n): g.add(v,t,1.0)
g.maxflow(s,t); stats["flows"]+=1; stats["ops"]+=g.ops
can=g.reach_t(t)
return frozenset(v for v in range(n) if not can[v])
def wsum(S,edges,w): return float(sum(w[j] for j,e in enumerate(edges) if all(v in S for v in e)))
def sequence(n, edges, w, stats, lam_max=None):
if lam_max is None: lam_max=2.0*(n+1)/max(1e-9,min(w))+1.0
lo,hi=0.0,lam_max
Slo=solve(n,edges,w,lo,stats); Shi=solve(n,edges,w,hi,stats)
out={Slo,Shi}
def rec(a,b,Sa,Sb,d=0):
if Sa==Sb or d>60: return
wa,ca=wsum(Sa,edges,w),len(Sa); wb,cb=wsum(Sb,edges,w),len(Sb)
if abs(wb-wa)<1e-12: return
lam=(cb-ca)/(wb-wa)
if not (a+1e-12 < lam < b-1e-12): return
S=solve(n,edges,w,lam,stats); out.add(S)
if S!=Sa and S!=Sb: rec(a,lam,Sa,S,d+1); rec(lam,b,S,Sb,d+1)
rec(lo,hi,Slo,Shi)
return sorted(out,key=len)
# ---- brute force reference (the logbook's original primitive) --------------
def brute(n, edges, w):
"""exact reference: walk the lower envelope of |S| - lam*w(S) over all 2^n masks.
Only O(gamma) probes are needed, so this stays exact without the O(4^n) crossing scan."""
M=1<<n; masks=np.arange(M)
bits=np.zeros(M,dtype=np.int64)
for v in range(n): bits+=(masks>>v)&1
bym=np.zeros(M)
for j,e in enumerate(edges):
em=0
for v in e: em|=1<<v
bym+=w[j]*((masks&em)==em)
def argmax_set(lam):
obj=bits-lam*bym; best=obj.min()
return int(np.bitwise_or.reduce(masks[obj<=best+2e-9]))
bps=[]; lam=0.0
for _ in range(4*n+8):
u=argmax_set(lam); w0=bym[u]; b0=bits[u]
gt=bym>w0+1e-12
if not gt.any(): break
cand=(bits[gt]-b0)/(bym[gt]-w0)
cand=cand[cand>lam+1e-9]
if cand.size==0: break
lam=float(cand.min()); bps.append(lam)
probes=[0.0]+bps
for a,b in zip(bps,bps[1:]): probes.append((a+b)/2)
probes.append((bps[-1] if bps else 0.0)+1.0)
seq=[]
for lam in sorted(set(probes)):
u=argmax_set(lam); S=frozenset(v for v in range(n) if u>>v&1)
if not seq or S!=seq[-1]: seq.append(S)
return sorted(set(seq),key=len)
def rand_hg(rng,n,m):
import math as _m
kmax=min(4,n)
avail=sum(_m.comb(n,k) for k in range(2,kmax+1)) # never request more edges than exist
m=min(m,avail); E=set(); guard=0
while len(E)<m and guard<200*m+1000:
guard+=1
k=int(rng.integers(2,min(5,n+1))); E.add(tuple(sorted(int(x) for x in rng.choice(n,k,replace=False))))
E=sorted(E); return E, rng.uniform(0.4,2.5,len(E))
if __name__=="__main__":
rng=np.random.default_rng(5); ok=0; bad=0; tot=0
for trial in range(150):
n=int(rng.integers(4,11)); m=int(rng.integers(2,min(14,2**n)))
E,w=rand_hg(rng,n,m); st={"flows":0,"ops":0}
a=sequence(n,E,w,st); b=brute(n,E,w)
tot+=1
if set(a)==set(b): ok+=1
else:
bad+=1
if bad<=3: print(" MISMATCH n=%d m=%d\n flow %s\n brute %s"%(n,m,[sorted(x) for x in a],[sorted(x) for x in b]))
print(" certification: %d/%d instances match brute force exactly"%(ok,tot))
|