Help19:=proc(): print(`CC(G,a), MST1(F, PartT, AvE), MST(G), GenREG(n,r), CCs(G), EP1(G), EP(G)  `): end:
with(combinat):

#CC(G,a): The connected component of vertex a in the graph G=[n,E]
CC:=proc(G,a) local n,E,N,S,S1,i,e,S2,v1:
n:=G[1]:
E:=G[2]:
for i from 1 to n do
 N[i]:={}:
od:
for e in E do
N[e[1]]:=N[e[1]] union {e[2]}:
N[e[2]]:=N[e[2]] union {e[1]}:
od:
S:={a}:
S1:=S union {seq(op(N[v1]),v1 in S)}:
while S<>S1 do
 S2:=S1 union {seq(op(N[v1]),v1 in S1)}:
 S:=S1:
 S1:=S2:
od:
S1:
end:

#MST1(G,PartT,AvE): inputs a weighted graph G=[n,E,DT] and a partial tree PartT and a set of available edges AvE performs one step
#of the Kruskal algorithm
MST1:=proc(G,partT,AvE) local n,E,DT,AvE1,AvE1d,i1,e:
n:=G[1]:
E:=G[2]:
DT:=G[3]:
if partT minus E<>{} or AvE minus E<>{} then
 RETURN(FAIL):
fi:
AvE1:=convert(AvE,list):
AvE1d:=[seq(DT[AvE1[i1]],i1=1..nops(AvE1))]:
e:=AvE1[min[index](AvE1d)]:

if member(e[2],CC([n,partT],e[1])) then
 RETURN(G,partT, AvE minus {e}):
else
 RETURN(G,partT union {e}, AvE minus {e}):
fi:
end:

MST:=proc(G) local n,E,A,i,DT,e:
n:=G[1]:
E:=G[2]:
DT:=G[3]:
if CC([n,E],1)<>{seq(i,i=1..n)} then
 RETURN(FAIL):
fi:
A:=G,{},E:
while nops(A[2])<n-1 and A[3]<>{} do 
A:=MST1(A):od:
[n,A[2]],add(DT[e],e in A[2])
:end:



EP:=proc(G) local n,E,P,E1:
n:=G[1]:
E:=G[2]:
P:=EP1(G):

E1:=E minus {seq({P[i1],P[i1+1]},i1=1..nops(P)-1)}:
if E1={} then
 RETURN(P):
fi:

[P,CCs([n,E1])]:
end:

EP1:=proc(G) local n,E,Nei,e,i,P,cu,st,j,S:
n:=G[1]: E:=G[2]:
#Nei is a table of length n such that N[i] is the set of VERTICES j such that {i,j} belongs to E
for i from 1 to n do
 Nei[i]:={}:
od:
for e in E do
 Nei[e[1]]:=Nei[e[1]] union {e[2]}:
 Nei[e[2]]:=Nei[e[2]] union {e[1]}:
od:
if {seq(nops(Nei[i]) mod 2, i=1..n)}<>{0} then
  RETURN(FAIL):
fi:

st:=1:
cu:=Nei[1][1]:
P:=[1,cu]:
while P[-1]<>1 do
S:=Nei[P[-1]] minus {P[-2]}:
P:=[op(P),S[1]]:
od:
P:
end:


#CCs(G): The set of connected components of the graph G=[n,E]
CCs:=proc(G) local n,i:
n:=G[1]:
{seq(CC(G,i),i=1..n)}:
end:

#GenREG(n,r): generates a random Eulerian graph
GenREG:=proc(n,r) local E,P,i,NE,j:

E:={}:
for i from  1 to r do
P:=randperm(n):
NE:={seq({P[j],P[j+1]},j=1..n-1),{P[n],P[1]}}:
if NE intersect E={} then
E:=E union NE:
fi:
od:
[n,E]:

end:

#C18.txt: March 31, 2025 Graph algithms
Help18:=proc(): print(` RWG(n,p,K), Dij(G,a) , DijP(G,a) `): end:

#RWG(n,p,K): inputs a pos. integer n and outputs a triple [n,E,DT]
#where the vertices are {1,...,n} the edges are of the form {i,j} and
#DT is table such DT[{i,j}] is the weight of the edge {i,j}
RWG:=proc(n,p,K) local G,DT,e,ra,E:
ra:=rand(1..K):

