Collatz問題 #19

Graphviz

これまでのところ、新規にグラフを作成するためにC言語でDOT言語表現を出力していた。
しかし実のところC言語でプログラムを書かなくてもgvprのみを使って新規のグラフを吐くプログラムが書ける。

collatz11.g
END {
# new directed graph with default edge color: blue
  graph_t g = graph("", "D");
  setDflt(g, "E", "color", "blue");

# insert loop "1 -> 4 -> 2 -> 1" and "8 -> 4"
  edge_sg(g, node(g, 2), node(g, 1), "");
  edge_sg(g, node(g, 4), node(g, 2), "");
  edge_sg(g, node(g, 8), node(g, 4), "");
  edge_t e = edge(node(g, 1), node(g, 4), "");
  aset(e, "color", "red");
  subedge(g, e);

# insert edges from source to result of collatz operation
  graph_t q1 = graph("", "N");
  node(q1, 8);
  node_t top, result, source;
  int level;
  for (level = 0; level < 10; level++) {
    graph_t q2 = graph("", "N");
    for (top = fstnode(q1); top != NULL; delete(q1, top), top = fstnode(q1)) {
      result = node(g, top.name);
      if (result.name % 6 == 4) {
        source = node(g, (result.name - 1) / 3);
        e = edge(source, result, "");
        aset(e, "color", "red");
        subedge(g, e);
        node(q2, source.name);
      }
      source = node(g, result.name * 2);
      edge_sg(g, source, result, "");
      node(q2, source.name);
    }
    clone(q1, q2);
  }

# output graph
  write(g);
}

これは値8へ10回以内の操作で達することのできる値を挙げてグラフとして出力するコードである。
8から1へ至る経路のエッジは簡単のためにハードコードしてある。

  for (level = 0; level < 10; level++) {

のループ本体が始まる時点で、level回の操作で8に達するノードがグラフq1に登録されている。
q1からノードを1個ずつ取り出して操作前の値を計算しグラフq2に登録していく。
操作前の値と操作後の値の対はエッジとして出力用グラフgに登録していく。
q1にノードがなくなった時点でそのlevelへ至るノードが全てq2に登録されており、
次のループを始める前にq2の内容をq1にコピーしている。
このgvprプログラムを、

$ ./gvpr -fcollatz11.g /dev/null | dot -Tpng -ocollatz11.png

のように入力データなしでgvprに評価させることでグラフが得られる。
gvprにデータが無いことを示すにはWindowsならnul、UNIX系なら/dev/nullをファイル名に指定してやればよい。
もしくはDOT言語で書かれた何かを与えてやってもよい。このコードは単にそれを無視する。
結果のグラフは次のようになる。

グラフデータのフィルタとして使用するのがgvprの主たる目的だろうから、
このような使い方はちょっと邪な気もするけれど、
コンパイルとか不要の簡易なグラフ作成スクリプトの実行環境としてgvprは役に立つ。
gvprのintは無限精度ではなく、gvprをコンパイルしたC処理系のint型の精度に依存することには注意が必要。