Comment Machine
Comment Machine

Reputation: 3

Constructing a nested dictionary based on parent-children relationship?

I am given a list of dictionaries like this:

[
    {'A': ['B', 'C', 'D']},
    {'B': ['E', 'F']},
    {'C': ['E']},
    {'F': ['G', 'H']}
]

A key in the dictionary is a parent of a corresponding dictionary value, i.e., {parent: [child1, child2, child3]}

How can I construct a tree-like dictionary in the following format like the following:

{'A':{'B':{'E': None,
           'F': {'G': None,
                 'H': None}
          },
      'C': {'E': None}}

If a node doesn't have a child, we will fill its value with None. I don't know how to write a recursive process to transform the list into a dictionary, any idea?

Thanks!

Upvotes: 0

Views: 664

Answers (2)

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion:

d = [{'A': ['B', 'C', 'D']}, {'B': ['E', 'F']}, {'C': ['E']}, {'F': ['G', 'H']}]
d1 = dict(list(i.items())[0] for i in d)
def flatten_structure(d, root = 'A'):
  if root:
    return {root:flatten_structure(d1[root], None)}
  return {i:flatten_structure(d1[i], None) if i in d1 else None for i in d}

print(flatten_structure(d1['A']))

Output:

{'A': {'B': {'E': None, 'F': {'G': None, 'H': None}}, 'C': {'E': None}, 'D': None}}

Upvotes: 0

Mehrdad Pedramfar
Mehrdad Pedramfar

Reputation: 11073

You can do this with a recursive function:

def find_set(d, k, v):
    for key, value in d.items():
        if isinstance(value, dict):
            find_set(d[key], k, v)
            return
        if key == k:
            d[key] = {}
            for i in v:
                d[key][i] = None
            return d
    d[k] = {}
    for i in v:
        d[k][i] = None
    return d

Code:

l = [{'A': ['B', 'C', 'D']}, {'B': ['E', 'F']}, {'C': ['E']}, {'F': ['G', 'H']}]

d = {}
for node in l:
    for key, value in node.items():
        find_set(d, key, value)

d will be :

{'A': {'B': {'E': None, 'F': {'G': None, 'H': None}, 'C': {'E': None}}, 'C': None, 'D': None}}

Upvotes: 3

Related Questions