#Maple package for Lecture 19

Help19:=proc(): print(`  Help19kn(), Help19gra(), Help19col(), Help19ham() , `): end:

Help19kn:=proc(): print(`  RandSet(K,n) , KS(S,k), KSint(S,k),KSnum(S,k) `): end:

Help19gra:=proc(): print(` LD(L), RG(n,p), CanF(G,n), Kn(n), Pn(n), Cn(n), Vecs(k,n)  `): 
end:

Help19col:=proc(): print(` DelEd(G,e), ConEd(G,e), CrP(G,t), IsGoodC(G,c),  AllGcol(G,k), IsGcol(G,k)`): 

end:

Help19ham:=proc(): print(`  IsHam(G), IsHCy(G,pi), HamC(G)`): end:





with(combinat):



#start Knapsack

#RandSet(K,n): A random set of integers from -K to K with about n elements

RandSet:=proc(K,n) local i,ra:
ra:=rand(1..K):
{seq(ra(),i=1..n)}:
end:


#KS(S,k): The number of subests of S that add-up to 0
KS:=proc(S,k) local x,s:

coeff(mul(1+x^s,s in S),x,k):

end:

#KSint(S,k): The number of subests of S that add-up to 0
KSint:=proc(S,k) local z,s,f,t:

f:=mul(1+z^s,s in S)/z^(k+1):
f:=subs(z=exp(I*t),f)/(2*Pi*I):
int(f*exp(I*t)*I,t=0..2*Pi):
end:

#KSnum(S,k): The number of subests of S that add-up to 0
KSnum:=proc(S,k) local z,s,f,t:

f:=mul(1+z^s,s in S)/z^(k+1):
f:=subs(z=exp(I*t),f)/(2*Pi*I):
evalf(Int(f*exp(I*t)*I,t=0..2*Pi)):
end:

#END Knapsack

###GENERAL GRAPH FUNCTIONS

#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:

#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:



#RG(n,p): A random graph on {1,2,...,n}
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:
  
[{seq(i,i=1..n)}, S]:

end:


#Kn(n): The complete graph on n vertices
Kn:=proc(n) local i,j:
[{seq(i,i=1..n)}, {seq(seq({i,j},j=i+1..n),i=1..n)}]:
end:

#Cn(n): The path graph on n vertices
Cn:=proc(n) local i:
[{seq(i,i=1..n)}, {seq({i,i+1},i=1..n-1)}]:
end:

#Pn(n): The path graph on n vertices
Pn:=proc(n) local i:
[{seq(i,i=1..n)}, {seq({i,i+1},i=1..n-1) , {n,1}}]:
end:

###END GENERAL GRAPH FUNCTIONS


#START k-Coloroing
#DelEd(G,e): Delets the edge e
DelEd:=proc(G,e) :

if not member(e,G[2]) then
 RETURN(FAIL):
fi:

[G[1],G[2] minus {e}]:
end:

#Contracts the edge e in the graph G, identifying its two members
ConEd:=proc(G,e) local i,j:


if not member(e,G[2]) then
 RETURN(FAIL):
fi:

i:=min(e):
j:=max(e):

[subs(j=i,G[1]), subs(j=i,G[2]) minus {{i}}]:


end:


#CrP(G,t): The Chromatic polynomial of the graph G in the variable t

CrP:=proc(G,t)  local e:

if G[2]={} then
 RETURN(t^nops(G[1])):
else
e:=G[2][1]:
CrP(DelEd(G,e),t)-CrP(ConEd(G,e),t):
fi:

end:


#IsGoodC(G,c): Is the coloring c good for the graph G
IsGoodC:=proc(G,c) local e:

for e in G[2] do
 if c[e[1]]=c[e[2]] then
  RETURN(false):
 fi:
od:
true:

end:


#Vecs(k,n): all the vectors of length n with components in {1,...,k}.
Vecs:=proc(k,n) local S,i,v:
if n=0 then
 RETURN({[]}):
fi:
S:=Vecs(k,n-1):
{seq(seq([op(v),i],i=1..k), v in S)}:
end:



#AllGcol(G,k): All the k-colorings of the graph G
AllGcol:=proc(G,k) local S,c,GC:

GC:={}:

S:=Vecs(k,nops(G[1])):

for c in S do
 if IsGoodC(G,c) then
  GC:=GC union {c}:
 fi:
od:
GC:

end:


#IsGcol(G,k): Is G k-colorable
IsGcol:=proc(G,k) local S,c:

S:=Vecs(k,nops(G[1])):


for c in S do
 if IsGoodC(G,c) then
   RETURN(true,c):
 fi:
od:
false:

end:

#End k-Coloroing

#Start Hamiltonian cycle

#IsHCy(G,pi): Given a graph G and a cycle, is that a Hamiltonian cycle for the graph G?
IsHCy:=proc(G,pi) local i:

if convert(pi,set)<>G[1] then
print(`Bad input`):
 RETURN(FAIL):
fi:

evalb({seq({pi[i],pi[i+1]},i=1..nops(pi)-1),{pi[nops(pi)],pi[1]} }  minus G[2]={}):

end:

#IsHam(G): Is the graph G Hamiltonian?
IsHam:=proc(G) local S,pi:

S:=permute(G[1]):

for pi in S do
 if IsHCy(G,pi) then
  RETURN(true,pi):
 fi:
od:

false:

end:


#HamC(G): The set of Hamiltonian paths of G
HamC:=proc(G) local S,pi,Cy:

S:=permute(G[1]):

Cy:={}:
for pi in S do
 if IsHCy(G,pi) then
  Cy:=Cy union {pi}:
 fi:
od:

Cy:

end:


###END  Hamiltionain cycle