STEP 5.0　モデル木　(分枝数b, 最大の深さm) の 接続情報の出力プログラム

作業

  1. model-tree.c というファイル名で、ソースプログラムを準備してください。
  2. コンパイルします。　gcc -o model-tree model-tree.c
  3. すると、下のような実行結果が得られます。

<背景> 根（ルート）のノード番号を0とする。ルートしかない木は深さ0とする。bは、枝分かれ数、mは、木の深さである。



model-tree.exeは、b, mを指定したモデル木について、以下のような接続情報　（辺; エッジ) を生成、出力する。

./model-tree 2 3　　（←　b=2, m=3を指定しています）

# BF: 2, MD: 3
# Tree Size 15
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14

(出力の最初の2行は、制御用の情報です。3行目からが辺の情報です。次の課題で使用する情報です)

上の出力からは、たとえば、「ノード4からは、ノード9, 10が接続していること」を読み取れる。

<下のプログラムを、そのまま、コンパイルしてください> 

解答例
#include <stdio.h>
#include <stdlib.h> 

/************************************************************
 * State
 ************************************************************/
typedef int stid;

/************************************************************
 * Model Tree
 ************************************************************/
int BF;	// Branching Factor
int MD;	// Max Depth
int NOCH;

// treeSize(D)
// size of a model tree with branching factor BF and depth D
// \sum_{j=0}^D B^j ... if j >= 0

int treeSize(int d){

  if(d < 0) return 0;
  if(d == 0) return 1;
  else return 1 + BF * treeSize(d-1);
}

// treeDepth(N)
// depth of the node N in a model tree with branching factor BF
// (root = 0)
int treeDepth(stid n){

  if(n == 0) return 0;
  else return 1 + treeDepth((n - 1) / BF);
}

// firstChild(N)
// the first child of the node N in a model tree with branching factor BF
// (root = 0, NOCH = all 1)
stid firstChild(stid st){
  int d;

  d = treeDepth(st);
  if(d == MD) return NOCH;
  else return treeSize(d) + BF * (st - treeSize(d - 1));
}

/**********************************************************************
 * Main
 **********************************************************************/

int main(int argc, char *argv[]){
  int tsize;
  int i, j, fc;

  if( argc != 3 ){
    exit(0);
  }

  BF = atoi(argv[1]);
  MD = atoi(argv[2]);
  NOCH = ~(stid) 0;

  printf("# BF: %d, MD: %d\n", BF, MD);
  tsize = treeSize(MD);
  printf("# Tree Size %d\n", tsize);

  for(i = 0; i < tsize; i++){
    fc = firstChild(i);
    /*
    printf("%d: ", i);
    if(fc != NOCH)
      for(j = 0; j < BF; j++) printf(" %d", fc + j);
    printf("\n");
    */
    if(fc != NOCH)
      for(j = 0; j < BF; j++) printf("%d %d\n", i, fc + j);
  }

}