Help23:=proc(): print(`Gens(G), LaGn(G), LabelP(L), RandCen(n,p,K),  LaCen(G,SI)`): end:


#Gens(G): Inputs a directed graph and outputs the list of sets [S1,S2,S3,..] such that S1 are sinks, S2 only go to S1, S3 only go to S1 union S2 etc.
#Try: G:=RDG(10,1/2); Gens(G);
Gens:=proc(G) local n,T,i,j1,j,NYD,AD:
n:=nops(G):

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

T[1]:={}:
for i from 1 to n do
 if G[i]={} then
  T[1]:=T[1] union {i}:
 fi:
od:

NYD:=NYD minus T[1]:
AD:=T[1]:

for j from 2 while NYD<>{} do
 T[j]:={}:
 for i in NYD do
   if G[i] minus AD={} then
     T[j]:=T[j] union {i}:
    fi:
 od:
AD:=AD union T[j]:
NYD:=NYD minus T[j]:
od:

[seq(T[j1],j1=1..j-1)]:

end:

#LaGn(G): A new approach for LaG(G), labelling each vertex as 0 (losing) or 1 (winning)
LaGn:=proc(G) local n,L,j,T,i,s:

n:=nops(G):

L:=Gens(G):

for i in L[1] do
 T[i]:=0:
od:

for j from 2 to nops(L) do
 for i in L[j] do
  if member(0,{seq(T[s], s in G[i])}) then
    T[i]:=1:
  else
   T[i]:=0:
 fi:
 od:
od:

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

end:


#LabelP(L): Given a list of pairs L=[[a[1],b[1]],..., [a[k],b[k]]] picks the i with the largest b[i] and returns [b[i],a[i]]
LabelP:=proc(L) local rec,cha,i:
if L=[] then
 RETURN(FAIL):
fi:

cha:=1:
rec:=L[1][2]:

for i from 2 to nops(L) do
 if L[i][2]>rec then
  cha:=i:
  rec:=L[i][2]:
 fi:
od:

[L[cha][2],L[cha][1]]:

end:



#RandCen(n,p,K): inputs a random directed graph w/o cycles with n vertices and prob. of an edge p and a large integer K outputs the
#graph together with a random assignment of rewards to the sinks. Try:
#RandCen(10,1/2,100);
RandCen:=proc(n,p,K) local G,ra,SI,i:

ra:=rand(1..K):

G:=RDG(n,p):

SI:={}:

for i from 1 to n do
 if G[i]={} then
  SI:=SI union {[i,[ra(),ra()]]}:
fi:
od:
G,SI:

end:


#LaCen(G,SI): Labels a Centepde game G,SI
LaCen:=proc(G,SI) local n,T,L,s,i,j:

n:=nops(G):

L:=Gens(G):

if {seq(s[1], s in SI)}<>L[1] then
 RETURN(FAIL):
fi:

for s in SI do
 T[s[1]]:=s[2]:
od:


for j from 2 to nops(L) do
 for i in L[j] do
    T[i]:=LabelP([seq(T[s],s in G[i])]):
 od:
od:

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

end:

###
#From C22.txt
#C22.txt: April 11, 2022
Help22:=proc(): print(`mex(S), ai(i), aiC(i), RDG(n,p), Parents(G), OneStep0(G,AL,T)  , OneStep1(G,AL,T), OneStep(G,AL,T), LaG(G)    `):
end:

#mex(S): inputs a set of NON-NEGATIVE integers and outputs the smallest
#non-neg. intger NOT in the set S, i.e. min({0,1,2,3,...} minus S)
mex:=proc(S) local i:
for i from 0 while member(i,S) do od:
i:
end:

#ai(i): the a-component in the losing position for Wythoff's game [a_i,i+a_i]
ai:=proc(i) local j:
option remember:
 if i=0 then
   RETURN(0):
else
mex({seq(ai(j),j=0..i-1),seq(ai(j)+j,j=0..i-1)}):
fi:
end:

