Python: create a nested dictionary from a list of parent child values

Question

Here is the input:

list_child_parent= [
    #first value is child, second is parent
    (0, 1),
    (1, 3),
    (8, 7),
    (3, 6),
    (4, 3),
    (5, 3)
]

The output needs to create a nested dictionary tree using these values. The tree will never be more than 6 levels deep.

For example:

output_dict = {
    6: {3: {1: {0: {}}, 4: {}, 5: {}}}, 7: {8: {}}
}

I have spent two days trying to accomplish this. I have tried writing functions to find where the key is in the tree and then add the new key after it, but I cannot produce code that can continue more than 3 levels. It's baffling and I feel that there is probably a standard library that can do this.

My experience level is low.

Answer 1

Not pretty and probably not Pythonic, but it should get you going:

#!/usr/bin/env python3

def make_map(list_child_parent):
    has_parent = set()
    all_items = {}
    for child, parent in list_child_parent:
        if parent not in all_items:
            all_items[parent] = {}
        if child not in all_items:
            all_items[child] = {}
        all_items[parent][child] = all_items[child]
        has_parent.add(child)

    result = {}
    for key, value in all_items.items():
        if key not in has_parent:
            result[key] = value
    return result

if __name__ == '__main__':
    list_child_parent = [
        #first value is child, second is parent
        (0, 1),
        (1, 3),
        (8, 7),
        (3, 6),
        (4, 3),
        (5, 3)
    ]

    actual = make_map(list_child_parent)

    expected = {
        6: {
            3: {
                1: {
                    0: {}
                },
                4: {},
                5: {}
            }
        },
        7: {
            8: {}
        }
    }
    print('OK' if expected == actual else 'FAIL')

Answer 2

This code will convert a tree from the given format into a tree structured dictionary. It's a lot of fluf, but it helps to keep track of what is happening. Performance wise it's pretty good.

LIST_CHILD_PARENTS = [                                                     
#first value is child, second is parent                                    
(0, 1),                                                                    
(1, 3),                                                                    
(8, 7),                                                                    
(3, 6),                                                                    
(4, 3),                                                                    
(5, 3)                                                                     
]                                                                          


class Node(object):                                                        
    def __init__(self, value):                    
        self.value = value
        # List of references to Node()'s.                                                
        self.child = []              
        # Reference to parent Node()                                                                           
        self.parent = None                                               
    def set_parent(self, parent):                                          
        self.parent = parent                                               
    def set_child(self, child):                                            
        self.child.append(child)                                           


def get_a_root(items):                                                     
    """Find a root node from items.                                        

    Grab some node and follow the parent pointers to a root.               
    """                                                                    
    cur_key = list(items.keys())[0]                                              
    while items[cur_key].parent is not None:                               
        cur_key = items[cur_key].parent.value                              
    parent = items[cur_key]                                                
    return parent                                                          

def extract_tree(items, root):                                             
    """Remove the tree from root in items.                                 
    """                                                                    
    cur_key = root.value                                                   
    this_node = items[cur_key]                                             
    if len(this_node.child) == 0:                                          
        items.pop(cur_key)                                                 
        return                                                             
    else:                                                                  
        for child in this_node.child:                                      
            extract_tree(items, child)                                     
        items.pop(cur_key)                                                  

def insert_from_root(tree, root):                                          
    """Insert the dictionary items from a tree.                            
    """                                                                    
    current = root                                                         
    if len(current.child) == 0:                                            
        tree[current.value] = {}                                           
        return                                                             
    else:                                                                  
        table = {}                                                         
        for child in current.child:                                        
            insert_from_root(table, child)                                 
        tree[current.value] = table                                                                                                

