Sorting JSON objects (objects) into a hierarchy

Question

I need to sort the JSON array in a hierarchy, here is my JSON file, it never ordered, but followed the structure:

{ "name":"Folder 2", "id":"zRDg", "parent":"OY00", "type":"folder" }, { "name":"Folder 1", "id":"OY00", "type":"folder" }, { "name":"Folder 3", "id":"ZDE1", "type":"folder" }, { "name":"DX00025.jpg", "id":"9Xdd", "parent":"OY00", "type":"jpeg" } 

The structure in this JSON file is as follows:

 { "name":"Folder 1", "id":"OY00", "type":"folder", "children": [{ "name":"Folder 2", "id":"zRDg", "type":"folder" }, { "name":"DX00025.jpg", "id":"9Xdd", "type":"jpeg" }] }, { "name":"Folder 3", "id":"ZDE1", "type":"folder" } 

I can't figure it out, since I'm new to python, my start (wrong):

 for index,item in result: if item['parent']: for item2 in result: if item2['id'] == item['parent']: item['children'] = item2 brake 

This is normal, but the problem is that it is not correct python , folder1 / folder2 / folder3 / wont work for this, I need a recursive function . I should also include changes to this structure, it can be a folder with a folder and files with a folder / folders in any combination.

Answer 1

 myJson = [ { "name":"Folder 2", "id":"zRDg", "parent":"OY00", "type":"folder" }, { "name":"Folder 1", "id":"OY00", "type":"folder" }, { "name":"Folder 3", "id":"ZDE1", "type":"folder" }, { "name":"DX00025.jpg", "id":"9Xdd", "parent":"OY00", "type":"jpeg" } ] #this creates a dictionary that maps id names to JSON items. #ex. itemsKeyedById["9Xdd"] gives the jpg item with id "9Xdd" itemsKeyedById = {i["id"]: i for i in myJson} #iterate through each item in the `myJson` list. for item in myJson: #does the item have a parent? if "parent" in item: #get the parent item parent = itemsKeyedById[item["parent"]] #if the parent item doesn't have a "children" member, #we must create one. if "children" not in parent: parent["children"] = [] #add the item to its parent "children" list. parent["children"].append(item) #filter out any item that has a parent. #They don't need to appear at the top level, #since they will appear underneath another item elsewhere. topLevelItems = [item for item in myJson if "parent" not in item] print topLevelItems 

Output (with padding):

 [ { 'name': 'Folder 1', 'id': 'OY00', 'type': 'folder', 'children': [ { 'name': 'Folder 2', 'id': 'zRDg', 'parent': 'OY00', 'type': 'folder' }, { 'name': 'DX00025.jpg', 'id': '9Xdd', 'parent': 'OY00', 'type': 'jpeg' } ] }, { 'name': 'Folder 3', 'id': 'ZDE1', 'type': 'folder' } ] 

It also works with elements nested at several depths. Input Example:

 myJson = [ { "name":"TopLevel folder", "id":"0", "type":"folder", }, { "name":"MidLevel folder", "id":"1", "type":"folder", "parent":"0" }, { "name":"Bottom Level folder", "id":"2", "type":"folder", "parent":"1" }, { "name":"Vacation Picture", "id":"3", "type":"jpg", "parent":"2" }, ] 

Output:

 [ { 'type': 'folder', 'name': 'TopLevel folder', 'id': '0', 'children': [ { 'type': 'folder', 'name': 'MidLevel folder', 'parent': '0', 'id': '1', 'children': [ { 'type': 'folder', 'name': 'Bottom Level folder', 'parent': '1', 'id': '2', 'children': [ { 'type': 'jpg', 'name': 'Vacation Picture', 'parent': '2', 'id': '3' } ] } ] } ] } ] 

Answer 2

How about using something like the Python networkx library?

 import json #networkx is a library for working with networks and trees import networkx as nx #The json_graph routines print out JSONic representations of graphs and trees #http://networkx.github.com/documentation/latest/reference/readwrite.json_graph.html from networkx.readwrite import json_graph dd='[{ "name":"Folder 2", "id":"zRDg", "parent":"OY00", "type":"folder"},{ "name":"Folder 1", "id":"OY00", "type":"folder"},{"name":"Folder 3", "id":"ZDE1", "type":"folder"},{ "name":"DX00025.jpg", "id":"9Xdd", "parent":"OY00", "type":"jpeg"}]' d=json.loads(dd) #A tree is a directed graph - create one with a dummy root DG=nx.DiGraph() DG.add_node('root') #Construct the tree as a directed graph and annotate the nodes with attributes #Edges go from parent to child for e in d: DG.add_node(e['id'],name=e['name'],type=e['type']) #If there a parent, use it... if 'parent' in e: DG.add_edge(e['parent'],e['id']) #else create a dummy parent from the dummy root else: DG.add_edge('root',e['id']) #Get the tree as JSON data = json_graph.tree_data(DG,root='root') #and dump the data from the dummy root children down... json.dumps(data['children']) ''' '[{"children": [{"type": "folder", "name": "Folder 2", "id": "zRDg"}, {"type": "jpeg", "name": "DX00025.jpg", "id": "9Xdd"}], "type": "folder", "name": "Folder 1", "id": "OY00"}, {"type": "folder", "name": "Folder 3", "id": "ZDE1"}]' ''' 

Answer 3

My solution for this case looks something like this:

 data = INPUT_LIST class Item: def __init__(self, _id, name, type, parent): self._id = _id self.name = name self.type = type self.parent = parent self.children = [] def get_dict(self): return { 'id': self._id, 'name': self.name, 'type': self.type, 'children': [child.get_dict() for child in self.children] } lookup = dict((item['id'], Item(item['id'], item['name'], item['type'], item['parent'] if 'parent' in item else None)) for item in data) root = [] for _id, item in lookup.items(): if not item.parent: root.append(item) else: lookup[item.parent].children.append(item) dict_result = [item.get_dict() for item in root] 

Answer 4

You have a graph (perhaps just a tree) with connections between nodes represented by the parent key. This is called an adjacency list .

You want to create a tree structure with links to other nodes using the children key, which is a list of other nodes.

To convert an adjacency list to a tree, you first need to get the node method by its identifier, so the first step is to create a dict of each node with a key by id.

Then you need to go through the list again and add the children to their parents.

Finally, create a list of nodes without parents (root nodes).

Note that you do not need a recursive algorithm at all.

We can combine some of these steps so that we don’t go through the list several times. Code below:

 def nest_list(L): """Modify list of associative dicts into a graph and return roots of graph Association is via a 'parent' key indicating a corresponding 'id'. Items in the list *will be modified*. Children will be placed in a list for a 'children' key Items without children will have no 'children' key 'parent' keys will be removed. Returned list is the full list of items which are not children of any other items. """ idx = {} children = [] root = [] # first pass: index items by id # if the item has no parents, put it in the 'root' list # otherwise add it to the 'children' list which we will # process in a second pass for item in L: idx[item['id']] = item if 'parent' in item: children.append(item) else: root.append(item) # second pass: find the parents of our children for child in children: parent = idx[child['parent']] del child['parent'] try: # retrieve the list of children for this # parent childlist = parent['children'] except KeyError: # this item has received no children so far # so we need to make a 'children' key and list # for it. parent['children'] = childlist = [] # append this child to the parent list of children childlist.append(child) #all done: return new root list return root 

Code in action:

 oldlist = [{ "name":"Folder 2", "id":"zRDg", "parent":"OY00", "type":"folder" }, { "name":"Folder 1", "id":"OY00", "type":"folder" }, { "name":"Folder 3", "id":"ZDE1", "type":"folder" }, { "name":"DX00025.jpg", "id":"9Xdd", "parent":"OY00", "type":"jpeg" }] expected = [{ "name":"Folder 1", "id":"OY00", "type":"folder", "children": [{ "name":"Folder 2", "id":"zRDg", "type":"folder" }, { "name":"DX00025.jpg", "id":"9Xdd", "type":"jpeg" }] }, { "name":"Folder 3", "id":"ZDE1", "type":"folder" }] from pprint import pprint newlist = nest_list(oldlist) pprint(newlist) assert newlist == expected