#aiC(i) : Faster way to compute ai(i) using Wythof's formula trunc(phi*i):
aiC:=proc(i)
trunc((1+sqrt(5))/2*i):
end:

#RDG(n,p): inputs a pos. integer n and a RATIONAL number p=a/b between 0 and 1
#and outputs a random directed graph w/o cycles such tha the prob. of
#an edge is p
RDG:=proc(n,p) local a,b,L,i,j,S,ra:
a:=numer(p):
b:=denom(p):

ra:=rand(1..b):

L:=[]:

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

L:
end:

#Parents(G): inputs a directed graph on {1,...,n} where n:=nops(G) such that G[i] is  the set of children of i (the set of outgoing neihbors)
#outputs the list whose i-th component is the set of "parents" of i, i.e. those j such that i belongs to G[j]. For example
#Parents([{2,3},{3},{}]); should be [{},{1},{1,2}]
Parents:=proc(G) local n,i,j,P:
option remember:
n:=nops(G):

#We initialize all the parents-sets to be empty
for j from 1 to n do
P[j]:={}:
od:

for i from 1 to n do
 for j in G[i] do
  P[j]:=P[j] union {i}:
 od:
od:

#For each vertex i (we look for its children) and append i to the set of parents of each such child

[seq(P[j],j=1..n)]:

end:



#OneStep0(G,AL,T): Given a graph G, with a set of already labelled vertices AL and a table T of lables
#performs one step in the labelling algorithm, the implication that if a vertex is labeled 0 then all its parents are labeled 1
#(since there exists is a legal move that will make the opponent lose)
OneStep0:=proc(G,AL,T) local AL1,n,T1,i,j,P:
AL1:=AL:
n:=nops(G):
P:=Parents(G):
T1:=T:
for i in AL do
 if T1[i]=0 then
  for j in P[i] do
  T1:=[op(1..j-1,T1),1,op(j+1..n,T1)]:
    AL1:=AL1 union {j}:
  od:
 fi:
od:

RETURN(G,AL1,T1):
end:


#OneStep1(G,AL,T): Given a graph G, with a set of already labelled vertices AL and a table T of lables
#performs one step in the labelling algorithm, that if all the children of a vertex are already labeld 1 then
#it is labeled 0 (since whatever the player can do it would be winning for the opponent)
OneStep1:=proc(G,AL,T) local n,T1,i,j:

n:=nops(G):
T1:=T:

 for i from 1 to n do
 if not member(i,AL) then
   if G[i] minus AL={} and {seq(T1[j],j in G[i])}={1} then
  T1:=[op(1..i-1,T1),0,op(i+1..n,T1)]:
     RETURN(G,AL union {i},T1):
   fi:
  fi:
 od:
G,AL,T1:
end:

#OneStep(G,AL,T): Given a graph G, with a set of already labelled vertices AL and a table T of lables
#performs one step in the labelling algorithm, that if all the children of a vertex are already labeld 1 then
#it is labeled 0 (since whatever the player can do it would be winning for the opponent)

OneStep:=proc(G,AL,T) local n,Hope:
n:=nops(G):
if nops(AL)=n then
 RETURN(G,AL,op(T)):
fi:

Hope:=OneStep0(G,AL,T):
if nops(Hope[2])>nops(AL) then
  RETURN(Hope):
fi:


Hope:=OneStep1(G,AL,T):
if nops(Hope[2])>nops(AL) then
  RETURN(Hope):
fi:

FAIL:

end:


#LaG(G)
LaG:=proc(G) local n,i,AL,T,Hope:
n:=nops(G):

T:=[(-1)$n]:

AL:={}:

for i from 1 to n do
 if G[i]={}  then
 T:=[op(1..i-1,T),0,op(i+1..n,T)]:
  AL:=AL union {i}:
 fi:
od:

Hope:=G,AL,T:
while nops(Hope[2])<n do
Hope:=OneStep(Hope):
od:

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