Recursively build a hierarchical JSON tree?

Question

I have a parent-child connection database. The data is as follows, but may be presented depending on what you want (dictionaries, list of lists, JSON, etc.).

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

The result I need is a hierarchical JSON tree that will be displayed using d3. There are discrete subtrees in the data that I will attach to the root of the node. Therefore, I need to follow the links recursively and build a tree structure. The most I can get is to iterate over all the people and add my children, but I cannot figure out how to use higher order links (for example, how to add a person with children to someone else's child). This seems like another question here , but I cannot know the root nodes in advance, so I cannot implement the decision made.

I am going to use 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 looks like this in my d3 layout.

Answer 1

To identify 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 the kit to get the root nodes, but if order is important, you can use the list and remove duplicates .

Answer 2

Try the following 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

If you want to format the data as a hierarchy in HTML / JS itself, look:

Create (multi-level) flare.json data format from flat json

If you have tons of data, web conversion will be faster since it uses shrinking functionality, while Python lacks functional programming.

BTW: I am also working on the same topic, that is, I am creating a resettable tree structure in d3.js. If you want to work, my email address is: [e-mail].