I wanna simulate a Galton-Watson Tree to a maximum of n generation given a reproduction law P. I use Maple but I am unable to create the edges of the tree whenever there are more than two vertices in the tree. I think that the problem is that I am unable to store the number of children that each node has. Here is the code:
I use the law below to test, but I believe it should work with any discrete law on posint. P:=RandomVariable(EmpiricalDistribution(Array([0,1,2]))):
Then the procedure to generate the tree is
GWT:=proc(n,P) #Renvoie un Arbre de Galton-Watson avec au plus n génération sous loi P; local G,g,p,s,N,k; if n=0 then G:=Graph(1); else g:=GWT(n-1,P); p:=Sample(P,1); G:=DisjointUnion(Graph(1),``(g,p[1])); if p[1]=1 then s=0; else s:=((p[1])^n-1)/(p[1]-1); fi; N:=nops(Vertices(G)); G:=RelabelVertices(G,[seq(k,k=1..N)]); if p[1]>0 then G:=AddEdge(G,{seq({1, 2+k*s},k = 0 .. p[1]-1)}); fi; G; fi; end proc;
Just to compare, I was able to code the construction of a m-ary tree up to n generation, given n and m with a pretty similar code:
Arbre:=proc(n,m) # m-ary arbre à n génération local k,T,t,s,N; if n=0 then T:=Graph(1); else t:=Arbre(n-1,m); T:=DisjointUnion(Graph(1),``(t,m)); if m=1 then s:=0; else s:=(m^n-1)/(m-1); fi; N:=nops(Vertices(T)); T:=RelabelVertices(T,[seq(k,k=1..N)]); T:=AddEdge(T,{seq({1, 2+k*s},k = 0 .. m-1)}); T; fi; end proc;
I was wondering if anyone could help with the coding? Maybe another way of storing the children. It may also be that it cannot be done with recursion.
Thanks
Edit#1 : Pseudo code would look like:
Input: n:nonneg integer, P: probability law if n=0 then return 1 vertice else create 1 vertice; i=0; while i<=n for each vertices in generation i generate a random number p from Law P and connect it with p other vertices (in generation i+1); i=i+1; Return the graph