/*==============================================================*/
/* program: RootedTree.c */
/* purpose: generating all rooted trees */
/* input : n -- number of nodes */
/* mc -- max number of children of a node */
/* lb,ub -- lower and upper bound on height */
/* output : listing of rooted trees in relex order */
/* date : September 1995, updated Sept 2000 */
/* programmers: Gang Li & Frank Ruskey */
/* algorithm: From the paper: G. Li and F. Ruskey, "The */
/* Advantages of Forward Thinking in Generating Rooted and */
/* Free Trees", 10th Annual ACM-SIAM Symposium on Discrete */
/* Algorithms (SODA), (1999) S939-940. See the web page at */
/* http://www.theory.csc.UVic.CA/~fruskey/ */
/* Publications/RootedFreeTree.html */
/* more info: See */
/* http://www.theory.csc.UVic.CA/inf/RootedTrees.html */
/*==============================================================*/
#include
#define MaxSize 64 /* max size of the tree */
#include
using namespace std;
int
n, /* number of nodes in a tree */
par[MaxSize], /* parent position of i */
L[MaxSize]; /* level of node i */
unsigned __int64 num; /* total number of trees */
int mc, /* max number of children */
chi[MaxSize], /* number of children of a node */
nextp[MaxSize], /* next good pos to add nodes */
rChi[MaxSize], /* the right most child of node i */
lb, /* lower bound of the height */
ub; /* upper bound of the height */
// code added by W. Bomfim
const int maxN = 30;
unsigned __int64 an; // a(n)
int Pai[maxN + 1]; // Copy of par[2] to par[n]
unsigned int C[maxN+1], // C[i], 1<=i<=n, number of occurences of i in array Pai
nL; // Number of zeros in C, or number of leaves
void inicialize(){
static int i;
C[1] = 0;
for(i=2; i<=n; i++){
Pai[i] = par[i];
C[i] = 0;
}
for(i=2; i<=n; i++)
C[Pai[i]]++;
nL = 0;
for(i=2; i<=n; i++)
if(C[i]==0)
nL++;
an = nL + (C[1] == 1);
}
void PrintIt() {
static int i, k, L;
num = num+1;
if(num == 1){
inicialize(); return; }
for(i=2; i<=n; i++)
if(par[i] != Pai[i]){
L = Pai[i];
C[L]--;
if(C[L]==0) nL++;
L = par[i];
C[L]++;
if(C[L]==1) nL--;
Pai[i] = par[i];
}
an += nL + (C[1] == 1);
}
// Gang Li & Frank Ruskey function Gen()
void Gen( int p, int s, int cL ) {
int np, temp;
if (p > n) PrintIt();
else {
if (cL==0 && p <= ub+2 ) par[p] = L[p] = p-1;
else
if (par[p-cL] < s) { par[p] = par[s]; L[p] = L[s]; }
else { par[p] = cL + par[p-cL]; L[p] = 1+L[par[p]]; }
++chi[par[p]];
temp = rChi[par[p]];
if (chi[par[p]] <= mc) {
rChi[par[p]] = p;
nextp[p] = chi[par[p]] < mc ? par[p] : nextp[par[p]];
Gen( p+1, s, cL ); /* <==== recursive call */
rChi[par[p]] = temp;
}
--chi[par[p]];
nextp[p] = nextp[par[p]];
np = nextp[p];
while (np >= 1) {
par[p] = np; L[p] = 1 + L[np];
++chi[np];
temp = rChi[np]; rChi[np] = p;
if (chi[np] >= mc) nextp[p] = nextp[np];
Gen( p+1, temp, p-temp ); /* <==== recursive call */
--chi[np];
rChi[par[p]] = temp;
np = nextp[np];
nextp[p] = np;
}
}
}
int main(){ // code modified by W. Bomfim
int i;
for(n=1; n<=maxN; n++){
mc = n-1;
lb = 0;
ub = n;
num = 0;
for( i=1; i<=n; i++)
chi[i]=0;
for (i=1; i<=lb+1; i++) {
par[i] = L[i] = nextp[i] = i-1;
rChi[i] = i+1; chi[par[i]] = 1;
}
rChi[lb+1] = 0;
Gen(lb+2, 0, 0);
cout << an << ", ";
}
printf("\n");
return(0);
}