CODEWITHSUNDEEP
python
Maugrim
Maugrim

Reputation: 126

Create nested dict from list of graph edges

How can I convert a list of graph edges into a nested hierarchical dict?

Some background: I need this dict for D3.js visualization. I am trying to replicate this format: https://raw.githubusercontent.com/d3/d3-hierarchy/v1.1.8/test/data/flare.json to use in Cluster Dendogram: https://observablehq.com/@d3/cluster-dendrogram

Input (child and parent): 

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

Desired output:

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

            ]
        }
    ]
}

Upvotes: 2

Views: 325

Answers (1)

fafl
fafl

Reputation: 7385

Try this:

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))

This will print:

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

Upvotes: 4

Related Questions