with(combinat):
with(GraphTheory):
#OLD CODE

#LC(p): inputs a rational number between 0 and 1 and outputs true with prob. p
LC:=proc(p) local a,b,ra:
if not (type(p,fraction) and p>=0 and p<=1) then
 RETURN(FAIL):
fi:
a:=numer(p):
b:=denom(p):
ra:=rand(1..b)():
if ra<=a then
 true:
else
 false:
fi:
end:

RG:=proc(n,p) local E,i,j:
E:={}:
for i from 1 to n do
 for j from i+1 to n do
   if LC(p) then
    E:=E union {{i,j}}:
   fi:
 od:
od:
[n,E]:
end:


Cliques := proc(G, k) local n, E, S, i, j, c, C, edge_pair:
n := G[1]:
E := G[2]:
S := {}:
C := choose({seq(i, i=1..n)}, k):
for c in C do
 edge_pair := {};
  for i in c do
   for j in c do
    if i < j then
     edge_pair := edge_pair union {{i,j}}:
    fi:
   od:
  od:
  if edge_pair subset E then
    S := S union {c};
   fi:
 od:
return S;
end:


#END OLD CODE



#3: Write a procedure
#TotClique(G,k)
#that inputs a graph G=[n,E] and a positive integer k, and outputs the #total number of k-cliques and k-anti-cliques.

#first I'm going to make a proc to give the graph complement
#and the edges of a complete graph:

CompleteGraphEdges:=proc(n) local i, j, edges:
edges := {};  
for i from 1 to n-1 do
 for j from i+1 to n do
  edges := edges union {{i, j}}:
 od:
od:
return edges;  
end proc:


Complement:=proc(G) local n, E, nonE, x, y, Cplete, Comp:

n:=G[1]:
E:=G[2]:
Cplete:=[n, CompleteGraphEdges(n)]:
nonE:=convert(convert(Cplete[2], set) minus convert(E, set), set):
Comp:=[n, nonE]:
return(Comp):
end:



TotClique:=proc(G, k) local n, E, verts, subsets, cliques, vertices, anticliques, S, i:

n:=G[1]:
E:=G[2]:
vertices:={seq(i,i=1..n)}:
cliques:=Cliques(G,k):
#print(cliques):
anticliques:=Cliques(Complement(G),k):
#print(anticliques):

#SANITY CHECK
if nops(choose(n,k))= nops(cliques)+nops(anticliques) then
#print(verified);
fi:
[nops(cliques), nops(anticliques)];
end:



#4: Writing a procedure
#CheckRamsey(k,K), that inputs a positive intgeger k and a large #integer K that picks K random graphs (using RG(18,1/2)) and finds the #minimum of ToClique(G,4);


CheckRamsey:=proc(k,K) local mincli,graphlist,totclilist,i, cliquelist,g :
graphlist:=[]:
for i from 1 to K do: 
graphlist:=[op(graphlist),RG(18,1/2)]:
od:
totclilist:=[]:
for g in graphlist do:
totclilist:=[op(totclilist), TotClique(g,4)]:
od:
print(kaylee):
print(min(totclilist));
end:



#5: Write a procedure
#EstimateAverageClique(n,p,k,K)
#that estimates the average number of cliques of size k in a random #graph given by RG(n,p) by picking K of them and averaging.
#What did you get for EstimateAverageClique(10,1/2,4,10000)?


EstimateAverageClique:=proc(n,p,k,K) local i,Numer,graphlist,g, kcliquecounts:

graphlist:=[]:
for i from 1 to K do:
graphlist:=[op(graphlist), RG(n,p)]:
od:

kcliquecounts:=[]:
for g in graphlist do:
kcliquecounts:=[op(kcliquecounts), TotClique(g, k)[1]]:
od:
Numer:=add(op(kcliquecounts)):
return(Numer/K);
end:

#I got EstimateAverageClique(10,1/2, 3, 1000)= 7627/500
#and EstimateAverageClique(10, 1/2, 4, 1000)=3171/1000

#EstimateAverageClique(10,1/2,4,10000)=6563/2000 which is approx 3.3