Recursively build hierarchical JSON tree?

Question

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.

Answer 1

To identify the root nodes 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.

Answer 2

Try follwing code:

import json

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

name_to_node = {}
root = {'name': 'Root', 'children': []}
for parent, child in links:
    parent_node = name_to_node.get(parent)
    if not parent_node:
        name_to_node[parent] = parent_node = {'name': parent}
        root['children'].append(parent_node)
    name_to_node[child] = child_node = {'name': child}
    parent_node.setdefault('children', []).append(child_node)

print json.dumps(root, indent=4)

Answer 3

In case you want to format the data as a hierarchy in the HTML/JS itself, take a look at:

Generate (multilevel) flare.json data format from flat json

In case you have tons of data the Web conversion will be faster since it uses the reduce functionality while Python lacks functional programming.

BTW: I am also working on the same topic i.e. generating the collapsible tree structure in d3.js. If you want to work along, my email is: erprateek.vit@gmail.com.