#C19.txt April 3, 2025
Help19:=proc(): print(`CC(G,a), MST1(G, partT, AveE) , MST(G) `):end:

#MST1(G,partT,AvE): inputs a weighted graph G and performs ONE step in the Kruskal
#algoritm by looking at the cheapest member of AvE and trying to join it to
#partT if it does NOT create a cycle, either way we remove it from AvE
MST1:=proc(G,partT,AvE) local n, E,DT,e,AvE1,AvE1d,i1:
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 is the cheapest edge
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:
FAIL:
end:

#MST(G): the minimal spanning tree of the weighted graph G=[n,E,DT]
#and the its cost (the sum of the costs of the edges of the cheapest tree)
MST:=proc(G) local n,E,A,i,DT,e:

n:=G[1]:
E:=G[2]:
DT:=G[3]:
if not CC([n,E],1)={seq(i,i=1..n)} then
 print(`not connected`):
 RETURN(FAIL):
fi:

A:=G,{},E:
while nops(A[2])<n-1 and E<>{}  do
A:=MST1(A):
od:
[n,A[2]], add(DT[e], e in A[2]):
end:

#CC(G,a): inputs a graph G=[n,E] and a vertex a and outputs the set of vertices connected to
#a.For example CC([5,{{1,2},{2,3},{4,5}}],1) is {1,2,3}.
CC:=proc(G,a) local n,E,i,N, e,S,s,S1,S2:
n:=G[1]:
E:=G[2]:
#N[i]: the set of neighbors of vertex i
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}:
#S is a set and we want the set of all the neighbors of S, a typical set of neighbors is N[s]
#and we want the union of all of them
S1:=S union {seq( op(N[s])   , s in S)}:
while S<>S1 do
S2:=S1 union {seq( op(N[s])   , s in S1)}:
S:=S1:
S1:=S2:
od:
S1:
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]:
#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:
 
#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