import itertools,json
SLUG='datalog-incremental-state'
def closure(edges):
    r=set()
    while True:
        nxt=set(edges)|{(a,d) for a,b in edges for c,d in r if b==c}
        if nxt==r:return r
        r=nxt
def traversal(edges):
    vertices={x for e in edges for x in e};out=set()
    for start in vertices:
        todo=[b for a,b in edges if a==start];seen=set()
        while todo:
            at=todo.pop()
            if at in seen:continue
            seen.add(at);out.add((start,at));todo.extend(b for a,b in edges if a==at)
    return out
def unary_closure(base):
    current=set(base)
    while True:
        nxt=current|({'q'} if 'p' in current else set())|({'p'} if 'q' in current else set())
        if nxt==current:return current
        current=nxt
def run():
    potential=[(a,b) for a in range(3) for b in range(3) if a!=b]
    graphs=[{e for e,keep in zip(potential,bits) if keep} for bits in itertools.product([False,True],repeat=6)]
    graph_ok=all(closure(g)==traversal(g) for g in graphs)
    deletion_cases=[(g,e) for g in graphs for e in sorted(g)]
    deletion_ok=all(closure(g-{e})==traversal(g-{e}) and closure(g-{e})<=closure(g) for g,e in deletion_cases)
    chain_cases=[(n,k) for n in range(2,33) for k in range(1,n)]
    chain_ok=all(len(closure({(i,i+1) for i in range(n-1)})-closure({(i,i+1) for i in range(n-1) if i!=k-1}))==k*(n-k) for n,k in chain_cases)
    algebra_cases=list(itertools.product(range(-2,3),repeat=4))
    algebra_ok=all((a+da)*(b+db)-a*b==da*b+a*db+da*db for a,b,da,db in algebra_cases)
    naive=unary_closure({'p'})
    # Each existing fact has one recursive support after the sole base p is removed.
    kept={x for x in naive if ('q' if x=='p' else 'p') in naive}
    least=unary_closure(set())
    diamond={('a','b'),('a','c'),('b','d'),('c','d')}
    histories=[diamond,diamond-{('b','d')},diamond-{('b','d'),('c','d')},diamond-{('c','d')}]
    sets=[closure(g) for g in histories];sizes=[len(s) for s in sets]
    expected_sets=[
        {('a','b'),('a','c'),('b','d'),('c','d'),('a','d')},
        {('a','b'),('a','c'),('c','d'),('a','d')},
        {('a','b'),('a','c')},
        {('a','b'),('a','c'),('b','d'),('a','d')},
    ]
    diamond_ok=all(actual==traversal(g)==expected for g,actual,expected in zip(histories,sets,expected_sets))
    expected_changes=[({('b','d')},set()),({('c','d'),('a','d')},set()),(set(),{('b','d'),('a','d')})]
    actual_changes=[(old-new,new-old) for old,new in zip(sets,sets[1:])]
    checks=[dict(name='Fixed point equals independent graph traversal',passed=graph_ok,cases=64,detail='Every three-vertex directed graph without self-edges, including cycles; positive paths.'),dict(name='Single-edge deletions preserve reference equivalence',passed=deletion_ok,cases=len(deletion_cases),detail='Exact pair sets compared after every present-edge deletion.'),dict(name='Chain output-retraction formula',passed=chain_ok,cases=len(chain_cases),detail='n=2..32 and every cut; recomputation compared with k(n-k).'),dict(name='Bilinear delta including simultaneous-change term',passed=algebra_ok,cases=len(algebra_cases),detail='All signed integer a,b,da,db in -2..2.'),dict(name='Naive recursive support is a nonleast fixed point',passed=kept=={'p','q'} and least==set() and kept!=least,cases=1,detail='After removing only extensional support, mutual recursive support incorrectly survives.'),dict(name='Diamond retains alternative derivation',passed=diamond_ok and sizes==[5,4,2,4],cases=4,detail='Every completed pair set equals independent traversal and an explicitly listed oracle.'),dict(name='Diamond change sets match lost and restored support',passed=actual_changes==expected_changes,cases=3,detail='Exact removed and added pair sets across all three updates; cardinality agreement alone cannot pass.')]
    ns=list(range(2,33,2))
    return dict(slug=SLUG,checks=checks,figures=[dict(id='diamond-history',title='Completed reachability through a diamond update history',x_label='Committed update step',y_label='Reachable ordered pairs',series=[dict(name='Positive set closure',x=[0,1,2,3],y=sizes)],caption='Start with diamond; delete b-to-d, delete c-to-d, then reinsert b-to-d. Sizes are 5, 4, 2, 4.',assumptions=['Set semantics','Positive-length paths','Fresh fixed point at every committed version'],kind='Constructed analytical model; not a measured benchmark'),dict(id='chain-retractions',title='Output change from a single central chain-edge deletion',x_label='Chain vertices n',y_label='Reachable ordered pairs',series=[dict(name='Original closure',x=ns,y=[n*(n-1)//2 for n in ns]),dict(name='Retracted cross-cut pairs',x=ns,y=[(n//2)*(n-n//2) for n in ns])],caption='At n=20, one central edge removal retracts 100 of 190 pairs; this counts output, not engine work.',assumptions=['Directed chain','Central cut','Each pair explicitly represented'],kind='Constructed analytical model; not a measured benchmark')],result_summary=dict(diamond_closure_sizes=sizes,chain20_pairs=190,chain20_retracted=100,naive_cycle_retained=sorted(kept),least_after_base_removal=sorted(least)))
if __name__=='__main__':print(json.dumps(run(),indent=2))