Multiuser tuple dictionary 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 result 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 several children.

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

Any help is appreciated.

Answer 1

I'm going to hack a quick tree class that can take this input and build a tree with it, then I'm going to write a method for this class that will convert 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()) 

There is a pprint (pretty print version)

 {'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 these empty dicts to be None , just change dictify to return {self.name: d if d else None}

Edit: schwobaseggl makes a good conclusion about the complexity of the insert. Here is a version of the Tree class that uses 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, this is O(N^2) ( N is the number of edges) because it intersects the entire tree for each edge. Since you know that you get the edges in depth, you can save a lot (for large trees: a lot!) Of time, remembering your current position on the tree, inserting it right where you are, and returning the tree if necessary.

The following is more concise and O(N) without the additional overhead of your own classes and additional 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': {}}}}