Recursively build hierarchical JSON tree?
Solution 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.
Solution 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)
Andrew Barr
I am a paleoecologist and paleoanthropologist. I use R for data analysis, visualization, and statistics. I use python (django) for web development.
Updated on July 25, 2022Comments
-
Andrew Barr almost 2 years
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.
-
Andrew Barr almost 11 yearsA bit of a wrinkle....your code doesn't work as expected with more links: for example, when I try it with these links,Tom appears multiple times! links=(("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Tom","Hurbert"),("Tom","Neil"),("Bob","Leroy"),("Bob","Earl"),("Tom","Reginald"))