Help13:=proc(): print(` RandDG(n,k),LC(p) , RandG(n,p), Paths(G,u,v,k) , NuPaths(G,u,v,k), GFt(G,v,t) `): end: #LC(p): inputs a rational number p outputs 1 with probability p (and 0 otherwise) #LC is short for "Loaded Coin" LC:=proc(p) local a,b,r: a:=numer(p): b:=denom(p): r:=rand(1..b)(): if r<=a then RETURN(1): else RETURN(0): fi: end: #RandDG(n,k): A random DIRECTED graph (IN CANONICAL FORM) on the set of vertices {1, ..., n} where each vetrex has up to k neighors #It uses the data structure of list where the i-th entry is the set of neigbors of vertex i . #Try: #RandDG(10,4): RandDG:=proc(n,k) local ra,i: ra:=rand(1..n): [seq({seq(ra(),i=1..k)},i=1..n)]: end: #RandG(n,p): inputs a positive integer n and rational positive number between 0 and 1, outputs #a graph (in CANONICAL FORM) where each edge has probability p of being picked. Try: #RandG(20,1/4); RandG:=proc(n,p) local T,i,j,r: #T is as a TABLE where T[i] (ultimately) is the set of neighbors ("friends") of vertex i. #They start out empty for i from 1 to n do T[i]:={}: od: for i from 1 to n do for j from i+1 to n do r:=LC(p): # i and j have to decide whether or not to become friends, they toss a loaded coin with probaility p of deciding #whether to be friends of each other if r=1 then #if the coin comes out YES, j is joined to T[i], and i is joined to T[j] T[i]:=T[i] union {j}: T[j]:=T[j] union {i}: fi: od: od: #We finally convert the table data-structure to a list of sets (our convention for describing graphs) [seq(T[i],i=1..n)]: end: #Paths(G,u,v,k): Inputs a graph G (on {1, ..., nops(G)}), (either directed or undirected) vertices u and v , and #a positive integer k, uses "Dynamical programming" to find the SET of paths , of length k, from u to v. #Try: Paths([{1,2},{2,3},{3,4},{1,2}],3); #We assume that the inputs are valid Paths:=proc(G,u,v,k) local Neighs, PA,nei,PA1,pa1: option remember: #INITIAL CONDITIONS, paths of length 0 are just lists of length 1 if k=0 then if u=v then RETURN({[u]}): else RETURN({}): fi: fi: #Every path from u to v of length k starts with a first step that is towards one of the neighbors of u #so let's find the set of neighbors of u Neighs:=G[u]: #We will dynamically construct all the paths from u to v of length k by #going through all the options for first step #PA is the desired output #We start out PA the empty set PA:={}: for nei in Neighs do #We call the procedure recursively to find the set of paths from a typical neighbor of u, to v of length one less, i.e. k-1 PA1:=Paths(G,nei,v,k-1): #For each of these paths we stick u at the beginning and add these to our desired output PA:=PA union {seq([u,op(pa1)], pa1 in PA1)}: od: PA: end: #NuPaths(G,u,v,k): Inputs a graph G (on {1, ..., nops(G)}), (either directed or undirected) vertices u and v , and #a positive integer k, uses "Dynamical programming" to find the NUMBER of paths , of length k, from u to v. #Try: NuPaths([{1,2},{2,3},{3,4},{1,2}],3); #We assume that the inputs are valid NuPaths:=proc(G,u,v,k) local Neighs,nei: option remember: #INITIAL CONDITIONS, paths of length 0 are just lists of length 1 if k=0 then if u=v then RETURN(1): else RETURN(0): fi: fi: #Every path from u to v of length k starts with a first step that is towards one of the neighbors of u #so let's find the set of neighbors of u Neighs:=G[u]: #The number of paths of length k from u to v is the sum of the number of paths from each neighbor of u to v, of length k-1 add(NuPaths(G,nei,v,k-1),nei in Neighs): end: #GFt(G,v,t): Inputs a graph G in CANONICAL FORM, and a vertex v (a positive inetgers from 1 to n=nops(G)) outputs #the List of rational function in t whose u-th entry is #the rational function whose coefficient of t^k is NuPaths(G,u,v,k). Try: #GFt([{2,3,4},{1,4},{1,2},{1,2,3}],4,t) GFt:=proc(G,v,t) local n,eq,var,X,u,Neighs,eq1,nei: n:=nops(G): #var is the set of desired quantities. The outputs is going to be [X[1], ..., X[n]] after it is SOLVED var:={seq(X[u],u=1..n)}: #We now use the powerful technique of weight-enumerators to set a SYSTEM of equations for these quantities #The weight enumerator according to the weight t^LengthOfPath of all paths from u to v #is t times the sum of the weight enumerators of all path from neighbors of u and if u=v you have to add #1 for the weight of the empty path eq:={}: #Neig is the set of neighbors of u for u from 1 to n do Neighs:=G[u]: if u=v then eq1:=X[u]=1+t*add(X[nei],nei in Neighs): else eq1:=X[u]=t*add(X[nei],nei in Neighs): fi: eq:=eq union {eq1}: od: #We now let Maple solve the linear system of equations var:=solve(eq,var): #we now plug the solution into seq vector of unknowns [X[1], ..., X[n]]: factor(subs(var,[seq(X[u], u=1..n)])): end: