building trees and tree transversal

Kashia answered:

I've seen others on #nitro work on different types of Hierarchical structures in Og, but the one already in Og could be good for you.

I'm not into Graph structures and efficiency, but as far as I've seen with the "NestedSet" pattern in hierarchichal.rb...

This structure seems to be very fast in querying, but slow while inserting.

h3. Creating

class Foo
  is NestedSets # "is Hierarchical" doesn't work for me
  property :name, String
end

This is all for setting it up. You might want to query google for more information on the topic of Nested Sets.

Also, there is a very nice screencast from a Rails guy, where a forum is built, with the help of NestedSets which look just like the ones in Og. Google is your friend.

h3. Usage

Now that we have set up the Base class, we can use it.

# in controller
  def list_foos(node = Foo[1], options)
    html = '<div class="foos">'
    html << '<ul>'
    html << '<li>' + node.name + '</li>'
    
    html << list_foos_rec(node, options)
    
    html << '</ul></div>'
    return html
  end

  def list_foos_rec(node, options)
    children = node.direct_foos
    html = '<ul>'
    
    children.each do |child|
      html << '<li>' + node_to_link(child) + '</li>'
      if options[:full] && child.foos_count > 0
        html << list_foos_rec(child, options)
      end
    end
    html << '</ul>'
    
    return html
  end
# ...

This is a cutdown snippet of one of my projects. It traverses through a Nested Set, and builds a tree structure with li's.

h3. General Info

This already shows two functions:

• .direct_foos
• .foos_count

The first one gets the children, which are direct children of the current node, the second gets the number of children. But there are more function, but first I have to explain the naming scheme:

• children => base.to_s.demodulize.underscore.downcase.plural

That is a lot of code, but actually there is no problem, basically you call it with plural if you want to call the children.

For our example:

• children: Foo => foos

On to the other functions:

• root? # is this node a root node?
• child? # is this node a child of someone?
• parent # if possible, get the parent of this node.
• foos_count # get number of children.
• foos # gets the children of this node.
• full_foos # gets all children of this nide.
• direct_foos # gets the children right below this node.
• add_foo(child) # add a child to this node.

Thats about it, foos/fullfoos/directfoos all take a option hash, like Foo.find(options...).