#!/usr/bin/env python3
"""Linked partition refinement, LexBFS, PEO and clique-tree certificates.
Only the Python standard library. Core algorithms take a prepared simple
undirected adjacency list. Unordered edge ingestion uses a separate hash check.
"""
import sys
sys.dont_write_bytecode=True
from collections import deque
from itertools import combinations
from pathlib import Path
from random import Random
import json

def require(ok,msg):
    if not ok:raise ValueError(msg)
def check(ok,msg):
    if not ok:raise AssertionError(msg)

class Block:
    __slots__=('prev','next','head','tail','size','epoch','target')
    def __init__(self):
        self.prev=self.next=None
        self.head=self.tail=-1
        self.size=0
        self.epoch=-1
        self.target=None

class OrderedPartition:
    """Block order matters; order inside a block is an explicit tie convention.
    refine consumes an iterable of active element IDs; duplicates are ignored.
    New intersection members follow their first occurrence in this iterable.
    Core memory has n element records and O(n) current/temporary block objects.
    """
    def __init__(self,n):
        require(type(n) is int and n>=0,'universe size')
        self.n=n
        self.prev=[i-1 for i in range(n)]
        self.next=[i+1 for i in range(n)]
        if n:self.next[-1]=-1
        self.owner=[None]*n
        self.mark=[-1]*n
        self.epoch=0
        self.root=Block()
        self.root.prev=self.root.next=self.root
        self.moves=0
        self.refinements=0
        if n:
            b=Block();b.head=0;b.tail=n-1;b.size=n
            self._before(self.root,b)
            self.owner=[b]*n
    def _before(self,old,new):
        new.prev=old.prev;new.next=old
        old.prev.next=new;old.prev=new
    def _unlink_block(self,b):
        b.prev.next=b.next;b.next.prev=b.prev
        b.prev=b.next=None
        b.target=None
    def _detach_element(self,v,b):
        p,q=self.prev[v],self.next[v]
        if p<0:b.head=q
        else:self.next[p]=q
        if q<0:b.tail=p
        else:self.prev[q]=p
        self.prev[v]=self.next[v]=-1
        b.size-=1
    def _append(self,v,b):
        self.prev[v]=b.tail;self.next[v]=-1
        if b.tail<0:b.head=v
        else:self.next[b.tail]=v
        b.tail=v;b.size+=1;self.owner[v]=b
    def refine(self,items):
        # Valid active IDs are a precondition of the mutating core. A malformed
        # iterable raises immediately; no transactional rollback is promised.
        self.epoch+=1;self.refinements+=1
        epoch=self.epoch;touched=[]
        for v in items:
            require(type(v) is int and 0<=v<self.n and self.owner[v] is not None,'active refinement member')
            if self.mark[v]==epoch:continue
            self.mark[v]=epoch
            old=self.owner[v]
            if old.epoch!=epoch:
                new=Block();self._before(old,new)
                old.epoch=epoch;old.target=new;touched.append(old)
            new=old.target
            self._detach_element(v,old);self._append(v,new);self.moves+=1
        for old in touched:
            old.target=None
            if old.size==0:self._unlink_block(old)
    def pop_first(self):
        if self.root.next is self.root:raise IndexError('empty partition')
        b=self.root.next;v=b.head
        self._detach_element(v,b);self.owner[v]=None
        if b.size==0:self._unlink_block(b)
        return v
    def snapshot(self):
        out=[];b=self.root.next
        while b is not self.root:
            row=[];v=b.head
            while v>=0:row.append(v);v=self.next[v]
            out.append(row);b=b.next
        return out
    def audit(self):
        seen=set();b=self.root.next;previous=self.root;blocks=0
        while b is not self.root:
            check(b.prev is previous and b.size>0,'block links/nonempty')
            v=b.head;p=-1;count=0
            while v>=0:
                check(v not in seen and self.owner[v] is b and self.prev[v]==p,'element identity/link')
                seen.add(v);count+=1;p=v;v=self.next[v]
            check(count==b.size and p==b.tail,'tail and count')
            check(b.target is None,'temporary targets cleared')
            previous=b;b=b.next;blocks+=1
        check(self.root.prev is previous,'last block')
        check(seen=={v for v in range(self.n) if self.owner[v] is not None},'owner coverage')
        check(blocks<=len(seen),'current block memory')
        return blocks

