Building a list with a parent-child dependency

Question

I have a list of dicts that looks something like this:

list = [{'parent': u'#5963','id': 5962},{'parent': u'','id': 5963}, 
{'parent': u'#5963', 'id': 5964}, {'parent': u'#5966', 'id': 5967}, 
{'parent': u'#5963','id': 5966}, {'parent': u'#5962','id': 5968} ]

The actual dicts are a bit more complex - they have more keys and values.

As you can see - every dict has a 'parent' key, which tells us elements parent's id and an 'id' key.

Now the question is: is it possible to build a new list (or sort this one) in a way that all dicts are placed in a parent-child way?

So the new dict will be:

[{'parent': u'','id': 5963},{'parent': u'#5963','id': 5962}, 
{'parent': u'#5962','id': 5968}, {'parent': u'#5963', 'id': 5964},
{'parent': u'#5963','id': 5966}, {'parent': u'#5966', 'id': 5967} ]

PS: There maybe no root elements (elements with 'parent' key = '')
PPS: Parent element may have more than 1-2 levels of children

I don't get it. What do yo mean with "parent-child way"? Or another question: what are you trying to accomplish? I'm pretty sure you could use a tree to get rid of these problems… — tamasgal
I'm getting the first list as a result of a SQL query. Then it is being passed to a template in order to build a table. Template uses list elements to create table's rows. What I need now - it to rearrange this list in a way the resulting table would have an hierarchy, thus parent-child way. — konart

Guillaume Guillaume · Accepted Answer · 2013-07-05T09:59:58

You can't do that with a straight sort, first build a tree from your list. You need two informations: the list of top nodes (either node with no parent or child with non existing parent) in the tree and the parent/children relation:

def build_tree(l):
    exists = set(map(lambda x : x['id'], l))

    tops = []
    children = {}
    for e in l:
        parent = e['parent']
        if not parent:
            tops.append(e)
            continue

        parent = int(parent[1:])
        if parent not in exists:
            tops.append(e)
            continue

        if parent in children:
            children[parent].append(e)
        else:
            children[parent] = [ e ]

    return children, tops

Then do a depth-first traversal of that tree with a recursive function:

def build_list(children, top):
    l = [ top ]
    if top['id'] in children:
        for child in children[top['id']]:
            l += build_list(children, child)
    return l

The first function give you the children/relation structure while the second let you build a list for each possible top node.

Now you can sort your list using those two functions:

l = [{'parent': u'#5963','id': 5962},{'parent': u'','id': 5963},
{'parent': u'#5963', 'id': 5964}, {'parent': u'#5966', 'id': 5967},
{'parent': u'#5963','id': 5966}, {'parent': u'#5962','id': 5968} ]
children, tops = build_tree(l)
for top in tops:
    print build_list(children, top)
# outputs : [{'id': 5963, 'parent': u''}, {'id': 5962, 'parent': u'#5963'},
# {'id': 5968, 'parent': u'#5962'}, {'id': 5964, 'parent': u'#5963'},
# {'id': 5966, 'parent': u'#5963'}, {'id': 5967, 'parent': u'#5966'}]

If you remove the node 5963, that will give :

[{'id': 5962, 'parent': u'#5963'}, {'id': 5968, 'parent': u'#5962'}]
[{'id': 5964, 'parent': u'#5963'}]
[{'id': 5966, 'parent': u'#5963'}, {'id': 5967, 'parent': u'#5966'}]

Building a list with a parent-child dependency

1 Answers