object_space_tree.rb

class ObjSpaceTree
  def initialize(object_id)
    @root = Node.new(object_id)
    expand
  end

  def expand
    depth = 0
    begin
      nodes_at_depth(depth).each do |node|
        has_children ||= !node.children.empty?
      end
      depth += 1
    end while has_children
  end

  def nodes_at_depth(depth)
    @root.nodes_at_depth(depth)
  end

  def prune(object_ids)
    @root.prune(object_ids)
  end

  class Node
    def initialize(object_id, parent=nil)
      @object_id = object_id
      @parent = parent
    end

    def children
      return @children if defined?(@children)

      reachable = ObjectSpace.reachable_objects_from(ObjectSpace._id2ref(@object_id))

      oids = (reachable || []).map do |object|
        next if object.is_a?(ObjectSpace::InternalObjectWrapper)

        oid = object.object_id
        next if oid.is_a?(Fixnum)

        oid
      end.compact.sort.reverse

      children = oids.map do |oid|
        Node.new(oid, self)
      end

      @children = children
    end

    def visited
      @visited ||= (parent ? parent.visited : Set.new)
    end

    def nodes_at_depth
      if depth == 0
        self
      else
        children.map do |child|
          child.nodes_at_depth(depth - 1)
        end.flatten
      end
    end
  end
end

def route(from, to, visited=nil)
  tree = { from => {} }
  depth = 0
  begin
    depth += 1
    # expand the tree
  end while has_children
end