#M18.txt: Maple code for Lecture 18 of Dr. Z.'s Combinatorics class
#
#
Help18:=proc():print(` CF(E,n) , AllGraphs(n) RandGr(n,K) , CC(G,i), CCs(G) , AllConGraphs(n), AllConGraphs(n) `): 
print(`AllGraphsK(n,K) , AllConGraphsK(n,K), NuConG(N), NuConGclever(N)`):
end:

with(combinat):

#CF(E,n): inputs a graph G on {1, ...,n} as a set of edges outputs it in canonical form as a list of
#sets of length n such that G[i] is the set of neighbors of i. Try:
#CF({{1,2},{1,3}},3);
CF:=proc(E,n) local T,i,e:

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

for e in E do
 #For every e={i,j} we include j in the set of neigbors of i and  i in the set of neighbors of j
 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:



#AllGraphs(n): All the (labeled) graphs on {1,...n}
AllGraphs:=proc(n) local S,s,i:
S:=powerset(choose({seq(i,i=1..n)},2)):
{seq(CF(s,n), s in S)}:
end:


#AllGraphsK(n,K): All the (labeled) graphs on {1,...n} with K edges
AllGraphsK:=proc(n,K) local S,s,i:
if not (K>=0 and K<=binomial(n,2)) then
 print(K, `must be between 0 and `, binomila(n,2)):
 RETURN(FAIL):
fi:

S:=choose(choose({seq(i,i=1..n)},2),K):
{seq(CF(s,n), s in S)}:
end:

#RandGr(n,K): a random  (labeled) graph on n vertices and K edges
RandGr:=proc(n,K) local i:
if not (K>=0 and K<=binomial(n,2)) then
 print(K, `must be between 0 and `, binomila(n,2)):
 RETURN(FAIL):
fi:

CF(randcomb(choose({seq(i,i=1..n)},2),K),n):
end:

#CC(G,i): The connected component of vertex i in the graph G
CC:=proc(G,i) local S1,S2,S3,s:

if not (1<=i and i<=nops(G)) then
 print(`bad input`):
 RETURN(FAIL):
fi:

S1:={i}:

S2:=S1 union {seq(op(G[s]), s  in S1)}:

while S1<>S2 do

S3:=S2 union {seq(op(G[s]), s  in S2)}:

S1:=S2:
S2:=S3:
od:
S2:
end:

#CCs(G): Inputs a graph G in canonical form  on {1,...,n} where n=nops(G), outputs the set partition of {1,...,n}
#consisting of its connected components. Try
#CCs([{},{},{}]);
#The set of connected components of G. Inputs the set partition of {1,
CCs:=proc(G) local n,i,StillToDo,ConComps,v:

n:=nops(G):

StillToDo:={seq(i,i=1..n)}:

ConComps:={}:

while StillToDo<>{} do
 v:=StillToDo[1]:
 ConComps:=ConComps union {CC(G,v)}:
 StillToDo:=StillToDo minus CC(G,v):
od:
ConComps:
end:


#AllConGraphs(n): The set of all connected (labeled) graphs on {1,..,n}
AllConGraphs:=proc(n) local S,s,C:
S:=AllGraphs(n):
C:={}:

for s in S do
 if nops(CCs(s))=1 then
  C:=C union {s}:
 fi:
od:

C:
end:


#AllConGraphsK(n,K): The set of all connected (labeled) graphs on {1,..,n} with K edges
AllConGraphsK:=proc(n,K) local S,s,C:
S:=AllGraphsK(n,K):
C:={}:

for s in S do
 if nops(CCs(s))=1 then
  C:=C union {s}:
 fi:
od:

C:
end:

#NuConG(N): The first N terms of the sequence "number of connected (labeled) graphs with n vertices", by BRUTE force
#Try:
#NuConG(5);
NuConG:=proc(N) local n1:
[seq( nops(AllConGraphs(n1)),n1=1..N)]:
end:


#NuConGclever(N): The first N terms of the sequence "number of connected (labeled) graphs with n vertices", done via
#Exonenital Generating functions. Try
#Try:
#NuConGclever(30);
NuConGclever:=proc(N) local f,i,x:
f:=log(add(2^binomial(i,2)*x^i/i!,i=0..N+1)):
f:=taylor(f,x=0,N+1):
[seq(coeff(f,x,i)*i!,i=1..N)]:
end: