"""Critical-path calculation and deterministic unit-task scheduling on three four-node DAGs; not graph-network training, Spark measurement, or Decima reproduction.
Run with Python 3.10+; standard library only. Writes results.json in the current directory.
"""
from functools import lru_cache
import math

graphs = {
    "chain": {"A": [], "B": ["A"], "C": ["B"], "D": ["C"]},
    "diamond": {"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"]},
    "independent": {"A": [], "B": [], "C": [], "D": []},
}

def inspect(parents, workers=2):
    children = {node: [] for node in parents}
    for node, dependencies in parents.items():
        for parent in dependencies:
            children[parent].append(node)
    @lru_cache(None)
    def critical(node):
        return 1 + max((critical(child) for child in children[node]), default=0)
    path = max(critical(node) for node in parents)
    completed, schedule = set(), []
    while len(completed) < len(parents):
        ready = sorted(node for node in parents if node not in completed
                       and set(parents[node]) <= completed)
        chosen = ready[:workers]
        assert chosen
        schedule.append(chosen)
        completed.update(chosen)
    lower_bound = max(math.ceil(len(parents) / workers), path)
    assert len(schedule) >= lower_bound
    assert sum(map(len, schedule)) == len(parents)
    return path, schedule

for name, parents in graphs.items():
    path, schedule = inspect(parents)
    print(f"{name}: work=4 critical_path={path} makespan={len(schedule)} "
          f"schedule={schedule}")

# Extended experiment: deterministic parameter sweep and invariants.
all_graphs=dict(graphs)
all_graphs['barrier']={'A':[],'B':[],'C':[],'D':['A','B','C'],'E':['A','B','C'],'F':['A','B','C']}
sweep=[]
for name,parents in all_graphs.items():
    for workers in [1,2,3,4,6]:
        path,timeline=inspect(parents,workers)
        completed=set()
        for tick in timeline:
            assert len(tick)<=workers
            assert all(set(parents[node])<=completed for node in tick)
            completed.update(tick)
        lower=max(math.ceil(len(parents)/workers),path)
        sweep.append(dict(graph=name,parents=parents,workers=workers,work=len(parents),critical_path=path,
                          lower_bound=lower,makespan=len(timeline),schedule=timeline))
barrier=next(r for r in sweep if r['graph']=='barrier' and r['workers']==2)
assert barrier['lower_bound']==3 and barrier['makespan']==4
# Each three-task layer requires two ticks on two workers; no child can overlap either root tick.
assert math.ceil(3/2)+math.ceil(3/2)==4
data=dict(worker_sweep=sweep)
print('Six-task barrier with two workers: work bound=3, path bound=2, actual optimal makespan=4.')

import json
from pathlib import Path
Path("results.json").write_text(json.dumps(data,indent=2,allow_nan=False)+"\n",encoding="utf-8")