#OK to post homework
#Ramesh Balaji,4/21/2024,hw25

with(combinat):

LD:=proc(p) local i:i:=rand(1..denom(p))(): if i<=numer(p) then true:else false:fi:end:

RHG:=proc(n,p) local i,j,G,pi:
pi:=randperm(n):
G:={seq({pi[i],pi[i+1]},i=1..n-1), {pi[n],pi[1]}}:

for i from 1 to n do
 for j from i+1 to n do
  if LD(p) then
    G:=G union {{i,j}}:
  fi:
 od:
od:
[G, pi]:  
end:

ZKP1:=proc(n,G,pi,Opt) local B1,B2,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:

for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:

if Opt=1 then
 [op(B1),op(B2)]:
else
 {seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}:
fi:
end:

# Part 2:

VerifyOpt1 := proc(n,G,B1,B2):
	for edge in G do:
		edge_list := convert(edge, list);
		left_map := B1[edge[1]];
		right_map := B1[edge[2]];

		if B2[{left_map, right_map}] <> 1 then:
			return false;
		fi:
	od:

	return true;
end:

ZKP1mod:=proc(n,G,pi,Opt) local B1,B2,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:

for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:

if Opt=1 then
 return VerifyOpt1(n,G,B1,B2);
else
 k:={seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}:
 if k = {1} then:
	 return true;
  else:
  	return false;
  end:
fi:
end:


# Part 3:

ZKP:=proc(n,G,pi,K):
	for i from 1 to K do:
		if not ZKP1mod(n,G,pi,rand(1..2)()) then:
			return false;	
		fi
	od:
	return true;
end:

n:=5;
j:=RHG(n,0.2);
G:=j[1];
pi:=j[2];
Bs:=ZKP1(n,G,pi,1);
B1 := Bs[1];
B2 := Bs[2];

VerifyOpt1(n,G,B1,B2);
ZKP(n,G,pi,20);

# Both are returning true