# Christopher Ross, 3/24/2005

#      PC(E) takes as input E, a set of 2-element sets (set of edges),
# and returns as output a list containing the Pruffer Code.

#      dePC(L) takes as input L, a list that contains the Pruffer Code,
# and returns as output the set of edges.

# Notes: Vertices must be expressed as integers between 1 and V.
# Ex: PC({{4,6},{2,6},{6,5},{5,3},{5,1},{1,7}});
# Ex: dePC([6,5,6,5,1]);

PC:=proc(E)
	local i, j, A, m, S, f, t;

	if(nops(E) < 2) then: return([]); end if:

	m:=1;
	for i from 1 to nops(E) do: m:=max(m,op(E[i])); end do:

	for i from 1 to m do: for j from 1 to m do:
		A[i][j]:=0;
	end do: end do:

	for i from 1 to nops(E) do:
		A[E[i][1]][E[i][2]]:=1;
		A[E[i][2]][E[i][1]]:=1;
	end do:

	S:={}; f:=1; t:=1; i:=``;
	while(sum(A[f][i],i=1..m) <> 1) do: f:=f+1; end do:
	while(A[f][t] <> 1) do: t:=t+1; end do:

	for i from 1 to nops(E) do:
		if((E[i][1] <> f) and (E[i][2] <> f)) then:
			S:= S union {E[i]};
		end if:
	end do:

	return([t, op(PC(S))]);
end proc:

dePC:=proc(L)
	local i, j, m, A, S;

	if(nops(L) = 0) then: return({}); end if:

	S:= {{nops(L)+2, L[nops(L)]}};

	for i from 1 to nops(L)+2 do: A[i]:=0; end do:
	for i from 1 to nops(L) do: A[L[i]]:=A[L[i]]+1; end do:
	for i from 1 to nops(L) do:
		m:=1;
		while(A[m] <> 0) do: m:=m+1; end do:
		S:= S union {{m, L[i]}};
		A[m]:=-1; A[L[i]]:= A[L[i]]-1;
	end do:
	return(S);
end proc: