Collatz問題 #17

値が100以下のノードにおける最長経路の開始ノードが97であることは、
初期値と操作回数の対応を詳細に見るためのCプログラムによって、
97から始めて118回の操作で1に至る結果から得られている。
これを別の方法で見てみる。
Graphvizにはdijkstraコマンドがある。
その名の通りDijkstra法でノード間の距離を求めるコマンドである。

$ ./collatz9 | tred 2> /dev/null | dijkstra 1 > dist.gv

これにより、

dist.gv

digraph {
        graph [maxdist="118.000"];
        edge [color=blue];
        1        [dist="0.000"];
        4        [dist="1.000"];
        1 -> 4   [color=red];
        2        [dist="1.000"];
        4 -> 2;
        2 -> 1;
        6        [dist="7.000"];
...snip

のように、dijkstraに引数で与えたノード1からの距離に関する属性が元のグラフに付加される。
dijkstraのデフォルトでは隣接ノード間の距離、つまりエッジ長は全て1であり、
グラフにはノード1からの最長距離を表すmaxdist属性、各ノードにはノード1からの距離を表すdist属性が付く。
maxdistが118であることから丁度118回の操作に対応していてめでたしめでたし、という訳にはいかない。
collatz9は100以下の開始ノードのさらに1個上流のノードも出力するので、maxdistは119にならなければならない。
原因は4 2 1 4のループにある。
そもそも有向グラフであるのに、その最下流の1のノードからの距離が出るということは、
dijkstraがエッジの向きを無視している事に他ならない。
上に示したdist.gvにおいてノード4のdistが1になっていることから、
ノード4より上流の距離はノード2をバイパスして1から4へ直接遡った場合の距離になっている。
そこで、手っ取り早い解決のために1から4へのエッジを消してしまおう。

$ ./collatz9 | gvpr -c 'E[tail.name==1]{delete($G,$);}' | tred | dijkstra 1 > dist.gv

tredで多重エッジを解消してから、1から4へのエッジをgvprで消してもいいが、
ここでは先に全ての1から4へのエッジを消してからtredで他の多重エッジを一本化した。
tredに与えるグラフにはループが無くなるのでtredにその旨を警告されることがなくなる。
gvprのオプション-cは入力グラフに変更を適用してそのまま出力に使用することを指示する。
-cオプションが無い場合は明示的に出力してやらないと何も出力しない。

$ grep maxdist dist.gv
        graph [maxdist="119.000"];

今度はちゃんとmaxdistが119になった。
せっかくなのでどこでも使えるわけではないgrepではなく、Graphvizで閉じるようにgvprで確認する。

$ gvpr 'BEG_G{print(maxdist);}' dist.gv
119.000

さて、ノード97のノード1からの距離は、

$ gvpr 'N[name==97]{print(dist);}' dist.gv
118.000

きちんと118という結果が得られた。