#Maple package for Lecture 19

Help:=proc(): print(` LD(L), RG(n,p), CanF(G,n) `): end:



#LD(L): Inputs a list of positive integers L (of n:=nops(L) members)
#outputs an integer i from 1 to n with the prob. of i being
#proportional to L[i]
#For example LD([1,2,3]) should output 1 with prob. 1/6
#output 2 with prob. 1/3
#output 3 with prob. 3/6=1/2
LD:=proc(L) local n,i,su,r:
n:=nops(L):
r:=rand(1..convert(L,`+`))():
su:=0:

for i from 1 to n do
 su:=su+L[i]:
  if r<=su then
    RETURN(i):
  fi:
od:
end:

#RG(n,p): A random graph on n vertices
RG:=proc(n,p) local a,b,S,i,j:

a:=numer(p):
b:=denom(p)-a:
S:={}:

for i from 1 to n do
 for j from i+1 to n do
   if LD([a,b])=1 then
    S:=S union {{i,j}}:
   fi:
 od:
od:
  
S:

end:

#CanF(G,n): The canonical form of the graph G on n vertices
CanF:=proc(G,n) local T,e,i:

for i from 1 to n do
 T[i]:={}:
od:

for e in G do
 T[e[1]]:= T[e[1]] union {e[2]}:
 T[e[2]]:= T[e[2]] union {e[1]}:
od:

[seq(T[i],i=1..n)]:
end: