quiz : 解答編 : Concurrent Clean : アルゴリズム

[id:lethevert:20060324:p2]のクイズの解答編です。（というか、ただ、私が解けただけなのですが）
もし、まだ考えている方がいたら（いないと思いますけど）、ネタばれ注意です。

プログラムの流れ

align nodes arcs --> draw --> fwritess

というのが基本的な流れです。
まず、align nodes arcsで頂点の配置を計算し、それに従ってdrawで頂点をキャンバスにプロットし、fwritessでキャンバスを描画します。
実際には、計算経過も出力するので、次のようにalign nodes arcsがリストを出力するようになっています。

align nodes arcs --> map (fwritess o draw)

align関数

alignは、次の流れで成り立っています。

align = initCell --> alignY --> alignX

initCellで頂点の配置を初期化し、alignYで頂点の上下の位置を決め、alignXで頂点を左寄せします。
alignXは、１つ目の頂点から順に、その頂点より前の連結している頂点の全ての位置より後ろで、もっとも前の位置に寄せていきます。

alignY関数

alignYがアルゴリズムの中心です。
最後尾の頂点から、深さ探索の行きがけにラベルを貼っていきます。ただし、一度、訪れた頂点は、２回訪れません。
ラベルは、0から始まり、バックトラックするごとに1が加算されます。最終的に、このラベルがY座標（上下の位置）になります。