G:=RG(n,p):
E:=G[2]:
for e in E do
DT[e]:=ra():
od:
[n,E,op(DT)]:
end:


#Dij(G,a): inputs a weighted graph G=[n,E,DT] and outputs and a starting 
#vertex a outputs a list L of length n such that L[i] is the MINIMAL DISTANCE
#min. distance
#from a to i. In particular L[a]=0
Dij:=proc(G,a) local n,E,DT,Nei,e,i,Uvis,Tt,T,Vis,cu,Nei1,v,cha,rec,i1:
n:=G[1]:
E:=G[2]:
DT:=G[3]:
#N is a table of length n such that N[i] is the set of VERTICES j such that {i,j} belongs to E
for i from 1 to n do
 Nei[i]:={}:
od:
for e in E do
 Nei[e[1]]:=Nei[e[1]] union {e[2]}:
 Nei[e[2]]:=Nei[e[2]] union {e[1]}:
od:
 
#Uvis is he currently set of still unvisoted vertices
Uvis:={seq(i,i=1..n)}:
#T[i] is the permanent label (the min. distance from a to i
#Tt[i]: is the current best upper bound
for i from 1 to n do
 Tt[i]:=infinity:
od:


T[a]:=0:
Uvis:=Uvis minus {a}:
Vis:=[a]:

while Uvis<>{} do
cu:=Vis[nops(Vis)]:
Nei1:=Nei[cu]:

for v in Nei1 do
if T[cu]+DT[{cu,v}]<Tt[v] then
 Tt[v]:=T[cu]+DT[{cu,v}]:
fi:
od:

cha:=Uvis[1]:
rec:=Tt[cha]:
for i1 from 2 to nops(Uvis) do
  if Tt[Uvis[i1]]<rec then
     cha:=Uvis[i1]:
     rec:=Tt[cha]:
  fi:
od:
T[cha]:=Tt[cha]:
Vis:=[op(Vis), cha]:

Uvis:=Uvis minus {cha}:
od:
[seq(T[i],i=1..n)]:
end:

#DijP(G,a): inputs a weighted graph G=[n,E,DT] and outputs and a starting 
#vertex a outputs a list L of length n such that L[i] is the MINIMAL DISTANCE
#it also returns a list P such that P[i] is the path from a to i that realizes the
#min. distance
#from a to i. In particular L[a]=0
DijP:=proc(G,a) local n,E,DT,Nei,e,i,Uvis,Tt,T,Vis,cu,Nei1,v,cha,rec,i1,Paths, TempPaths:
n:=G[1]:
E:=G[2]:
DT:=G[3]:
#N is a table of length n such that N[i] is the set of VERTICES j such that {i,j} belongs to E
for i from 1 to n do
 Nei[i]:={}:
od:
for e in E do
 Nei[e[1]]:=Nei[e[1]] union {e[2]}:
 Nei[e[2]]:=Nei[e[2]] union {e[1]}:
od:
 
#Uvis is he currently set of still unvisoted vertices
Uvis:={seq(i,i=1..n)}:
#T[i] is the permanent label (the min. distance from a to i
#Tt[i]: is the current best upper bound
for i from 1 to n do
 Tt[i]:=infinity:
od:

Paths[a]:=[a]:

T[a]:=0:
Uvis:=Uvis minus {a}:
Vis:=[a]:

while Uvis<>{} do
cu:=Vis[nops(Vis)]:
Nei1:=Nei[cu]:

for v in Nei1 do
if T[cu]+DT[{cu,v}]<Tt[v] then
 Tt[v]:=T[cu]+DT[{cu,v}]:
 TempPaths[v]:=[op(Paths[cu]),v]:
fi:
od:

cha:=Uvis[1]:
rec:=Tt[cha]:
for i1 from 2 to nops(Uvis) do
  if Tt[Uvis[i1]]<rec then
     cha:=Uvis[i1]:
     rec:=Tt[cha]:
  fi:
od:
T[cha]:=Tt[cha]:
Vis:=[op(Vis), cha]:
Paths[cha]:=TempPaths[cha]:

Uvis:=Uvis minus {cha}:
od:
[seq(T[i],i=1..n)], [seq(Paths[i],i=1..n)]:
end:

#C2.txt: Jan. 27, 2025
Help2:=proc(): print(`LC(p), RG(n,p), `):end:
with(combinat):
#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:
####end from C2.txt