3

Recursively build hierarchical JSON tree?

 2 years ago
source link: https://www.codesd.com/item/recursively-build-hierarchical-json-tree.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Recursively build hierarchical JSON tree?

advertisements

I have a database of parent-child connections. The data look like the following but could be presented in whichever way you want (dictionaries, list of lists, JSON, etc).

links=(("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl"))

The output that I need is a hierarchical JSON tree, which will be rendered with d3. There are discrete sub-trees in the data, which I will attach to a root node. So I need to recursively go though the links, and build up the tree structure. The furthest I can get is to iterate through all the people and append their children, but I can't figure out to do the higher order links (e.g. how to append a person with children to the child of someone else). This is similar to another question here, but I have no way to know the root nodes in advance, so I can't implement the accepted solution.

I am going for the following tree structure from my example data.

{
"name":"Root",
"children":[
    {
     "name":"Tom",
     "children":[
         {
         "name":"Dick",
         "children":[
             {"name":"Harry"}
         ]
         },
         {
          "name":"Larry"}
     ]
    },
    {
    "name":"Bob",
    "children":[
        {
        "name":"Leroy"
        },
        {
        "name":"Earl"
        }
    ]
    }
]
}

This structure renders like this in my d3 layout.

1Acgc.png

To identify the root notes you can unzip links and look for parents who are not children:

parents, children = zip(*links)
root_nodes = {x for x in parents if x not in children}

Then you can apply the recursive method:

import json

links = [("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl")]
parents, children = zip(*links)
root_nodes = {x for x in parents if x not in children}
for node in root_nodes:
    links.append(('Root', node))

def get_nodes(node):
    d = {}
    d['name'] = node
    children = get_children(node)
    if children:
        d['children'] = [get_nodes(child) for child in children]
    return d

def get_children(node):
    return [x[1] for x in links if x[0] == node]

tree = get_nodes('Root')
print json.dumps(tree, indent=4)

I used a set to get the root nodes, but if order is important you can use a list and remove the duplicates.


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK