Tree to Array Algorithm (Ruby)

Question

I have a branching model that consists of parent_id and child_id. I want to get an array of relationships between parents and children without asking 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 1 child, and the children of his children, like this:

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

without asking each parent for its children.

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

Answer 1

The first search will be the completion of the assignment.

 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=>{}} 

Answer 2

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 edges (and now you will understand 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