STEP 5.1 モデル木 (分枝数b, 最大の深さm) の 接続行列

<背景> 根(ルート)のノード番号を0とする。ルートしかない木は深さ0とする。



STEP 5.0の model-treeは、b, mを引数とするモデル木について、以下のような情報を生成、出力する。

./model-tree 2 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が接続していることを読み取れる。



<問題> model-tree.exeの接続行列データ出力をパイプで受け取り、接続行列を出力せよ。また、引数のノードから接続しているノードをプリントせよ。

<実行例>

./model-tree 2 3 | ./matrix 4
     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
  0  .  1  1  .  .  .  .  .  .  .  .  .  .  .  .
  1  .  .  .  1  1  .  .  .  .  .  .  .  .  .  .
  2  .  .  .  .  .  1  1  .  .  .  .  .  .  .  .
  3  .  .  .  .  .  .  .  1  1  .  .  .  .  .  .
  4  .  .  .  .  .  .  .  .  .  1  1  .  .  .  .
  5  .  .  .  .  .  .  .  .  .  .  .  1  1  .  .
  6  .  .  .  .  .  .  .  .  .  .  .  .  .  1  1
  7  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  8  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  9  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 10  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 11  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 13  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 14  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
4: 9 10

4からは 9と10 に接続(辺があります。bが2だから、あるノードの子ノードは2つ)

<下のプログラムに適切に追加しなさい。上とは異なる実行例で確認してください>

(ファイル名をmatrix.c とすると、gcc -o matrix matrix.c でコンパイル)


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

/* 格納可能なノード最大値 */
#define NMAX 0xFFF

/* プロトタイプ */
void initAdj(void); /* adjacency 隣接 */
void printAdj(void);

int adj[NMAX][NMAX]; /* 確保。かなり大きい */
int nmax; /* 実際のモデル木の最大ノード */

/* 接続行列の初期化 */
void initAdj() {

    int i,j;
    int bf, md; /* bとmの値 */

    /* 最初の2行の制御用情報から、読み込み */
    scanf("# BF: %d, MD: %d\n", &bf, &md);
    scanf("# Tree Size %d\n", &nmax);

    /* 使用する部分に0をセット */
    for (i = 0; i < nmax; i++)
        for (j = 0; j < nmax; j++) 
            adj[i][j]=0;
 
    /* 3行目から、2つずつのデータを読み込む。最後はEOF。例題0101では、control z(UNIXはcontrol d) */
    while (scanf("%d %d", &i, &j)!=EOF) {
        if(i < nmax && j < nmax){
        adj[i][j]=1;
        }
    }
}

void printAdj(){
    int i,j;
  
    /* 以下を作成せよ */

}


int main(int argc, char *argv[]){
    int start, j;

    if (argc != 2){ /* コマンドと引数で2つなければ、すぐに終了 */
        exit(0);
    }

    start = atoi(argv[1]); /* 引数の文字列を整数に変換して、start変数に代入 */

    initAdj(); /* 初期化せよ。標準入力からデータを読み込み、セットせよ */
    printAdj(); /* 接続行列をプリント */

    printf("%d:", start);
    /* startノードに隣接しているノードを出力せよ */

    return 0;
}