Алгоритм дерева к массиву (Ruby)

Question

У меня есть модель ветви, которая состоит из parent_id и child_id.Я хочу получить массив отношений между родителями и детьми, не запрашивая каждого родителя для своих детей.

Для этой таблицы:

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

Я хочу получить детей 1 и детей его детейнапример:

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

без опроса каждого родителя для своих детей.

Существует ли алгоритм для эффективного достижения этого или мне нужно пройти через каждого родителя?Спасибо.

Answer 1

Поиск будет выполнен с первого дыхания.

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

Функциональный и рекурсивный подход:

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

[править] Без фасетов (и теперь вы поймете, почему я его использую!):

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