multi nested dictionary from tuples in python

Question

I have this list of tuples

list_of_tuples = [('0', '1'), ('1', '1.1'), ('1', '1.2'), ('1', '1.3'), ('1', '1.4'), ('0', '3'), ('3', '3.1'), ('3', '3.2'), ('3', '3.3'), ('3', '3.4'), ('3', '3.5'), ('0', '4'), ('4', '4.1'), ('4', '4.2'), ('4', '4.3'), ('4', '4.4'), ('4', '4.5'), ('4', '4.6'), ('4', '4.7'), ('4', '4.8'), ('4', '4.9'), ('0', '5'), ('5', '5.1'), ('5', '5.2'), ('5', '5.3'), ('5', '5.4'), ('0', '6'), ('6', '6.1'), ('6', '6.2'), ('6', '6.3'), ('6', '6.4'), ('6', '6.5'), ('0', '7'), ('7', '7.1'), ('7', '7.2'), ('7', '7.3'), ('7.3', '7.3.1'), ('7.3', '7.3.2'), ('7.3', '7.3.3'), ('0', '8'), ('8', '8.1.1'), ('8', '8.1.2'), ('8', '8.2'), ('0', '9'), ('9', '9.1'), ('9', '9.2'), ('0', '10'), ('10', '10.1'), ('10', '10.2'), ('10', '10.3'), ('10.3', '10.3.2'), ('10.3', '10.3.3'), ('10.3', '10.3.4'), ('10.3', '10.3.5'), ('10.3', '10.3.6')

The first value in the tuple is the parent and the second is the value.

(parent,child)

i want the output to be like this.

{ '0':
     {'1':
         {'1.1':None,
          '1.2':None......
         }
     {'3':
         {'3.1':None/[]..
         }
     }
}

i can add it to the dictionary but i want it to be nested like a tree with multiple children.

d = defaultdict(list)
for k, v in h:
   d[k].append(v)

Any help is appreciated.

Answer 1

I'm going to whip up a quick tree class that can take this input and build a tree with it, then I'm going to write a method for that class that converts them back to dictionaries

class Tree:
    def __init__(self, name, parent=None): #parent is None to detect root
        self.name = name
        self.parent = parent
        self.children = []    
    def add(self, target , child):
        '''
        Does DFS until it finds Tree with name target.  Creates a Tree(child)
        as child of Tree name
        '''
        if self.name == target:
            self.children.append(Tree(child, self))
            return True
        else:
            for subtree in self.children:
                if subtree.add(target, child):
                    return True
        if self.parent:
            return False
        raise ValueError('Bad Parent no such node {}'.format(target))    
    def dictify(self):
        d = {}
        for child in self.children:
          d.update(child.dictify())
        return {self.name: d}

list_of_tuples = [('0', '1'), ('1', '1.1'), ('1', '1.2'), ('1', '1.3'), ('1', '1.4'), ('0', '3'), ('3', '3.1'), ('3', '3.2'), ('3', '3.3'), ('3', '3.4'), ('3', '3.5'), ('0', '4'), ('4', '4.1'), ('4', '4.2'), ('4', '4.3'), ('4', '4.4'), ('4', '4.5'), ('4', '4.6'), ('4', '4.7'), ('4', '4.8'), ('4', '4.9'), ('0', '5'), ('5', '5.1'), ('5', '5.2'), ('5', '5.3'), ('5', '5.4'), ('0', '6'), ('6', '6.1'), ('6', '6.2'), ('6', '6.3'), ('6', '6.4'), ('6', '6.5'), ('0', '7'), ('7', '7.1'), ('7', '7.2'), ('7', '7.3'), ('7.3', '7.3.1'), ('7.3', '7.3.2'), ('7.3', '7.3.3'), ('0', '8'), ('8', '8.1.1'), ('8', '8.1.2'), ('8', '8.2'), ('0', '9'), ('9', '9.1'), ('9', '9.2'), ('0', '10'), ('10', '10.1'), ('10', '10.2'), ('10', '10.3'), ('10.3', '10.3.2'), ('10.3', '10.3.3'), ('10.3', '10.3.4'), ('10.3', '10.3.5'), ('10.3', '10.3.6')]

root = Tree('0')
for parent, child in list_of_tuples:
  root.add(parent, child)
print(root.dictify())

Here is is with pprint (pretty printing)

{'0': {'1': {'1.1': {}, '1.2': {}, '1.3': {}, '1.4': {}},
       '10': {'10.1': {},
              '10.2': {},
              '10.3': {'10.3.2': {},
                       '10.3.3': {},
                       '10.3.4': {},
                       '10.3.5': {},
                       '10.3.6': {}}},
       '3': {'3.1': {}, '3.2': {}, '3.3': {}, '3.4': {}, '3.5': {}},
       '4': {'4.1': {},
             '4.2': {},
             '4.3': {},
             '4.4': {},
             '4.5': {},
             '4.6': {},
             '4.7': {},
             '4.8': {},
             '4.9': {}},
       '5': {'5.1': {}, '5.2': {}, '5.3': {}, '5.4': {}},
       '6': {'6.1': {}, '6.2': {}, '6.3': {}, '6.4': {}, '6.5': {}},
       '7': {'7.1': {},
             '7.2': {},
             '7.3': {'7.3.1': {}, '7.3.2': {}, '7.3.3': {}}},
       '8': {'8.1.1': {}, '8.1.2': {}, '8.2': {}},
       '9': {'9.1': {}, '9.2': {}}}}

If you want those empty dicts to be None just change dictify to return {self.name: d if d else None}

Edit: schwobaseggl makes a good point about insertion complexity. Here is a version of the Tree class that takes advantage of ordered inputs

class Tree:
    def __init__(self, name, parent=None): #parent is None to detect root
        self.name = name
        self.parent = parent
        self.children = []        
    def add(self, target , child):
        '''
        Accepts additions in DFS order.  Relies on the fact that every node will
        be the direct descendant of the previous node or one of its ancestors.
        '''
        if self.name == target:
            kiddo = Tree(child, self)
            self.children.append(kiddo)
            return kiddo
        elif self.parent:
            return self.parent.add(target, child)
        else:
            raise ValueError('Bad Parent no such node {}'.format(target))    
    def dictify(self):
        d = {}
        for child in self.children:
          d.update(child.dictify())
        return {self.name: d}
list_of_tuples = [('0', '1'), ('1', '1.1'), ('1', '1.2'), ('1', '1.3'), ('1', '1.4'), ('0', '3'), ('3', '3.1'), ('3', '3.2'), ('3', '3.3'), ('3', '3.4'), ('3', '3.5'), ('0', '4'), ('4', '4.1'), ('4', '4.2'), ('4', '4.3'), ('4', '4.4'), ('4', '4.5'), ('4', '4.6'), ('4', '4.7'), ('4', '4.8'), ('4', '4.9'), ('0', '5'), ('5', '5.1'), ('5', '5.2'), ('5', '5.3'), ('5', '5.4'), ('0', '6'), ('6', '6.1'), ('6', '6.2'), ('6', '6.3'), ('6', '6.4'), ('6', '6.5'), ('0', '7'), ('7', '7.1'), ('7', '7.2'), ('7', '7.3'), ('7.3', '7.3.1'), ('7.3', '7.3.2'), ('7.3', '7.3.3'), ('0', '8'), ('8', '8.1.1'), ('8', '8.1.2'), ('8', '8.2'), ('0', '9'), ('9', '9.1'), ('9', '9.2'), ('0', '10'), ('10', '10.1'), ('10', '10.2'), ('10', '10.3'), ('10.3', '10.3.2'), ('10.3', '10.3.3'), ('10.3', '10.3.4'), ('10.3', '10.3.5'), ('10.3', '10.3.6')]

root = Tree('0')
curr = root
for parent, child in list_of_tuples:
  curr = curr.add(parent, child)
print(root.dictify())

Answer 2

Patrick's solution is generic and object-oriented. However, it is O(N^2) (N being the number of edges) because it traverses the entire tree for each edge. Since you know that you get the edges in depth-first order, you can save a lot (for large trees: a lot lot!) of time by memorizing your current position in the tree, inserting right where you are, and going back up the tree if needed.

The following is more concise and O(N) without the additional overhead of your own classes and extra-conversion:

from pprint import pprint

d = {}
crnt = d  # memo the crnt subtree
stck = []  # stack of (sub)trees along current path
for k, v in list_of_tuples:
  while stck and k not in crnt:
    crnt = stck.pop()
  if k not in crnt:
    crnt[k] = {}
  stck.append(crnt)
  crnt = crnt[k]
  crnt[v] = {}

pprint(d)

{'0': {'1': {'1.1': {}, '1.2': {}, '1.3': {}, '1.4': {}},
       '10': {'10.1': {},
              '10.2': {},
              '10.3': {'10.3.2': {},
                       '10.3.3': {},
                       '10.3.4': {},
                       '10.3.5': {},
                       '10.3.6': {}}},
       '3': {'3.1': {}, '3.2': {}, '3.3': {}, '3.4': {}, '3.5': {}},
       '4': {'4.1': {},
             '4.2': {},
             '4.3': {},
             '4.4': {},
             '4.5': {},
             '4.6': {},
             '4.7': {},
             '4.8': {},
             '4.9': {}},
       '5': {'5.1': {}, '5.2': {}, '5.3': {}, '5.4': {}},
       '6': {'6.1': {}, '6.2': {}, '6.3': {}, '6.4': {}, '6.5': {}},
       '7': {'7.1': {},
             '7.2': {},
             '7.3': {'7.3.1': {}, '7.3.2': {}, '7.3.3': {}}},
       '8': {'8.1.1': {}, '8.1.2': {}, '8.2': {}},
       '9': {'9.1': {}, '9.2': {}}}}