def prepare_graph(n,edges):
    require(type(n) is int and n>=0,'vertex count')
    seen=set();adj=[[] for _ in range(n)]
    for edge in edges:
        require(len(edge)==2 and all(type(v) is int and 0<=v<n for v in edge),'endpoints')
        u,v=edge
        require(u!=v,'no loops')
        key=(min(u,v),max(u,v))
        require(key not in seen,'no parallel edges')
        seen.add(key);adj[u].append(v);adj[v].append(u)
    return adj

def lexbfs(adj,record_trace=False):
    n=len(adj);part=OrderedPartition(n);order=[];trace=[]
    for step in range(n):
        if record_trace:before=part.snapshot()
        v=part.pop_first();order.append(v)
        # Iterable scans each adjacency record, without building global labels.
        part.refine(u for u in adj[v] if part.owner[u] is not None)
        if record_trace:trace.append({'pick':v,'before':before,'after':part.snapshot()})
    return {'order':order,'trace':trace,'moved_elements':part.moves,'refinement_calls':part.refinements}

def verify_peo(adj,order):
    n=len(adj)
    require(len(order)==n,'permutation length')
    seen=[False]*n
    for v in order:
        require(type(v) is int and 0<=v<n and not seen[v],'permutation identity')
        seen[v]=True
    pos=[0]*n
    for i,v in enumerate(order):pos[v]=i
    later=[[] for _ in range(n)];groups=[[] for _ in range(n)];parent=[-1]*n
    for v in range(n):
        later[v]=[u for u in adj[v] if pos[u]>pos[v]]
        if later[v]:
            p=min(later[v],key=lambda u:pos[u]);parent[v]=p;groups[p].append(v)
    mark=[-1]*n;checks=0
    for p in range(n):
        for u in adj[p]:mark[u]=p
        for v in groups[p]:
            for u in later[v]:
                if u!=p:
                    checks+=1
                    if mark[u]!=p:return {'valid':False,'witness':[v,p,u],'later':later,'parent':parent,'membership_checks':checks}
    return {'valid':True,'witness':None,'later':later,'parent':parent,'membership_checks':checks}

def color_and_maximum_clique(adj,peo):
    proof=verify_peo(adj,peo)
    require(proof['valid'],'valid PEO required')
    n=len(adj);color=[-1]*n;mark=[-1]*(n+1);largest=[]
    for v in reversed(peo):
        for u in adj[v]:
            if color[u]>=0:mark[color[u]]=v
        c=0
        while mark[c]==v:c+=1
        color[v]=c
        bag=[v]+proof['later'][v]
        if len(bag)>len(largest):largest=bag
    return {'color':color,'color_count':max(color,default=-1)+1,'maximum_clique':largest}

def maximal_cliques(adj,peo):
    proof=verify_peo(adj,peo)
    require(proof['valid'],'valid PEO required')
    n=len(adj);candidates=[[v]+proof['later'][v] for v in peo]
    # Dense Boolean rows make the stated cubic bound independent of set hashing.
    rows=[[False]*n for _ in range(n)]
    for i,C in enumerate(candidates):
        for v in C:rows[i][v]=True
    keep=[]
    for i,C in enumerate(candidates):
        contained=False
        for j,D in enumerate(candidates):
            if len(C)<len(D) and all(rows[j][v] for v in C):contained=True;break
        if not contained:keep.append(sorted(C))
    check(len({tuple(C) for C in keep})==len(keep),'PEO bags are distinct')
    return keep

def clique_tree(adj,peo):
    cliques=maximal_cliques(adj,peo);n=len(adj);k=len(cliques)
    if not k:return {'cliques':[],'edges':[],'weight':0,'upper_bound':0}
    contain=[[False]*n for _ in range(k)]
    for i,C in enumerate(cliques):
        for v in C:contain[i][v]=True
    weight=[[0]*k for _ in range(k)]
    for i in range(k):
        for j in range(i):
            weight[i][j]=weight[j][i]=sum(contain[j][v] for v in cliques[i])
    # Complete weighted clique graph, including zero edges between components.
    in_tree=[False]*k;best=[-1]*k;parent=[-1]*k;best[0]=0;edges=[]
    for _ in range(k):
        u=max((i for i in range(k) if not in_tree[i]),key=lambda i:(best[i],-i))
        in_tree[u]=True
        if parent[u]>=0:edges.append((parent[u],u,weight[parent[u]][u]))
        for v in range(k):
            if not in_tree[v] and weight[u][v]>best[v]:best[v]=weight[u][v];parent[v]=u
    total=sum(w for _,_,w in edges);upper=sum(map(len,cliques))-n
    return {'cliques':cliques,'edges':[list(e) for e in edges],'weight':total,'upper_bound':upper}

