Python – Genera un diccionario (árbol) a partir de una lista de tuplas

Tengo una lista siguiente: –

a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)] 

que es una lista de tuplas. Los elementos dentro de una tupla tienen el formato (Id, ParentId) Su nodo raíz siempre que Id == ParentId . La lista puede estar en cualquier orden de tuplas.

Quiero generar el siguiente diccionario usando la lista anterior de tuplas,

 output = [{ 'id': 1, 'children': [{ { 'id': 3, 'children': [{ { 'id': 5 }, { 'id': 4 }, { 'id': 6 } }] }, { 'id': 2 } }] }, { 'id': 7, 'children': [{ { 'id': 9 }, { 'id': 8 } }] }] 

es decir (en términos de gráficos- un forrest)

  1 7 / \ / \ 2 3 8 9 /|\ 4 5 6 

Mi salida final debería ser el diccionario dado arriba.

Intenté lo siguiente:

La solución que he probado es la siguiente:

 # set the value of nested dictionary. def set_nested(d, path, value): reduce(lambda d, k: d.setdefault(k, {}), path[:-1], d)[path[-1]] = value return d # returns the path of any node in list format def return_parent(list, child): for tuple in list: id, parent_id = tuple if parent_id == id == child: return [parent_id] elif id == child: return [child] + return_parent(list, parent_id) paths = [] temp = {} for i in a: id, parent_id = i temp[id] = {'id': id} path = return_parent(a, id)[::-1] paths.append(path) # List of path is created d = {} for path in paths: for n, id in enumerate(path): set_nested(d, path[:n + 1], temp[id]) # setting the value of nested dictionary. print d 

La salida que obtuve es

 { '1': { '3': { '6': { 'id': '6' }, '5': { 'id': '5' }, 'id': '3', '4': { '10': { 'id': '10' }, 'id': '4' } }, '2': { 'id': '2' }, 'id': '1' }, '7': { '9': { 'id': '9' }, '8': { 'id': '8' }, 'id': '7' } } 

Estoy cerca de eso, pero no puedo obtener el resultado exacto. Además, ¿hay alguna mejor solución mejor?

Aquí hay un enfoque más simple. (Editado según me di cuenta de la respuesta de Thomas, que los nodos pueden darse en cualquier orden): el Paso 1 crea los nodos (es decir, los agrega al diccionario de nodos), mientras que el Paso 2 crea la estructura primaria <-> secundaria.

Se hacen los siguientes supuestos: No hay ciclos (no está claro cuál sería el resultado esperado en tal caso, señala Garret R), no faltan bordes, no faltan raíces de árboles.

 a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)] # pass 1: create nodes dictionary nodes = {} for i in a: id, parent_id = i nodes[id] = { 'id': id } # pass 2: create trees and parent-child relations forest = [] for i in a: id, parent_id = i node = nodes[id] # either make the node a new tree or link it to its parent if id == parent_id: # 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) print forest 

EDITAR: ¿Por qué su solución no funciona como esperaba?

Aquí hay una sugerencia sobre el nivel superior: la salida que desea obtener es una lista de árboles. Sin embargo, la variable con la que está tratando con (d) debe ser un diccionario, porque en la función set_nested usted le aplica el método setdefaults.

Para hacer esto más fácil, definamos un objeto relacional simple:

 class Node(dict): def __init__(self, uid): self._parent = None # pointer to parent Node self['id'] = uid # keep reference to id # self['children'] = [] # collection of pointers to child Nodes @property def parent(self): return self._parent # simply return the object at the _parent pointer @parent.setter def parent(self, node): self._parent = node # add this node to parent's list of children node['children'].append(self) 

A continuación, defina cómo relacionar una colección de nodos entre sí. Usaremos un dict para mantener los punteros a cada nodo individual:

 def build(idPairs): lookup = {} for uid, pUID in idPairs: # check if was node already added, else add now: this = lookup.get(uid) if this is None: this = Node(uid) # create new Node lookup[uid] = this # add this to the lookup, using id as key if uid != pUID: # set this.parent pointer to where the parent is parent = lookup[pUID] if not parent: # create parent, if missing parent = Node(pUID) lookup[pUID] = parent this.parent = parent return lookup 

Ahora, toma tus datos de entrada y relacionalos:

 a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)] lookup = build(a) # can look at any node from here. for uid in [1, 3, 4]: parent = lookup[uid].parent if parent: parent = parent['id'] print "%s's parent is: %s" % (uid, parent) 

Finalmente, obtenga la salida: hay una buena posibilidad de que desee que los datos se arraiguen como una lista de árboles únicos, en lugar de como un diccionario, pero puede elegir lo que desee.

 roots = [x for x in lookup.values() if x.parent is None] # and for nice visualization: import json print json.dumps(roots, indent=4) 

flexible:

 [ { "id": 1, "children": [ { "id": 2, "children": [] }, { "id": 3, "children": [ { "id": 4, "children": [] }, { "id": 5, "children": [] }, { "id": 6, "children": [] } ] } ] }, { "id": 7, "children": [ { "id": 8, "children": [] }, { "id": 9, "children": [] } ] } ] 

Según sea necesario, esta solución funciona independientemente del orden de los nodos.

 a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)] b = [(8, 7), (5, 3), (2, 1), (1, 1), (3, 1), (7, 7), (4, 3), (6, 3), (9, 7)] def build_forest( nodelist ): forest = [] nodes = {} id = 'id' children = 'children' for node_id, parent_id in nodelist: #create current node if necessary if not node_id in nodes: node = { id : node_id } nodes[node_id] = node else: node = nodes[node_id] if node_id == parent_id: #add node to forrest forest.append( node ) else: #create parent node if necessary if not parent_id in nodes: parent = { id : parent_id } nodes[parent_id] = parent else: parent = nodes[parent_id] #create children if necessary if not children in parent: parent[children] = [] #add node to children of parent parent[children].append( node ) return forest print( build_forest( a ) ) print( build_forest( b ) )