# OK to post homework
# Matthew Esaia, 2/16/2025, Homework 7

Help:=proc() print(`testAntiPC(), NumberOfLeaves(T), RandomTree(n), EstimateAverageNumberOfLeaves(n,K)`): end:

## PROBLEM 1
# testAntiPC(): tests the AntiPC function by checking PC(AntiPC(P)) = P
testAntiPC:=proc() local P,ra,Test,status,i:
	ra := rand(1..12):
	for i from 1 to 100 do
		P := [seq(ra(), 1..10)]:
		Test := PC(AntiPC(P)):
		status := true:
		if (P <> Test) then
			status := false:
		fi:
	od:
	
	print(status):
end:

## PROBLEM 2
# NumberOfLeaves(T): given a labeled tree finds the number of leaves
NumberOfLeaves:=proc(T) local V,v,e,N,node,leaves:

	V:={seq(op(e),e in T)}:
	for v in V do
		N[v] := 0:
	od:
	
	for e in T do
		N[e[1]] := N[e[1]] + 1:
		N[e[2]] := N[e[2]] + 1:
	od:

	leaves := 0:
	for v in V do
		if N[v] = 1 then
			leaves := leaves + 1:
		fi:
	od:
	leaves:
end:

## PROBLEM 3
# RandomTree(n): Outputs a random labeled tree on {1..n}
RandomTree:=proc(n) local ra,P,T:
	ra := rand(1..n):
	P := [seq(ra(), 1..n-2)]:
	T := AntiPC(P):
end:

## PROBLEM 4
# EstimateAverageNumberOfLeaves(n,K): estimates the average number of leaves in a random
# labeled tree with n vertices
EstimateAverageNumberOfLeaves:=proc(n,K) local sum,i:
	sum := 0:
	for i from 1 to K do
		sum := sum + NumberOfLeaves(RandomTree(n)):
	od:
	
	sum := sum / K:
end:

# EstimateAverageNumberOfLeaves(100,1000) = 37.485
# EstimateAverageNumberOfLeaves(100,10000) = 37.380
# These answers are extremely close, and shows that the average number of leaves
# on a tree with 100 vertices is approximately 37.5


##### FUNCTIONS FROM C7.txt
# 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) neighbor of the smallest leaf
# and T1 is the smaller tree where the only edge incident to 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:
	op(N):
	
	for e in T do
		N[e[1]] := N[e[1]] union {e[2]}:
		N[e[2]] := N[e[2]] union {e[1]}:
	od:
	op(N):
	
	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:

# AntiPC(P): inputs a list of length n - 2 with entries {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:
##### END OF FUNCTIONS