def verify_clique_tree(adj,record):
    n=len(adj);C=record['cliques'];k=len(C)
    if n==0:return C==[] and record['edges']==[] and record['weight']==0 and record['upper_bound']==0
    if not C or len(record['edges'])!=k-1:return False
    neighborhoods=[set(row) for row in adj]
    for bag in C:
        if not bag or len(set(bag))!=len(bag) or any(type(v) is not int or not(0<=v<n) for v in bag):return False
        if any(v not in neighborhoods[u] for u,v in combinations(bag,2)):return False
        if any(all(v in neighborhoods[u] for u in bag) for v in range(n) if v not in bag):return False
    if len({tuple(sorted(bag)) for bag in C})!=k:return False
    tree=[[] for _ in C]
    for i,j,w in record['edges']:
        if not(0<=i<k and 0<=j<k) or i==j or w!=len(set(C[i])&set(C[j])):return False
        tree[i].append(j);tree[j].append(i)
    reached={0};stack=[0]
    while stack:
        for j in tree[stack.pop()]:
            if j not in reached:reached.add(j);stack.append(j)
    if len(reached)!=k:return False
    if record['weight']!=sum(w for _,_,w in record['edges']) or record['upper_bound']!=sum(map(len,C))-n or record['weight']!=record['upper_bound']:return False
    for v in range(n):
        ids={i for i,bag in enumerate(C) if v in bag}
        if not ids:return False
        seen={next(iter(ids))};stack=list(seen)
        while stack:
            for j in tree[stack.pop()]:
                if j in ids and j not in seen:seen.add(j);stack.append(j)
        if seen!=ids:return False
    if any(not any(u in bag and v in bag for bag in C) for u in range(n) for v in adj[u]):return False
    return True

def find_hole(adj):
    """Slow optional negative certificate: each v / nonadjacent neighbor pair,
    BFS avoiding other neighbors of v. O(n^3(n+m)) conservative RAM bound.
    """
    n=len(adj);neighbor=[set(row) for row in adj]
    for v in range(n):
        for x,y in combinations(adj[v],2):
            if y in neighbor[x]:continue
            forbidden=neighbor[v]-{x,y};forbidden.add(v)
            parent={x:None};q=deque([x])
            while q and y not in parent:
                u=q.popleft()
                for z in adj[u]:
                    if z not in forbidden and z not in parent:parent[z]=u;q.append(z)
            if y in parent:
                path=[];u=y
                while u is not None:path.append(u);u=parent[u]
                return [v]+path[::-1]
    return None

def is_hole(adj,cycle):
    if cycle is None or len(cycle)<4 or len(set(cycle))!=len(cycle):return False
    if any(type(v) is not int or not 0<=v<len(adj) for v in cycle):return False
    E=[set(row) for row in adj];k=len(cycle)
    for i,u in enumerate(cycle):
        for j in range(i+1,k):
            expected=j==i+1 or(i==0 and j==k-1)
            if ((cycle[j] in E[u])!=expected):return False
    return True

def recognize(adj,record_trace=False,negative_certificate=False):
    traversal=lexbfs(adj,record_trace);peo=traversal['order'][::-1];proof=verify_peo(adj,peo)
    out={'chordal':proof['valid'],'search':traversal,'peo':peo,'violation':proof['witness']}
    if proof['valid']:
        out.update(color_and_maximum_clique(adj,peo));out['clique_tree']=clique_tree(adj,peo)
    elif negative_certificate:
        out['hole']=find_hole(adj);check(is_hole(adj,out['hole']),'negative certificate')
    return out

# Slow and structurally different test oracles.
def oracle_lex_label_max(adj,order):
    n=len(adj);labels=[[] for _ in range(n)];remaining=set(range(n))
    for i,v in enumerate(order):
        check(v in remaining and labels[v]==max(labels[u] for u in remaining),'lex label maximality')
        remaining.remove(v)
        for u in adj[v]:
            if u in remaining:labels[u].append(n-i)