def build_graphs():                                                        
    """Map all input graphs into Node(object)'s.           

    Return: A hash table by value: Node(value, child, parent)              
    """                                                                    
    items = {}                                                             
    for child, parent in LIST_CHILD_PARENTS:                               
        if not child in items:                                       
            c_n = Node(child)  
            items[child] = c_n                 
        else:                                                              
            c_n = items[child]                                             
        if not parent in items:                                      
            p_n = Node(parent) 
            items[parent] = p_n                    
        else:                                                              
            p_n = items[parent]                                            
        p_n.set_child(c_n)                                                 
        c_n.set_parent(p_n)                                                                                       
    return items                                                           

def run_dict_builder():                                                    
    """Map the graphs from input and map into a dict.                                  

    Sequence:                                                              
        1- Map all graphs from input trees: list(tuple)             
        2- For each root node:                                             
            2A - Get a root node.                                      
            2B - Extract tree under this root from graphs list.                  
            2C - Insert the tree from this root into dict.                      
        3- Return the Dictionary Tree structure.                                                     
    """                                                                    
    graphs = build_graphs()                                                

    h_table = {}                                                           
    while len(graphs) > 0:                                                 
        root = get_a_root(graphs)                                          
        extract_tree(graphs, root)                                
        insert_from_root(h_table, root)                          
    return h_table                                                         

print(run_dict_builder())

Answer 3

Even though this question was answered a long time ago I wanted to give another solution that, to me, seems quite a bit cleaner. I mostly use this with lists of parents and children that get zipped together. For example

parents = [None, 1, 2, 3, 3, 2, 6, 6, 1, 9, 10, 10, 9, 13, 13]
children = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

# {1: {2: {3: {4: {}, 5: {}}, 6: {7: {}, 8: {}}}, 9: {10: {11: {}, 12: {}}, 13: {14: {}, 15: {}}}}}

Implementation:

def create_tree(node_map, root=None):
""" Given a list of tuples (child, parent) return the nested dictionary representation.
"""

def traverse(parent, node_map, seen):
    children = {}
    for edge in node_map:
        if edge[1] == parent and edge[0] not in seen:
            seen.add(edge[0])
            children[edge[0]] = traverse(edge[0], node_map, seen)
    return children

return traverse(root, node_map, {root})

Usage:

Example of root the exclusion.

We want the root to be "a" but is excluded because a root should be indicated as having no parent (None).

parents = ["a", "b", "c", "a", "b", "e", "e"]
children = ["b", "c", "d", "e", "f", "g", "h"]
edges = list(zip(children, parents))
test_tree = create_tree(edges, "a")
print(test_tree)
# result {'b': {'c': {'d': {}}, 'f': {}}, 'e': {'g': {}, 'h': {}}}

Adding the root with no parent designates the node as the root.

parents = [None, "a", "b", "c", "a", "b", "e", "e"]
children = ["a", "b", "c", "d", "e", "f", "g", "h"]
edges = list(zip(children, parents))
test_tree = create_tree(edges, None)
print(test_tree)
# result: {'a': {'b': {'c': {'d': {}}, 'f': {}}, 'e': {'g': {}, 'h': {}}}}

Multiple trees can be represented by having multiple roots.

parents = [None, "a", "b", "c", None, "b", "e", "e"]
children = ["a", "b", "c", "d", "e", "f", "g", "h"]
edges = list(zip(children, parents))
test_tree = create_tree(edges, None)
print(test_tree)
# result: {'a': {'b': {'c': {'d': {}}, 'f': {}}}, 'e': {'g': {}, 'h': {}}}

To get the desired output from the original post we find and designate the roots.

edges = [
    #first value is child, second is parent
    (0, 1),
    (1, 3),
    (8, 7),
    (3, 6),
    (4, 3),
    (5, 3)
]
roots = {edge[1] for edge in edges} - {edge[0] for edge in edges}
edges += [(root, None) for root in roots]
test_tree = create_tree(edges, None)
print(test_tree)
# result: {6: {3: {1: {0: {}}, 4: {}, 5: {}}}, 7: {8: {}}}