#OK to post homework
#Blair Seidler, 2021-04-04 Assignment 19

with(combinat):
with(Statistics):

Help:=proc():
print(`CrPbetter(G,t)`):
end:

# 2.

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

#I should have named this CrPworse, since it performs nowhere near as well as CrP.
#My idea was to pick an edge from some high degree vertex, hoping that the contraction
#would collapse a number of edges. Unfortunately, the amount of computation used vastly
#outpaces any gains the algorithm might have made.

#Leaving it here mostly for comedic effect.

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

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

PickEdge:=proc(G) local m,e,i:
m:=Mode(<seq(op(G[2][i]), i = 1 .. nops(G[2]))>):
if type(m,`set`) then
  m:=trunc(m[1]):
else
  m:=trunc(m):
fi:
for e in G[2] do
  if m in e then
    RETURN(e):
  fi:
od:
end:

# 3.

#PetGr(): Returns the Petersen graph in the format we are using
PetGr:=proc():
RETURN([{1,2,3,4,5,6,7,8,9,10},
{{1,2},{1,5},{1,8},{2,3},{2,6},{3,4},{3,10},{4,5},{4,7},{5,9},{6,7},{6,9},{7,8},{8,10},{9,10}}]):
end:

#CrP(PetGr(),t) gives the chromatic polynomial
#t^10 - 15*t^9 + 105*t^8 - 455*t^7 + 1353*t^6 - 2861*t^5 + 4275*t^4 - 4305*t^3 + 2606*t^2 - 704*t
#Evaluating at t=1000, we get 985104546350143270697605296000 possible 1000-colorings

#The number of k-colorings of the Petersen graph forn k=3..10 is
#120, 12960, 332880, 3868080, 27767880, 144278400, 594347040, 2055598560
#This is sequence A296913 in the OEIS



#### From C19.txt ####

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