ある記号列の列挙 #2

C Graphviz

再帰関数enumerateの呼び出し関係をグラフで表してみる。
例えば、enumerate(5, 4)内では個数aを一つ減じて、
enumerate(4, 4)が呼ばれているので、これを、


と表現することにする。
ノードに関数の二つの引数の値、エッジにaとbのどちらの記号数を減じて呼び出したかを表記している。
グラフの手書きは面倒なのでプログラムに書かせてみよう。

en2.c
#include <stdio.h>

static void enumerate(unsigned int a, unsigned int b)
{
    if (a > 0) {
        printf("\"%d %d\" -> \"%d %d\" [label=\"a\"];\n", a, b, a - 1, b);
        enumerate(a - 1, b);
    }
    if (b > 0) {
        printf("\"%d %d\" -> \"%d %d\" [label=\"b\"];\n", a, b, a, b - 1);
        enumerate(a, b - 1);
    }
}

int main(void)
{
    puts("digraph {");
    enumerate(5, 4);
    puts("}");
    return 0;
}

Graphvizが提供するライブラリを使わずDOT形式で直接標準出力に吐かせている。
プログラムの骨格は既述したコードそのままである。
どちらかの記号の個数を一つ減らしてenumerateを呼ぶ時に、
ノードとエッジの情報を出力するように付け加えただけである。
ノードを識別する名前は二つの引数の値そのものである。
そして、DOTとして完結するようenumerate(5, 4)を呼ぶ前後でdigraphの宣言を出力する。

このプログラムの出力はDOT形式なので、そのまま

$ ./en2 | dot -Tpng -o en2.png

で画像にすることができる。しかしかなり大きなものになる。

$ ./en2 | gc
      30     460 %1 (<stdin>)

30個のノードに対して460本のエッジが張られるようなグラフである。
この関数は二回関数を呼び出す機会があるので、
各ノードから多くとも二本のエッジしか出ていないとすれば、
グラフ中の総エッジ数は60本となり460本は多い。
これは、二つのノード間に複数のエッジが存在しているからである。
ある引数の組で呼び出された関数内からある引数の組で呼び出される関数は、
一度だけでなく複数回呼び出されることがあるのが原因である。
たとえば、enumerate(0, 0)はenumerate(1, 0)かenumerate(0, 1)からしか呼ばれないが、
前の記事によればenumerate(0, 0)は126回も呼ばれている。
これはenumerate(1, 0)やenumerate(0, 1)自体が何度も呼ばれていることを示している。
関数enumerateが何回呼ばれるかをsstestの方でカウントしたもの

$ ./sstest | wc -l
461

は、enumerate(5, 4)を呼ぶ操作がen2の出力ではエッジとして表現されていないため1の差がある。
多過ぎるエッジの数は関数の呼び出しをそのまま素直に表現したためである。
問題の性質上、二つのノード間に張られた複数のエッジのラベルが異なることはないので、
同じラベルの付いたエッジがかなりの多重度で張られていると推測できる。
というか実際にこの大きなグラフを画像にして見てみるとそうなっていることが分かる。
このようなグラフは、

$ ./en2 | tred | gc
      30      49 %1 (<stdin>)

のようにtredを使ってノード間のエッジ数をひとつにすることができる。
30個のノードと49本のエッジから成るグラフにまとめられた。
これはdotで画像にしてもいいくらいには小さくなったグラフだろう。

$ ./en2 | tred | dot -Tpng -o en2u.png