function pointer_jump(pt,val) = let npt = pt->pt; nval = {v + nv: v in val; nv in val->pt}; in if eql(npt,pt) then val else pointer_jump(npt,nval) \$ function wyllie_list_rank(pt) = let % set value to 1 everywhere except at the tails % val = {if i==pt then 0 else 1: pt; i in [0:#pt]}; in pointer_jump(pt,val) \$ function euler_tour_from_edges(edges,n) = let e = edges ++ {j,i : i,j in edges}; adj = int_collect({e1,i: e1,e2 in e; i in [0:#e]}); map = flatten({zip(ne,rotate(ne,1)) : i,ne in adj}); perm = dist(0,#e)<-map; in drop(perm,#edges)++take(perm,#edges) \$ function euler_tree_from_edges(edges,n) = let tour = euler_tour_from_edges(edges,n); rank = wyllie_list_rank(rep(tour,#edges,#edges)); rank = {x + 1 : x in rank}; pos = {if a > b then (e2,(b,a)) else (e1,(a,b)) : e1,e2 in edges; a in take(rank,#edges); b in drop(rank,#edges)}; in dist((0,2*n-1),n)<-pos \$ % An example spanning tree 8 1 \ / 9 - 2 - 3 - 4 - 5 / | \ 7 11 - 0 6 - 10 % edges = [(1, 5), (5, 6), (6, 10), (4, 5), (3, 4), (2, 3), (2, 11), (2, 9), (7, 9), (8, 9), (0, 11)]; euler_tree_from_edges(edges,12);