parametric_sequence_flow.py

"""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))