#C7.txt
Help7:=proc(): print(`PC1(T), PC(T), AntiPC(P) `): end:
WT:={{1,4},{2,4},{3,4},{4,5},{5,6}};

#PC1(T): one step in the Pruffer code algorithm. Looks for the smallest leaf
#outputs the pair [a,T1] where a is the LABEL of the (only) neighboor of the smallest leaf
#and T1 is the smaller tree where the only edge incident that leaf is removed
PC1:=proc(T) local e,V,N,v,L,a:
V:={seq(op(e),e in T)}:
for v in V do
 N[v]:={}:
od:

for e in T do
N[e[1]]:=N[e[1]] union {e[2]}:
N[e[2]]:=N[e[2]] union {e[1]}:
od:
L:={}:
for v in V do
 if nops(N[v])=1 then
   L:=L union {v}:
 fi:
od:
a:=min(L):
[N[a][1],T minus { {a,N[a][1] }} ]:
end:

PC:=proc(T) local n,P,i,T1,nick:
n:=nops(T)+1:
T1:=T:
P:=[]:
for i from 1 to n-2 do
 nick:=PC1(T1):
 P:=[op(P),nick[1]]:
 T1:=nick[2]:
od:
P:
end:

#Added after class (based on Nick Belov's idea and top of p. 49 of Robin Wilson's book)
#AntiPC(P): inputs a list of length n-2 with entries from {1, ...,n} outputs the tree with
#labels {1, ...,n} whose Pruffer code is P
AntiPC:=proc(P) local n,V,i,P1,b1,E:
n:=nops(P)+2:
V:={seq(i,i=1..n)}:
P1:=P:
E:={}:

while P1<>[] do
b1:=min (V minus convert(P1,set)):
E:=E union {{P1[1],b1}}:
P1:=[op(2..nops(P1),P1)]:
V:=V minus {b1}:
od:

E union {V}:


end: