如何将嵌套字典存储的树转换为networkx兼容的边列表？

实现思路 #

你给出的嵌套字典结构符合「父节点为字典键，子节点全部存放在对应值的列表中」的规则，我们可以用BFS遍历整棵树，每遍历到一个父节点就提取它的所有直接子节点，生成边元组即可。

完整实现代码 #

from collections import deque

# 你的原始嵌套字典
output_dict = { 'Sort': [ { 'Aggregate': [ { 'Hash Join': [{ 'Hash Join': [ { 'Sequential Scan': [ ] }, { 'Hash': [ { 'Sequential Scan': [ ] } ] } ] },{ 'Hash': [ { 'Sequential Scan': [ ] } ] } ] } ] } }

edges = []
# 初始化BFS队列，每个元素格式为 (当前父节点名, 子节点列表)
queue = deque()
# 先提取根节点入队
root_node = next(iter(output_dict.keys()))
queue.append( (root_node, output_dict[root_node]) )

while queue:
    parent, children_list = queue.popleft()
    # 遍历当前父节点的所有子项
    for child_item in children_list:
        # 每个子字典只有1个键，即为子节点名称
        child_node = next(iter(child_item.keys()))
        # 生成边加入结果列表
        edges.append( (parent, child_node) )
        # 把子节点和它的子列表加入队列继续遍历
        queue.append( (child_node, child_item[child_node]) )

# 打印边列表结果
for edge in edges:
    print(edge)

运行输出 #

('Sort', 'Aggregate')
('Aggregate', 'Hash Join')
('Hash Join', 'Hash Join')
('Hash Join', 'Hash')
('Hash Join', 'Sequential Scan')
('Hash Join', 'Hash')
('Hash', 'Sequential Scan')
('Hash', 'Sequential Scan')

导入到NetworkX #

拿到边列表后直接调用add_edges_from方法即可构建有向图：

import networkx as nx
G = nx.DiGraph()
G.add_edges_from(edges)

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