木構造で循環

先日、
「単方向リンクリストの循環参照の有無をO(n)で検出する」問題
が各所で話題となっていました。

さてさてさて、
現在仕事で作っている、締め切り間際のプログラムがあるのですが、このプログラムに循環参照しているデータを与えるとStackOverflowError例外を投げて終了してしまうのです。
（Javaで組んでいて、該当箇所は再帰呼び出しをしているので…）

元々、循環参照しているデータは、処理対象外で動作保証外なので、エラーで終了しようが、OSが落ちようが、マシンから異音がして爆発炎上しようが、いきなり出世して宝くじが当たってステキな恋人ができてウハウハな人生をおくる事になろうが、全然構わないのですが、折角なので、前以って検出できないか考えてみることにしました。

ただ、上記問題と違うのは、
データ構造が単方向リンクリストではなく、N分木なんですよね。

って、循環したら木構造とちゃうやん。

リンクリストの場合、「リストを1つずつ進むポインタと2つずつ進むポインタを用意して、リストの終りに達する前に同じ場所を指したら循環」って方法で検出できるそうですが、木では無理です。

いや、子ノードへ遷移する時に子の数だけスレッドを作って並列に処理させれば可能じゃないのかと思ったりして…。
もっとも、スレッドの数が凄い事になるので、実用的じゃ無さそうですけど。

で、何か良い方法はないものかと調べていると………。

「Windowsのファイルシステムは、ディレクトリを循環させられる」！？

この辺の物を使用するみたいです。

今日の一冊
	ハイペリオン (海外SFノヴェルズ) 作者: ダン シモンズ 出版社/メーカー: 早川書房 発売日: 1994/12 メディア: 単行本