In article <997774251.527258.14423.nullmailer / ev.netlab.jp>,
  matz / ruby-lang.org (Yukihiro Matsumoto) writes:

> [ruby-dev:14451]の繰り返しになりますが、inspectは引数を取ら
> ないので、重複検査用の情報を外部から与える事ができません。こ
> れはinspectがこういうAPIなので出てくる制限です。Marshalには
> このような制限はありません。

それはあまり本質的ではないような気がしますが。
スレッド変数で渡すか引数で渡すかというだけの違いでしょう。

> traverseについては面白いといえば面白いですが、再帰まで考慮し
> て実用的に使えて、かつ汎用的なtraverse APIが定義できるかどう
> かちょっと自信がありません。

結局 DFS でしょう?
教科書に載っている通りに DFS を書けばいいんじゃないですか?

# そういえば、なぜ Depth First Search とゆーのはなぜ探さなくても
# search なのだろう? Depth First Traverse と呼ぶべきではないだろうか...
# いや、Discrete Fourier Transform と混乱するか。

class DFS
  def initialize(obj)
    @curr = @number = 1
    @hash = {obj.__id__ => -1}
  end

  def status(obj)
    id = obj.__id__
    unless @hash.include? id
      return :fresh
    end

    number = @hash[id]
    if number < 0
      return :backward
    elsif @curr < number
      return :forward
    else
      return :cross
    end
  end

  def traverse(obj)
    if (s = status(obj)) == :fresh
      id = obj.__id__
      number = @number += 1
      @hash[id] = -number
      prev = @curr
      @curr = number
      yield s
      @curr = prev
      @hash[id] = number
    else
      yield s
    end
  end

  def DFS.start(obj)
    old = Thread.current[:__dfs__]
    Thread.current[:__dfs__] = DFS.new(obj)
    yield :fresh
    Thread.current[:__dfs__] = old
  end

  def DFS.status(obj)
    Thread.current[:__dfs__].status(obj)
  end

  def DFS.traverse(obj, &block)
    Thread.current[:__dfs__].traverse(obj, &block)
  end
end

# うろ覚えで書いた上、一切テストしてません。
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「ふえろ! わかめちゃん作戦です$(C⊇」(Little Worker, 桂遊生丸)