#Help with Joyal's bijection
Help23j:=proc(): print(` GrabCycle(S,T), LtoC(L), CtoL(C), FindCycle(f,i) , RandF(n), CanC(C) , Joyal(f), RandTree(n) `): end:

#Help with Pruffer's bijection
Help23p:=proc(): print(` Neis(G,v), Leaves(G), Pruffer(T) , mex(S) ), InvPruffer(C) `): end:

#RandF(n): A random function {1,..n}->{1,..n}
RandF:=proc(n) local ra,i:
ra:=rand(1..n):
[seq(ra(),i=1..n)]:
end:

#GrabCycle(S,T): Given a set S of vertices and a table T grabs a cycle that belongs to the first element of S
GrabCycle:=proc(S,T) local s,cu,ne,C:
s:=S[1]:
C:=[]:
cu:=s:
ne:=T[cu]:

if ne=s then
RETURN([s]):
fi:

while ne<>s do
C:=[op(C),cu]:
 ne:=T[cu]:
cu:=ne:
od:

C:

end:




#LtoC(L): Given a permutation of an arbitary set of positive integers in one-line notation
#converts it to a collection of cycles. Try:
#LtoC([6,1,4,5]);
LtoC:=proc(L)  local T,L1,C,S,C1,i:
L1:=sort(L):

for i from 1 to nops(L) do
T[L1[i]]:=L[i]:
od:

#S  is the vertices yet to be visited
S:={op(L)}:

#C is the set of cycles

C:={}:

while S<>{} do
 C1:=GrabCycle(S,op(T)):
 C:=C union {C1}:
 S:=S minus {op(C1)}:
od:

C:

end:


#CtoL(C): Given a collection of cycles, converts it to one line notation
CtoL:=proc(C) local j,C1,S, T,i:

S:=[]:
for C1 in C do
 for j from 1 to nops(C1)-1 do
 T[C1[j]]:=C1[j+1]:
 od:
T[C1[nops(C1)]]:=C1[1]:
S:=[op(S),op(C1)]:
od:
S:=sort(S):
[seq(T[S[i]],i=1..nops(S))]:
end:




#CanC(C): The canonical form of the cycle C
CanC:=proc(C) local s,i:
s:=min(op(C)):

for i from 1 to nops(C) while C[i]<>s do od:
[op(i..nops(C),C),op(1..i-1,C)]:
end:

#FindCycle(f,i): inputa a function f from {1, ...n} to {1,...,n} and a vertex i , 1<=i<=n output
#the cycle it leads to, and where it hits it. Try:
#FindCycle([1,2,2,2,3],3);
FindCycle:=proc(f,i) local n,cu,ne,C,j:
n:=nops(f):
if not 1<=i and i<=n then
 RETURN(FAIL):
fi:

cu:=i:

C:=[]:

while not member(cu,C) do
 C:=[op(C),cu]:
 ne:=f[cu]:
 cu:=ne:
od:

C:=[op(C),ne]:

for j from 1 to nops(C) while C[j]<>C[nops(C)] do od:
CanC([op(j+1..nops(C),C)]),C[nops(C)]:
end:


#Joyal(f): The joyal mapping. Inputs a function f from {1,..,n} to {1, ..n} outputs
# a doubly-rooted tree
Joyal:=proc(f) local n,C,i,L,C1,AllEdges,CycleEdges, OtherEdges:

n:=nops(f):

#C is the set of all cycles
C:={seq(FindCycle(f,i)[1],i=1..n)}:


#AllEdges is the set of all (n of them) edges in the graph of f (but making them undirected)
AllEdges:={seq({i,f[i]},i=1..n)}:

#CycleEdges is the set of all (n of them) edges that participate in the cycles
CycleEdges:={seq(seq({C1[i],C1[i+1]},i=1..nops(C1)-1), C1 in C),seq( {C1[1],C1[nops(C1)]}, C1 in C)}:

#OtherEdges are the edges that will move to the output
OtherEdges:=AllEdges minus CycleEdges:

L:=CtoL(C):

#The output is the tree (represented as a set of edges) followed by the two roots (start and end of skeleton, that may be the same)
OtherEdges union {seq({L[i],L[i+1]},i=1..nops(L)-1)},  [L[1],L[nops(L)] ]:
 
end:


#RandTree(n): A random tree on n vertices using the Joyal bijection. Try:
#RandTree(30);
RandTree:=proc(n) local f:
f:=RandF(n):
Joyal(f)[1]:
end:


#Neis(G,v): given a graph G and a vertex v, find the set of neighbors of v. Try
#Neis({{1,2},{1,3},{1,4}},2);
Neis:=proc(G,v) local e,N:

N:={}:

for e in G do
 if member(v,e) then
 N:=N union e:
 fi:
od:

N minus {v}:

end:


#Leaves(G): The set of leaves of the graph G (i.e. vertices with only one neighbor)
Leaves:=proc(G) local Le,V,v,i:
#V is the set of vertices
V:={seq(op(G[i]),i=1..nops(G))}:

Le:={}:

for v in V do
 if nops(Neis(G,v))=1 then
  Le:=Le union {v}:
 fi:
od:

Le:

end:


#Pruffer(T): inputs a tree T outputs its Pruffer code
Pruffer:=proc(T) local T1,s,f,C:

#If the tree has only one edge (and hence two vertices) the output is the empty list. This is the INITIAL condition
if nops(T)=1 then
 RETURN([]):
fi:

#we build the Pruffer code step by step startint with the empty list
C:=[]:

#T1 is the current tree, that keeps shrinking, we start with the whole tree T
T1:=T:

while nops(T1)>1 do
#s is the smallest leaf
s:=min(op(Leaves(T1))):

#f is the (only) vertex  connected to it
f:=Neis(T1,s)[1]:

#We append f to C
C:=[op(C),f]:

#The new T1 is the smaller tree obtained by deleting s  and the edge connecting s and f
T1:=T1 minus {{s,f}}:
od:
C:
end:

#mex(S): Given a set of positive integers S finds the smallest integer that is NOT in S. For example
#mex({1,2,3,6}) is 4
mex:=proc(S) local i:

for i from 1 while member(i,S) do od:
i:
end:


#InvPruffer(C): Given a list of length n-2 whose entries are drawn from {1, ..., n} outputs the labelled tree on {1, ...,n}
#whose  Pruffer code is C. Try:
#InvPruffer([1,1]);
InvPruffer:=proc(C) local i,n,C1,b,j:
n:=nops(C)+2:

#C1 us the Pruffer code with n appended at the end, making it a list of length n-1
C1:=[op(C),n]:

b[1]:=mex(convert(C1,set)):

for i from 2 to n-1 do
b[i]:=mex({op(i..n-1,C1), seq(b[j],j=1..i-1)}):
od:

{seq({C1[i],b[i]},i=1..n-1)}:

end: