Sorting JSON object(s) into a Hierarchy

Question

I need to sort out a JSON array into a Hierarchy, here my JSON file, it's never ordered but follow 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"
}

Into this JSON file, the structure is like this:

{
  "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 really figure it out, as 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 ok, but the problem is it not correct python, folder1/folder2/folder3/ wont work for this, i need a recursive function. I should also include this structure changes, it can be folder withing folder and files withing folder/folders any combination.

It looks like you already know how to implement `setFolder`. What's stopping you from implementing the rest? — shx2, Mar 23 '13 at 14:51

Kevin · Accepted Answer · 2013-03-26T13:16:33.620

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's "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 indentation added by me):

[
    {
        '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 items that are nested more than one deep. Example input:

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'
                            }
                        ] 
                    }
                ]
            }
        ]
    }
]

Well i can confirm it works, well but now i can't understand it, if you can explain the lines of code in detail you will get the ***150*** :) Btw new to python, go easy, thanks in advance. — Kivylius, Mar 26 '13 at 13:05
I commented the lines. Is there anything in particular you don't understand? — Kevin, Mar 26 '13 at 14:18

score 3 · Answer 2 · edited Mar 29 '13 at 15:02

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's 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's 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"}]'
'''

score 2 · Answer 3 · answered Mar 27 '13 at 05:41

My solution for this case is 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]

score 2 · Answer 4 · answered Mar 28 '13 at 20:33

What you have here is a graph (probably just a tree) with connections between nodes represented by a parent key. This is known as an adjacency list.

You want to produce a tree structure with links to other nodes through a children key which is a list of other nodes.

To convert an adjacency list into a tree, you first need to have a way to retrieve a node by its id, so the first step is to create a dict of every node, keyed by id.

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

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

Note that you don't need a recursive algorithm at all.

We can combine some of these steps to avoid going through the list multiple 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's 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

But what about folder withing folders withing folder and a real live dynamic Hierarchy, This example completely ignores folder 4 link: http://ideone.com/fkgYGx — Kivylius, Mar 28 '13 at 22:28
Because "Folder 4" is it's own parent! Do you really want to allow that? You could add a special case for `item['id'] == item['parent']`, but honestly I have no idea how that should be handled. — Francis Avila, Mar 28 '13 at 22:30
My silly mistake, wrong copy paste, sorry. this then successfully support nesting of items, what i dont get is how this works, where/how do's the nesting occur, you could have /folder/folder/folder/folder/file.jsp and this code seems to work but i dont understand where/how the nesting part occurs. — Kivylius, Mar 28 '13 at 22:35
The nesting part occurs in the second loop, specifically `childlist.append(child)`, as explained in the code comments. — Francis Avila, Mar 28 '13 at 22:36

Sorting JSON object(s) into a Hierarchy

4 Answers4

Linked