Forum: Ruby looping through a tree from trunk to leaves

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
C91098dc76d7ad473165ef24fe805312?d=identicon&s=25 Nanyang Zhan (xain)
on 2007-04-20 20:45
I've just built a acts_as_tree model,
now I need to render it out as a tree structure in view.
and I also need a action method to loop through every row of the
database following the tree structure ( from root to it's branch, then
to the ends of the branch, then go back for other branches...). I think
both the view helper and action method need to use a similar loop style,
and this code may be popular, at lease useful. Is there any article
about this subject?

I've get a view snip, btw:
http://snippets.dzone.com/tag/acts_as_tree
Ac0085dae0703db56ad7f8cb9e1798ba?d=identicon&s=25 Phillip Gawlowski (Guest)
on 2007-04-20 20:53
(Received via mailing list)
Nanyang Zhan wrote:
> http://snippets.dzone.com/tag/acts_as_tree
>

You might want to tell the Rails folk, too.
http://www.rubyonrails.com/community

--
Phillip "CynicalRyan" Gawlowski
http://cynicalryan.110mb.com/
http://clothred.rubyforge.org

Rule of Open-Source Programming #8:

Open-Source is not a panacea.
D4d28bd014f9e7324bad99dcc3b0d390?d=identicon&s=25 Rich Morin (Guest)
on 2007-04-20 21:57
(Received via mailing list)
At 3:45 AM +0900 4/21/07, Nanyang Zhan wrote:
> I've just built a acts_as_tree model,
> now I need to render it out as a tree structure in view.
> and I also need a action method to loop through every row ...

The word "loop" may be leading you in the wrong direction.  If
you hear the words "tree" or "hierarchy", you should be looking
at recursive solutions.  So, in pseudo-ruby:


  # walk - level is either an item or a tree of items
  #
  def walk(level)
    if level.is_leaf?
      # handle leaf action
    else
      # handle branch pre-action
      level.each { |item| walk(item) }
      # handle branch post-action
    end
  end

In my (limited) experience, recursive code tends to be very
small and simple, once written.  Writing it, however, can be
challenging, in that it requires a different way of thinking
than iterative code does.


There are also tree-walk routines that will simply allow you
to iterate through the nodes of a tree.  Whether there is a
routine such as this for your particular tree, I don't know.

-r
--
http://www.cfcl.com/rdm            Rich Morin
http://www.cfcl.com/rdm/resume     rdm@cfcl.com
http://www.cfcl.com/rdm/weblog     +1 650-873-7841

Technical editing and writing, programming, and web development
Bc368ef524130e8d0deb386de961e24a?d=identicon&s=25 Suraj Kurapati (snk)
on 2007-04-20 22:57
Nanyang Zhan wrote:
> from root to it's branch,
> then to the ends of the branch,
> then go back for other branches...

This is a Depth First Search (DFS) tree traversal:

  http://en.wikipedia.org/wiki/Depth-first_search
9dfe8c734b0f9b37a4e218425c0a2138?d=identicon&s=25 Gene Tani (Guest)
on 2007-04-21 00:11
(Received via mailing list)
On Apr 20, 11:45 am, Nanyang Zhan <s...@hotmail.com> wrote:
>
> --
> Posted viahttp://www.ruby-forum.com/.

google thru *rails-talk* for ajax tree control, widgets, etc, you'll
see:

http://ajaxonrails.wordpress.com/2006/11/26/ajaxon...
http://www.epiphyte.ca/code/live_tree.html

and lots more
F5bb435184cc39b6ef4847ed29cfdc46?d=identicon&s=25 Roseanne Zhang (roseanne)
on 2007-04-21 00:20
Suraj Kurapati wrote:
> Nanyang Zhan wrote:
> This is a Depth First Search (DFS) tree traversal:
>
>   http://en.wikipedia.org/wiki/Depth-first_search

Way to go!!!!
C91098dc76d7ad473165ef24fe805312?d=identicon&s=25 Nanyang Zhan (xain)
on 2007-04-21 00:29
Rich Morin wrote:
> The word "loop" may be leading you in the wrong direction.  If
> you hear the words "tree" or "hierarchy", you should be looking
> at recursive solutions.

Now it seems obviously "loop" IS a wrong word. Both "walk" and "travel"
are far more fit the idea.

I'll start form a very simple tree, no cross. and your code certainly
give my a idea to start. thanks.



Suraj Kurapati wrote:

> This is a Depth First Search (DFS) tree traversal:
>
>   http://en.wikipedia.org/wiki/Depth-first_search

And thank you, Suraj Kurapati. The link and the terms no only help solve
my problem, but also open a world of search relate algorithm to me.
Bea287582f4125fa81a2ca945bd48753?d=identicon&s=25 Julian I. Kamil (Guest)
on 2007-04-21 03:50
(Received via mailing list)
This will do for 'MyModel':

def view(args)
  args[:children].each do |child|
    printf("%03d %s%s\n", child.id, args[:level], child.class.name)
    view(:children => child.children, :level =>
"#{args[:level].gsub(/./, ' ')} ...")
  end
end

view(:children => MyModel.find(:all, :conditions => [ "parent_id IS
NULL" ]), :level => '')

Julian I. Kamil <julian.kamil@gmail.com>
This topic is locked and can not be replied to.