"""Owned cyclic unweighted graph, FIFO BFS versus recursive DFS discovery trees."""
from collections import deque
import json
def validate(G,start):
    if start not in G or any(v not in G for es in G.values() for v in es):raise ValueError('known source and destinations')
def bfs(G,start):
    validate(G,start);seen={start};parent={start:None};distance={start:0};queue=deque([start]);order=[];tree=[]
    while queue:
        u=queue.popleft();order.append(u)
        for v in G[u]:
            if v not in seen:
                seen.add(v);parent[v]=u;distance[v]=distance[u]+1;tree.append([u,v]);queue.append(v)
    return {'order':order,'parent':parent,'distance_hops':distance,'discovery_tree_edges':tree}
def dfs(G,start):
    validate(G,start);seen=set();parent={start:None};order=[];tree=[]
    def visit(u):
        seen.add(u);order.append(u)
        for v in G[u]:
            if v not in seen:parent[v]=u;tree.append([u,v]);visit(v)
    visit(start);return {'order':order,'parent':parent,'discovery_tree_edges':tree}
def route(parent,target):
    if target not in parent:return None
    p=[]
    while target is not None:p.append(target);target=parent[target]
    return list(reversed(p))
def all_simple_routes(G,start,target):
    out=[]
    def walk(u,p):
        if u==target:out.append(p);return
        for v in G[u]:
            if v not in p:walk(v,p+[v])
    walk(start,[start]);return out
def demo():
    G={'S':['A','B'],'A':['C'],'B':['T'],'C':['D'],'D':['T','A'],'T':[],'U':[]};b=bfs(G,'S');d=dfs(G,'S');br=route(b['parent'],'T');dr=route(d['parent'],'T');oracle=all_simple_routes(G,'S','T');reverse=dfs({u:list(reversed(es)) for u,es in G.items()},'S')
    assert b['order']==['S','A','B','C','T','D'] and d['order']==['S','A','C','D','T','B']
    assert br==['S','B','T'] and dr==['S','A','C','D','T']
    assert len(br)-1==min(len(p)-1 for p in oracle)==2 and len(dr)-1==4 and route(reverse['parent'],'T')==['S','B','T']
    assert route(b['parent'],'U')is None and route(d['parent'],'U')is None
    assert len(b['order'])==len(set(b['order']))==6 and len(d['order'])==len(set(d['order']))==6
    assert len(b['discovery_tree_edges'])==len(d['discovery_tree_edges'])==5 and sum(map(len,G.values()))==7
    return {'authored_directed_unweighted_graph':G,'neighbor_order':'as listed; mark on discovery, BFS enqueue/DFS function entry','BFS':b,'DFS':d,'BFS_target_route':br,'DFS_first_discovery_target_route':dr,'independent_all_simple_target_routes':oracle,'DFS_reversed_neighbor_lists':reverse,'DFS_reversed_target_route':route(reverse['parent'],'T'),'total_graph_edges':7,'each_discovery_tree_edges':5,'isolated_U_routes':[route(b['parent'],'U'),route(d['parent'],'U')],'NetworkX_or_live_network_executed':False}
if __name__=='__main__':print(json.dumps(demo(),indent=2))