def oracle_peo(adj):
    E=[set(row) for row in adj];left=set(range(len(adj)));out=[]
    while left:
        candidate=next((v for v in sorted(left) if all(y in E[x] for x,y in combinations(E[v]&left,2))),None)
        if candidate is None:return None
        left.remove(candidate);out.append(candidate)
    return out

def oracle_maximal_cliques(adj):
    n=len(adj);E=[set(row) for row in adj];out=[]
    for mask in range(1,1<<n):
        C=[v for v in range(n) if mask>>v&1]
        if all(v in E[u] for u,v in combinations(C,2)) and not any(all(v in E[u] for u in C) for v in range(n) if not(mask>>v&1)):
            out.append(tuple(C))
    return sorted(out)

def main():
    rng=Random(8102026);operations=0
    for _ in range(600):
        n=rng.randrange(0,30);part=OrderedPartition(n);naive=[list(range(n))] if n else []
        for step in range(70):
            active=[v for row in naive for v in row]
            if active and rng.random()<.25:
                expected=naive[0].pop(0)
                if not naive[0]:naive.pop(0)
                check(part.pop_first()==expected,'linked first pop')
            else:
                chosen=[rng.choice(active) for j in range(rng.randrange(0,2*len(active)+1))] if active else []
                selected=set(chosen);first=list(dict.fromkeys(chosen));new=[]
                for row in naive:
                    rowset=set(row);front=[v for v in first if v in rowset];back=[v for v in row if v not in selected]
                    if front:new.append(front)
                    if back:new.append(back)
                naive=new;part.refine(chosen)
            check(part.snapshot()==naive,'ordered partition transition');part.audit();operations+=1
    graphs=chordal=nonchordal=holes=0
    for n in range(7):
        E=list(combinations(range(n),2))
        # All labelled graphs through n=5; 3500 distinct masks at n=6.
        masks=range(1<<len(E)) if n<=5 else rng.sample(range(1<<len(E)),3500)
        for mask in masks:
            edges=[e for i,e in enumerate(E) if mask>>i&1];adj=prepare_graph(n,edges)
            out=recognize(adj,negative_certificate=True);oracle=oracle_peo(adj)
            check(out['chordal']==(oracle is not None),'LexBFS vs simplicial peeling')
            oracle_lex_label_max(adj,out['search']['order'])
            check(out['search']['moved_elements']==len(edges),'each edge updates its later selected endpoint once')
            if out['chordal']:
                chordal+=1
                maximal=oracle_maximal_cliques(adj)
                check(sorted(map(tuple,out['clique_tree']['cliques']))==maximal,'all and only maximal cliques')
                check(verify_clique_tree(adj,out['clique_tree']),'running intersection/cover/maximal')
                check(out['clique_tree']['weight']==out['clique_tree']['upper_bound'],'maximum-weight equality')
                check(out['color_count']==len(out['maximum_clique'])==max(map(len,maximal),default=0),'matching upper/lower color certificate')
                check(all(out['color'][u]!=out['color'][v] for u,v in edges),'proper color')
            else:
                nonchordal+=1;check(is_hole(adj,out['hole']),'induced cycle witness');holes+=1
            graphs+=1
    edges=[(0,1),(0,2),(1,2),(2,3),(0,4),(1,4),(4,5)]
    example=recognize(prepare_graph(6,edges),record_trace=True,negative_certificate=True)
    counter=recognize(prepare_graph(4,[(0,1),(1,2),(2,3),(3,0)]),record_trace=True,negative_certificate=True)
    # A bad arbitrary order is not a nonchordality certificate.
    path=prepare_graph(3,[(0,1),(1,2)])
    check(not verify_peo(path,[1,0,2])['valid'] and recognize(path)['chordal'],'arbitrary-order fallacy')
    record={'status':'PASS','partition_state_transitions':operations,'graph_instances':graphs,'chordal_instances':chordal,'nonchordal_instances':nonchordal,'verified_holes':holes,'examples':{'six_vertex':example,'chordless_square':counter},'scope':'Exact finite exhaustive oracles and deterministic replay. Core search linear on prepared adjacency; full trace, cubic clique-tree builder and optional slow hole extraction separately costed.'}
    output=Path(__file__).with_name('algorithms-chordal-certificates-results.json');output.write_text(json.dumps(record,ensure_ascii=False,indent=2)+'\n');print(json.dumps(record,ensure_ascii=False,indent=2))

if __name__=='__main__':main()