Tree to array algorithm (Ruby)

Question

I have a branch model that consists of parent_id and child_id. I want to get an array of parent/children relations without querying each parent for its children.

For this table:

Parent_id | Child_id
1         | 2
1         | 6
1         | 9
2         | 3
3         | 10
4         | 7

I want to get 1's children, and his childrens' children like this:

{2 => {3 => {10}}, 6, 9}

without querying each parent for its children.

Is there an algorithm to achieve this efficiently or do I need to go through each parent? Thanks.

@tokland doesn't matter, I'm looking for either hash/array representation. — Gal
– Gal, Commented Nov 6, 2011 at 16:02

ZelluX · Accepted Answer · 2011-11-06 16:36:28Z

5

A breath-first search will do the job.

def build_tree(i, edges)
    list = {}
    out_nodes = edges.select {|e| e[0] == i}.map {|e| e[1]}.uniq
    out_nodes.each {|n| list[n] = build_tree(n, edges)}
    list
end

edges = [[1,2],[1,6],[1,9],[2,3],[3,10],[4,7]]
puts build_tree(1, edges)
# {2=>{3=>{10=>{}}}, 6=>{}, 9=>{}}

edited Nov 6, 2011 at 16:36

answered Nov 6, 2011 at 16:15

ZelluX

73.6k20 gold badges76 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Zabba Over a year ago

Mistook the times. This runs faster, at 3.6 seconds, 100,000 times. Benchmark pastie.

tokland · Accepted Answer · 2011-11-06 16:43:20Z

2

A functional and recursive approach:

require 'facets'

def create_tree(pairs, root)
  relationships = pairs.map_by { |parent, child| [parent, child] }  
  get_children = proc do |parent|
    (relationships[parent] || []).mash do |child| 
      [child, get_children.call(child)]
    end
  end  
  get_children.call(root)
end

pairs = [[1, 2], [1, 6], [1, 9], [2, 3], [3, 10], [4, 7]]
p create_tree(pairs, 1)
#=> {6=>{}, 2=>{3=>{10=>{}}}, 9=>{}}

[edit] Without facets (and now you'll see why I use it!):

def create_tree(pairs, root)
  relationships = Hash[pairs.group_by { |p, c| p }.map { |p, ary| [p, ary.map { |p, c| c }] }]
  get_children = proc do |parent|
    Hash[(relationships[parent] || []).map do |child| 
      [child, get_children.call(child)]
    end]
  end  
  get_children.call(root)
end

edited Nov 6, 2011 at 16:43

answered Nov 6, 2011 at 16:17

tokland

68.2k13 gold badges151 silver badges174 bronze badges

6 Comments

Gal Over a year ago

Facets is not working for me (I get a 500 error). Do you know why?

Zabba Over a year ago

Did you try gem install facets ?

Gal Over a year ago

I have it in my gemfile (I'm using rails), ran bundle.

Zabba Over a year ago

Mistook the times. The first code is 5 seconds, run 100,000 times.

tokland Over a year ago

@zabba, thanks for the benchmarkings. Is then this code faster than the imperative one? It's a bit surprising, maybe ZelluX's code is not the fastest implementation.

|

Collectives™ on Stack Overflow

Tree to array algorithm (Ruby)

2 Answers 2

1 Comment

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related