"""Owned Kahn dependency ordering; residual blocked vertices are not all cycle members."""
import json
def kahn(G,reverse_ready=False):
    if any(v not in G for es in G.values() for v in es):raise ValueError('all endpoints must be declared')
    if any(len(es)!=len(set(es)) for es in G.values()):raise ValueError('simple directed graph subset')
    indegree={u:0 for u in G}
    for es in G.values():
        for v in es:indegree[v]+=1
    initial=indegree.copy();ready=[u for u,d in indegree.items() if d==0];order=[];trace=[]
    while ready:
        ready.sort(reverse=reverse_ready);before=ready[:];u=ready.pop(0);order.append(u);updates=[]
        for v in G[u]:
            old=indegree[v];indegree[v]-=1;updates.append({'node':v,'before':old,'after':indegree[v]})
            if indegree[v]==0:ready.append(v)
        trace.append({'ready_before_choice':before,'chosen':u,'indegree_updates':updates})
    residual=[u for u in G if u not in order]
    return {'ready_policy':'descending lexical' if reverse_ready else 'ascending lexical','initial_indegrees':initial,'partial_or_complete_order':order,'trace':trace,'residual_blocked_nodes':residual,'complete_topological_order':len(order)==len(G)}
def valid_order(G,order):
    if len(order)!=len(G) or set(order)!=set(G):return False
    pos={u:i for i,u in enumerate(order)};return all(pos[u]<pos[v] for u,es in G.items() for v in es)
def on_cycle(G,start):
    todo=list(G[start]);seen=set()
    while todo:
        u=todo.pop()
        if u==start:return True
        if u not in seen:seen.add(u);todo.extend(G[u])
    return False
def demo():
    G={'A':['C'],'B':['C','E'],'C':['D'],'D':[],'E':[],'U':[]};asc=kahn(G);desc=kahn(G,True)
    assert valid_order(G,asc['partial_or_complete_order']) and valid_order(G,desc['partial_or_complete_order'])
    assert asc['partial_or_complete_order']==['A','B','C','D','E','U'] and desc['partial_or_complete_order']==['U','B','E','A','C','D']
    cyclic=G|{'D':['B']};blocked=kahn(cyclic);members=[u for u in cyclic if on_cycle(cyclic,u)]
    assert blocked['partial_or_complete_order']==['A','U'] and blocked['residual_blocked_nodes']==['B','C','D','E']
    assert members==['B','C','D'] and not blocked['complete_topological_order']
    assert not valid_order(cyclic,blocked['partial_or_complete_order'])
    return {'edge_convention':'prerequisite -> dependent','authored_DAG':G,'ascending_ready_run':asc,'descending_ready_run':desc,'both_orders_independently_checked_against_every_edge':True,'cycle_added_D_to_B_graph':cyclic,'cyclic_run':blocked,'cycle_members_by_separate_return_reachability_test':members,'blocked_but_not_on_cycle':['E'],'NetworkX_or_task_execution_performed':False}
if __name__=='__main__':print(json.dumps(demo(),indent=2))