c-----------------------------------------------------------
c Chapter 29: Random Unlabeled Rooted Trees(P274)
c-----------------------------------------------------------
c   Name of subroutine: RANRUT
c
c   Algorithm:Generating random unlabled rooted tree
c
c   input: nn=5
c   number of calls: run=50   
c   complier: f77 ranrut_2.f
c-----------------------------------------------------------
       
      parameter(nn=5,run=50)
      integer t(nn),stack(2,nn),tree(nn)
      do 30 j=1, run
      call ranrut(nn,t,stack,tree)
      write(*,20),(tree(i),i=1,nn)
20    format(5(i2))
30    continue
      stop 
      end

c-----Subroutine begines here-------------------------------
      subroutine ranrut(nn,t,stack,tree)
      implicit integer(a-z)
      real rand
      dimension tree(nn),stack(2,nn),t(nn)
      data nlast/1/
      t(1)=1
1     if(nn.le.nlast) go to 10
      sum=0
      do 2  d=1,nlast
      i=nlast+1
      td=t(d)*d
      do 3  j=1,nlast
      i=i-d
      if(i.le.0) go to 2
3     sum=sum+t(i)*td
2     continue
      nlast=nlast+1
      t(nlast)=sum/(nlast-1)
      go to 1
10    n=nn
      is1=0
      is2=0
12    if(n.le.2) go to 70
20    z=(n-1)*t(n)*rand(iseed)
      d=0
30    d=d+1
      td=d*t(d)
      m=n
      j=0
40    j=j+1
      m=m-d
      if(m.lt.1) go to 30
50    z=z-t(m)*td
      if(z.ge.0) go to 40
60    is1=is1+1
      stack(1,is1)=j
      stack(2,is1)=d
      n=m
      go to 12
70    tree(is2+1)=l
      l=is2+1
      is2=is2+n
      if(n.gt.1) tree(is2)=is2-1
80    n=stack(2,is1)
      if(n.eq.0) go to 90
      stack(2,is1)=0
      go to 12
90    j=stack(1,is1)
      is1=is1-1
      m=is2-l+1
      ll=tree(l)
      ls=l+(j-1)*m-1
      if(j.eq.1) go to 105
      do 104 i=l,ls
      tree(i+m)=tree(i)+m
      if(mod(i-l,m).eq.0) tree(i+m)=ll
104   continue
105   is2=ls+m
      if(is2.eq.nn) return
      l=ll
      go to 80
      end