graph (1)

先日ちょっとしたお祭り状態だった「単方向リンクリストの循環参照の有無を O(n) で検出する」問題．@IT のフォーラムや ladybug さんのところ (id:ladybug:20051116) などで取り上げられていたのでご存じの方も多いかと思いますが，まだ未見の方はまずはそちらからどうぞ．
http://www.cotton-tree.com/garyu/archives/2005/11/post_156.html
まあ流石に今更このネタについて書くわけではありません．以下ではちょっとした派生話題などでも．
3D プログラミングでも循環検出はよく出くわすトピックです．昔シーングラフライブラリを作っていたときの話ですが，ノード連結メソッドで循環を検出すべきかどうかに数日悩んだ記憶があります．シーングラフがツリーを保つ限りは再帰的に綺麗なアルゴリズムが書けるのですが，ツリーではなくなるような要素が入り込むととたんにややこしくなるのでどうしても神経質にならざるを得ません．
例えば LightWave には，オブジェクトの回転制御の方法として「常にワールド座標での特定オブジェクト方向に Z 軸を向ける」というモードがあります．このモードの使い方を誤ると座標系の計算に循環が発生してしまい，計算が終わらなくなってしまいます．
今であれば物理エンジンによって差分化された形で面白い循環が扱えていることでしょう．3次元世界に住む我々には，目の前にぶら下がるニンジンへの距離に応じて速度を変える馬の存在を普通と感じるのですが，それを許すのはそれを許すだけの「やさしさ」を実装してくれた神様が居てこその話です．多分日曜日も安息できなかった勤勉な神様に感謝を．