How to sort a list into a hierarchy structure parent/child/grandchild?

Question

Sort the 'a' list like a parent/child hierarchy. where the first item is the ID, second is a description and the third is the parent ID.

a = [('222', 'Workroom', '111'),
('333', 'Setup Part', '222'),
('444', 'Scale', '222'),
('666', 'Workroom', '000'),
('888', 'Setup Part', '777'),
('777', 'Workroom', '666'),
('555', 'Workroom', '111'),
('111', 'Workroom', '000'),
('120', 'Workroom', '000'),
('100', 'Workroom', '000'),
('101', 'Workroom', '000'),
('110', 'Workroom', '101'),
('130', 'Workroom', '120')]

Desired output

a = [('100', 'Workroom', '000'),
('101', 'Workroom', '000'),
    ('110', 'Workroom', '101'),
('111', 'Workroom', '000'),
    ('555', 'Workroom', '111'),
    ('222', 'Workroom', '111'),
        ('333', 'Setup Part', '222'),
        ('444', 'Scale', '222'),
('120', 'Workroom', '000'),
    ('130', 'Workroom', '120'),
('666', 'Workroom', '000'),
    ('777', 'Workroom', '666'),
        ('888', 'Setup Part', '777'),]

What is the desired output? Depth-first? Breadth-first? Something completely different? Have a look at the [Sorting How To](https://docs.python.org/3.6/howto/sorting.html#sortinghowto) from the Python Documentation. — Christian König, May 15 '17 at 13:17
a = [('100', 'Workroom', '000'), ('101', 'Workroom', '000'), ('111', 'Workroom', '000'), ('555', 'Workroom', '111'), ('222', 'Workroom', '111'), ('333', 'Setup Part', '222'), ('444', 'Scale', '222'), ('110', 'Workroom', '101'), ('120', 'Workroom', '000'), ('130', 'Workroom', '120'), ('666', 'Workroom', '000'), ('777', 'Workroom', '666'), ('888', 'Setup Part', '777'),] — Miguel Rigau, May 15 '17 at 13:29
Should `('110', 'Workroom', '101'),` not come directly after `('101', 'Workroom', '000'),` and be indented one level in your visualisation? — Christian König, May 15 '17 at 13:37
take a look at: http://stackoverflow.com/questions/34964878/python-generate-a-dictionarytree-from-a-list-of-tuples. maybe a duplicate? — DSLima90, May 15 '17 at 13:40

score 2 · Accepted Answer · edited May 23 '17 at 12:18

Based on the correct answer from:

Python - Generate a dictionary(tree) from a list of tuples

You can try:

a = [('222', 'Workroom', '111'),
('333', 'Setup Part', '222'),
('444', 'Scale', '222'),
('666', 'Workroom', '000'),
('888', 'Setup Part', '777'),
('777', 'Workroom', '666'),
('555', 'Workroom', '111'),
('111', 'Workroom', '000'),
('120', 'Workroom', '000'),
('100', 'Workroom', '000'),
('101', 'Workroom', '000'),
('110', 'Workroom', '101'),
('130', 'Workroom', '120')]

# step 1: create all the nodes dictionary
nodes = {}
for i in a:
    id, desc, parent_id = i
    nodes[id] = { 'id': id, 'desc': desc }

# step 2: create trees and parent-child relations
forest = []
for i in a:
    id, desc, parent_id = i
    node = nodes[id]

    # either make the node a new tree or link it to its parent
    if parent_id == '000':
        # start a new tree in the forest
        forest.append(node)
    else:
        # add new_node as child to parent
        parent = nodes[parent_id]
        if not 'children' in parent:
            # ensure parent has a 'children' field
            parent['children'] = []
        children = parent['children']
        children.append(node)

# step 3: simple function to print then with indentation
def print_node(node,level=0):
    print("  "*level, node['id'], node['desc'])
    if node.get('children',False):
        for child in node['children']:
            print_node(child,level=level+1)

for node in forest:
    print_node(node,level=0)

In the answer we create a dictionary for all the nodes and then we add a children value for all of than, containing the sub nodes.

Note that i don't do any sorting, just create the forest and the nodes and print it. If you need you can sort by using the sorted function.

Tell me if that is what you want. Hope it helps...

How to sort a list into a hierarchy structure parent/child/grandchild?

1 Answers1