Ruby RGL开发中如何递归将扁平数组重构为多维嵌套数组

使用 ruby RGL library 存储嵌套结构做结构还原时，调用graph.edges.as_json会返回扁平的边关系数组，需要将其转换为等价的多维嵌套结构。

输入示例 #

[
  {"source"=>1, "target"=>8}, 
  {"source"=>8, "target"=>10}, 
  {"source"=>8, "target"=>13}, 
  {"source"=>8, "target"=>9}, 
  {"source"=>10, "target"=>102}, 
  {"source"=>102, "target"=>103}, 
  {"source"=>102, "target"=>105}, 
  {"source"=>102, "target"=>101}, 
  {"source"=>103, "target"=>104}, 
  {"source"=>104, "target"=>101}, 
  {"source"=>101, "target"=>96}
]

期望输出格式 #

[
  {source: 1,
    target: [
      {source: 8,
        target: [
          {source: 10,
            target: [
              {source: 102, 
                target: [
                  {source: 103,
                    target: [
                      {source: 104,
                        target: [
                          {source: 101,
                            target: [
                              {source: 96,
                                target: []
                              }
                            ]
                          }
                        ]
                      }
                    ]
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
]

实现代码 #

实现逻辑分三步：

1. 构建邻接表，存储每个节点对应的所有直接子节点
2. 识别根节点：所有没有入边（从未作为target出现在边记录中）的节点为顶层根节点
3. 从根节点递归向下遍历构建嵌套结构，增加访问标记避免图中环导致的无限递归

require 'set'

def edges_to_nested(edges)
  # 构建邻接表与入边节点集合
  adjacency_list = Hash.new { |hash, key| hash[key] = [] }
  incoming_nodes = Set.new

  edges.each do |edge|
    source = edge["source"]
    target = edge["target"]
    adjacency_list[source] << target
    incoming_nodes.add(target)
  end

  # 查找所有根节点
  root_nodes = adjacency_list.keys.reject { |node| incoming_nodes.include?(node) }

  # 递归构建单节点嵌套结构
  build_nested_node = lambda do |current_node, visited_nodes|
    return nil if visited_nodes.include?(current_node)
    visited_nodes.add(current_node)
    
    {
      source: current_node,
      target: adjacency_list[current_node].map do |child_node|
        build_nested_node.call(child_node, visited_nodes.dup)
      end.compact
    }
  end

  root_nodes.map { |root| build_nested_node.call(root, Set.new) }
end

# 调用示例
edge_list = [
  {"source"=>1, "target"=>8}, {"source"=>8, "target"=>10}, {"source"=>8, "target"=>13},
  {"source"=>8, "target"=>9}, {"source"=>10, "target"=>102}, {"source"=>102, "target"=>103},
  {"source"=>102, "target"=>105}, {"source"=>102, "target"=>101}, {"source"=>103, "target"=>104},
  {"source"=>104, "target"=>101}, {"source"=>101, "target"=>96}
]
nested_result = edges_to_nested(edge_list)

特性说明 #

• 支持多根节点场景，若图存在多个无入边的顶层节点，会全部返回在顶层数组中
• 内置环检测逻辑，遇到带环的图结构不会触发无限递归栈溢出
• 叶子节点的target字段默认返回空数组，和期望输出格式完全对齐

内容的提问来源于stack exchange，提问作者user1009835