python - 从图边列表创建嵌套字典

Question

如何将图边列表转换为嵌套的分层字典？

一些背景:我需要这个字典来实现 D3.js 可视化。我正在尝试复制此格式:https://raw.githubusercontent.com/d3/d3-hierarchy/v1.1.8/test/data/flare.json在聚类树状图中使用:https://observablehq.com/@d3/cluster-dendrogram

输入( child 和 parent ):

[
("a", "b"),
("c", "a"),
("d", "a"),
("e", "a"),
("f", "a"),
("g", "a"),
("h", "g")
]

期望的输出:

{
    "name": "b",
    "children": [
        {
            "name": "a",
            "children": [
                {"name": "c"},
                {"name": "d"},
                {"name": "e"},
                {"name": "f"},
                {
                    "name": "g",
                    "children": [
                        {"name": "h"}
                    ]
                }

            ]
        }
    ]
}

Answer 1

试试这个:

elements = [
    ("a", "b"),
    ("c", "a"),
    ("d", "a"),
    ("e", "a"),
    ("f", "a"),
    ("g", "a"),
    ("h", "g")
]

def create_result_element(name, children):
    if children:
        return {'name': name, 'children': children}
    else:
        return {'name': name}

def get_children(parent, a, seen):
    return [
        create_result_element(e[0], get_children(e[0], a, seen | {e[0]}))
        for e in a
        if e[1] == parent and e[0] not in seen
    ]

def create_tree(a):
    # Search for elements with no parent
    top_elements = {e[1] for e in a} - {e[0] for e in a}
    return [
        create_result_element(t, get_children(t, a, {t}))
        for t in top_elements
    ]

print(create_tree(elements))

这将打印:

[
  {
    'name': 'b',
    'children': [
      {
        'name': 'a',
        'children': [
          {'name': 'c'},
          {'name': 'd'},
          {'name': 'e'},
          {'name': 'f'},
          {
            'name': 'g',
            'children': [
              {'name': 'h'}
            ]
          }
        ]
      }
    ]
  }
]