How to recursively search through self-referential subtopics?

Question

If I have a self-referential Topic class and I want to recursively loop through all of my subtopics, what would be a good Ruby way to do that:

@category.topics.all(:parent_id => topic.id).each do |subtopic|
    subtopic.delete_tags
    @category.topics.all(:parent_id => subtopic.id).each do |subsubtopic|
    subsubtopic.delete_tags
        @category.topics.all(:parent_id => subsubtopic.id).each do |subsubsubtopic|
        subsubtopic.delete_tags
            @category.topics.all(:parent_id => subsubsubtopic.id).each do |subsubsubsubtopic|
            subsubsubtopic.delete_tags
            end
        end
    end
end

Answer 1

Something like this?

class Topic
  def delete_subtopic_tags
    all(:parent_id => self.id).each do |subtopic|
      subtopic.delete_subtopic_tags
      subtopic.delete_tags
    end
  end
end

Answer 2

Is this an ActiveRecord model class? If so, you should be able to cleanly recurse through child objects using something like the following code:

class Topic
  has_many :topics
  belongs_to :parent, :classname => "Topic", :foreign_key => 'parent_id'

  # ...other model class logic...
  def delete_tags_recursive
    delete_tags
    topics.each {|subtopic| subtopic.delete_tags_recursive }
  end
end

This has the additional benefit of letting you use the topics and parent methods created by the has_many and belongs_to decorators in order to easily walk the topic tree.

Answer 3

I don't know Ruby, but if you have hash table and linked list implementations handy I'd do it something like this (in Java-ish pseudocode):

Topic currentTopic = topic;
list.add(currentTopic);
hashtable.add(currentTopic);
while (list.empty() == false) {
    for (Topic t : currentTopic.getSubtopics()) {
        if (hashtable.contains(t) == false) {
            list.add(t);
            hashtable.add(t);
        }
    }
    visit(currentTopic);
    list.remove(currentTopic);
    currentTopic = list.getFirst();
}

The major point here is to keep the hashtable list so that you can easily make sure that you never visit a Topic twice. Other than that, it's essentially an implementation of breadth-first search. visit() does whatever you need to do for each individual topic.