CODEWITHSUNDEEP
pythonjson
jesy2013
jesy2013

Reputation: 319

How to assign children of a node wherever the node exist in the depth of a tree in Python?

I have data that describes a tree (parent - children). I want to build a JSON file based on it and assign children of a parent wherever the parent is found in the tree.

This problem is the extension of this answer: https://stackoverflow.com/a/57216064/1233240

Code:

file = [
     ('parent1', ['child1', 'child2', 'child3']),
     ('parent2', ['child4', 'child5', 'child6']),
     ('child1', ['child7', 'child8']),
     ('child5', ['child10', 'child33']),
     ('parent3', ['child1', 'child2', 'child3'])
]

json_dict = {}
flat_dict = {}

for parent, children in file:
    if parent in flat_dict:
        value = flat_dict[parent]
    else:
        value = {}
        flat_dict[parent] = json_dict[parent] = value
    for child in children:
        flat_dict[child] = value[child] = {}

Current Output:

{
    "parent1": {
        "child1": {
            "child7": {},
            "child8": {}
        },
        "child2": {},
        "child3": {}
    },
    "child1": {},
    "child2": {},
    "child3": {},
    "parent2": {
        "child4": {},
        "child5": {
            "child10": {},
            "child33": {}
        },
        "child6": {}
    },
    "child4": {},
    "child5": {
        "child10": {},
        "child33": {}
    },
    "child6": {},
    "child7": {},
    "child8": {},
    "child10": {},
    "child33": {},
    "parent3": {
        "child1": {},
        "child2": {},
        "child3": {}
    }
}

Expected Output:

I want all child1 node like this:

"child1": {
    "child7": {},
    "child8": {}
}

but as we can see, only in parent1 node it keeps its children.

Upvotes: 1

Views: 74

Answers (2)

Mad Physicist
Mad Physicist

Reputation: 114548

One way would be to add a simple modification to the linked answer, to check if a child is already present, and use the existing object.

json_dict = {}
flat_dict = {}

for parent, children in file:
    if parent in flat_dict:
        value = flat_dict[parent]
    else:
        value = {}
        flat_dict[parent] = json_dict[parent] = value
    for child in children:
        if child in flat_dict:
            value[child] = flat_dict[child]
        else:
            flat_dict[child] = value[child] = {}

In both cases, the code can be shortened using dict.setdefault, but I normally wouldn't use that, since it creates an empty dictionary instance even when that's not necessary:

json_dict = {}
flat_dict = {}

for parent, children in file:
    if parent in flat_dict:
        value = flat_dict[parent]
    else:
        value = json_dict[parent] = flat_dict[parent] = {}
    for child in children:
        value[child] = flat_dict.setdefault(child, {})

While the second solution performs some potentially unnecessary operations, the code does look much clearer.

An alternative that is equally clean but with fewer unnecessary objects uses collections.defaultdict:

from collections import defaultdict

json_dict = {}
flat_dict = defaultdict(dict)

for parent, children in file:
    if parent in flat_dict:
        value = flat_dict[parent]
    else:
        value = json_dict[parent] = flat_dict[parent]
    for child in children:
        value[child] = flat_dict[child]

Aside from requiring an import, this solution will not print as cleanly as a regular-dict based one. However, that will not affect the conversion to JSON in any way.

Since you commented that you don't actually want child nodes in the root, the snippets shown here will only place parent nodes in root. They will not, however, remove a node from root if you find out that it is a child later on. This can be accomplished with another simple modification, shown here for the defaultdict example, but applicable to all others as well:

from collections import defaultdict

json_dict = {}
flat_dict = defaultdict(dict)

for parent, children in file:
    if parent in flat_dict:
        value = flat_dict[parent]
    else:
        value = json_dict[parent] = flat_dict[parent]
    for child in children:
        value[child] = flat_dict[child]
        json_dict.pop(child, None)

Here is an IDEOne link with the final answer.

Keep in mind that this code will not check for circular references. A circular reference will automatically remove itself from the result. For example:

file = [
    ('A', ['B']),
    ('B', ['C']),
    ('C', ['A']),
]

Upvotes: 1

LazyCoder
LazyCoder

Reputation: 1265

Hope this is what you wanted.

Code:

relations = []
for k,l in file:
    for v in l:
        relations.append((k,v))
pop_list=[]
items = {}
for parent, child in relations:
    parent_dict = items.setdefault(parent, {})
    child_dict = items.setdefault(child, {})
    if child not in parent_dict:
        parent_dict[child] = child_dict
    pop_list.append(child)
for child in pop_list:
    if child in items.keys():
        items.pop(child)
print(items)

Output:

{'parent1': {'child1': {'child7': {}, 'child8': {}}, 'child2': {}, 'child3': {}}, 'parent2': {'child4': {}, 'child5': {'child10': {}, 'child33': {}}, 'child6': {}}, 'parent3': {'child1': {'child7': {}, 'child8': {}}, 'child2': {}, 'child3': {}}}

Upvotes: 2

Related Questions