import json, math, itertools
KIND="Constructed analytical model; not a measured benchmark"
def fig(i,title,xlabel,ylabel,series,caption,assumptions):
    return dict(id=i,title=title,x_label=xlabel,y_label=ylabel,series=series,caption=caption,assumptions=assumptions,kind=KIND)
def check(name,passed,cases,detail):
    assert passed, name
    return dict(name=name,passed=bool(passed),cases=cases,detail=detail)

def star(n): return [[j for j in range(1,n)] if i==0 else [0] for i in range(n)]
def path(n): return [[j for j in (i-1,i+1) if 0<=j<n] for i in range(n)]
def step(g,front,visited,pull):
    out=set(); probes=0
    if pull:
        for v in range(len(g)):
            if v in visited: continue
            for u in g[v]:
                probes+=1
                if u in front: out.add(v);break
    else:
        for u in front:
            for v in g[u]:
                probes+=1
                if v not in visited:out.add(v)
    return out,probes
def bfs(g,pull):
    seen={0};front={0};distance={0:0};depth=0;work=0
    while front:
        nxt,n=step(g,front,seen,pull);work+=n;depth+=1
        for v in nxt:distance[v]=depth
        seen|=nxt;front=nxt
    return distance,work
def run():
    sizes=[8,16,32,64,128];p=4
    hub_load=[];edge_load=[]
    for n in sizes:
        g=star(n);loads=[sum(len(g[v]) for v in range(n) if v%p==j) for j in range(p)]
        hub_load.append(max(loads));edge_load.append(math.ceil(sum(map(len,g))/p))
    # dense frontier in a clique: every remaining vertex finds one frontier neighbor immediately
    clique=[[j for j in range(32) if j!=i] for i in range(32)]
    fronts=[1,2,4,8,16,24,31];push=[];pull=[]
    for f in fronts:
        fs=set(range(f));push.append(step(clique,fs,fs,False)[1]);pull.append(step(clique,fs,fs,True)[1])
    tests=[]
    graphs=[star(n) for n in range(2,34)]+[path(n) for n in range(2,34)]
    tests.append(check('Push and pull recover identical BFS distances',all(bfs(g,False)[0]==bfs(g,True)[0] for g in graphs),len(graphs),'64 explicit connected graphs, canonical neighbor order.'))
    tests.append(check('Closed-form distances independently validate both traversals',all(bfs(star(n),mode)[0]=={i:(0 if i==0 else 1) for i in range(n)} and bfs(path(n),mode)[0]=={i:i for i in range(n)} for n in range(2,34) for mode in (False,True)),64,'Known star/path distance formulas provide an oracle independent of push-pull agreement.'))
    tests.append(check('Path is a counterexample to unconditional pull',bfs(path(64),True)[1]>bfs(path(64),False)[1],1,'Pull scans undiscovered vertices repeatedly on a high-diameter path.'))
    tests.append(check('Complete-graph single-step probe formulas',all(a==f*31 and b==32-f for f,a,b in zip(fronts,push,pull)),7,'Exact enumeration independently checks frontier degree and early-exit formulas.'))
    tests.append(check('Vertex balance can hide edge imbalance',hub_load[3]==78 and edge_load[3]==32,1,'64-vertex star; four equal vertex-count partitions.'))
    return dict(slug='graph-workload-skew',checks=tests,figures=[fig('partition','The hub survives equal vertex counts','Vertices in star','Maximum directed-edge tasks per worker',[dict(name='Vertex-ID modulo 4 ownership',x=sizes,y=hub_load),dict(name='Ideal edge task balance lower bound',x=sizes,y=edge_load)],'Undirected star represented with two directed adjacency entries per edge. Ideal edge balance omits replication cost.',['Four workers','Unit cost per adjacency entry','No communication or memory contention']),fig('direction','Early exit with a dense frontier in a clique','Frontier vertices out of 32','Adjacency probes in one level',[dict(name='Push',x=fronts,y=push),dict(name='Pull',x=fronts,y=pull)],'Every unvisited clique vertex finds a frontier neighbor immediately because canonical neighbor order begins at vertex zero.',['Exact BFS step semantics','Frontier is vertices 0 through f-1','No frontier-format conversion overhead'])],result_summary=dict(star64_vertex_max=hub_load[3],star64_edge_lower_bound=edge_load[3],star64_average=126/4,star64_imbalance=78/(126/4),path64_push_probes=bfs(path(64),False)[1],path64_pull_probes=bfs(path(64),True)[1],clique32_front16_push=push[4],clique32_front16_pull=pull[4]))

if __name__=="__main__":
    print(json.dumps(run(),indent=2))