Solución:
Aquí hay un enfoque más simple. (Editado como me di cuenta de la respuesta de Thomas que los nodos se pueden dar 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 padre <-> hijos.
Se hacen las siguientes suposiciones: Sin ciclos (no está claro cuál sería el resultado esperado en tal caso, señaló Garret R), sin bordes faltantes, sin raíces de árboles faltantes.
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 pista con respecto al nivel superior: El resultado que desea obtener es un lista de árboles. Sin embargo, la variable con la que está tratando (d) debe ser un diccionario, porque en la función set_nested le aplica el método setdefaults.
Para facilitar esto, 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 contener 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, tome sus datos de entrada y relacione:
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, obtener el resultado: es muy probable 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": []
}
]
} ]