Crear un árbol json de la lista csv en python

recursion tree

Question

Estoy intentando construir una jerarquía json a partir de una tabla simple en python.

Los datos aparecen como los siguientes:

id parent name
1 10 test-name-1
2 10 test-name-2
3 5 test-name-3
4 none test-name-4
5 10 test-name-5
6 none test-name-6
7 1 test-name-7
8 1 test-name-8
9 8 test-name-9
10 4 test-name-10

y estoy buscando un resultado como este:

{"$4":{"name":"test-name-4","children":{
"$10":{"name":"test-name-10","children":{
"$1":{"name":"test-name-1","children":{
"$7":{"name":"test-name-7","children":{}},
"$8":{"name":"test-name-8","children":{
"$9":{"name":"test-name-9","children":{}}}}}},
"$2":{"name":"test-name-2","children":{}},
"$5":{"name":"test-name-5","children":{
"$3":{"name":"test-name-3","children":{}}}}}}}},
"$6":{"name":"test-name-6","children":"test-name-6"}}

No tengo idea de cuántas "hojas" habrá o "raíces", o en qué orden aparecerán las filas del csv. Mi pregunta es, ¿hay alguna forma de que pueda construir recursivamente un diccionario / lista desde un nodo secundario? hasta el padre? ¿Cómo puedo producir un árbol jerárquico a partir de las piezas de "hoja" del árbol en python?

¡Gracias por la ayuda!

Answer 1

La respuesta dada no funcionó para mí en Python 3.6 porque Dict.Dict ha quedado en desuso. Así que hice algunos cambios para que funcione y generalicé un poco al permitir que el usuario especifique columnas para child_id, parent_id y child name a través de la línea de comandos. Vea a continuación (estoy recién aprendiendo y estoy seguro de que esto podría mejorarse, pero funciona para mis propósitos).

""" Converts a CSV file with Parent/Child Hierarchy to a hierarchical JSON file for front-end processing (javascript/DS)
USAGE: csv2json.py <somefile.csv> a b c (column nrs of a=child_id, b=parent-id, c=name(of child))
ROOT of hierarchy should contain child_id and parent_id = ''none'' or blank. name must exist """
import sys
import json
import csv
#import UserDict
from collections import UserDict
class Node(object):
def __init__(self, child_id, parent_id, name):
self.child_id = child_id
self.parent_id = parent_id
self.children = []
self.name = name
class NodeDict(UserDict):
def addNodes(self, nodes):
""" Add every node as a child to its parent_id by doing two passes."""
for i in (1, 2):
for node in nodes:
self.data[node.child_id] = node
if node.parent_id in self.data.keys():
if (node.parent_id != "none" or node.parent_id != "") and node not in self.data[node.parent_id].children:
self.data[node.parent_id].children.append(node)
class NodeJSONEncoder(json.JSONEncoder):
def default(self, node):
if type(node) == Node:
return {"name":node.name, "children":node.children}
raise TypeError("{} is not an instance of Node".format(node))
if __name__ == "__main__":
nodes = []
with open(sys.argv[1], ''r'') as f:
reader = csv.reader(f)
for row in reader:
if not row[int(sys.argv[4])] : #skip if no name/label exists
continue
child_id, parent_id, name = row[int(sys.argv[2])] , row[int(sys.argv[3])] , row[int(sys.argv[4])]
nodes.append(Node(child_id, parent_id, name))
nodeDict = NodeDict()
nodeDict.addNodes(nodes)
rootNodes = [node for child_id, node in nodeDict.items()
if (node.parent_id == "none" or node.parent_id == "")]
for rootNode in rootNodes:
print(NodeJSONEncoder().encode(rootNode))

Answer 2

Para asignar todos los nodos secundarios a su principal, puede hacer dos pasadas sobre la lista de nodos. El primer pase agrega cada nodo a un UserDict . En el segundo paso, se garantiza que el elemento primario de cada nodo está en el UserDict por lo que el nodo se puede agregar a los elementos UserDict de su elemento principal.

Para serializar a JSON se puede usar un JSONEncoder .

#!/usr/bin/env python
import sys
import json
import UserDict
class Node(object):
def __init__(self, nid, parent, name):
self.nid = nid
self.parent = parent
self.children = []
self.name = name
class NodeDict(UserDict.UserDict):
def addNodes(self, nodes):
""" Add every node as a child to its parent by doing two passes."""
for i in (1, 2):
for node in nodes:
self.data[node.nid] = node
if node.parent in self.data.keys():
if node.parent != "none" and
node not in self.data[node.parent].children:
self.data[node.parent].children.append(node)
class NodeJSONEncoder(json.JSONEncoder):
def default(self, node):
if type(node) == Node:
return {"nid":node.nid, "name":node.name, "children":node.children}
raise TypeError("{} is not an instance of Node".format(node))
if __name__ == "__main__":
nodes = []
with open(sys.argv[1]) as f:
for row in f.readlines()[1:]:
nid, parent, name = row.split()
nodes.append(Node(nid, parent, name))
nodeDict = NodeDict()
nodeDict.addNodes(nodes)
rootNodes = [node for nid, node in nodeDict.items()
if node.parent == "none"]
for rootNode in rootNodes:
print NodeJSONEncoder().encode(rootNode)

Resultado:

{"name": "test-name-4", "nid": "4", "children":[
{"name": "test-name-10", "nid": "10", "children":[
{"name": "test-name-1", "nid": "1", "children":[
{"name": "test-name-7", "nid": "7", "children": []},
{"name": "test-name-8", "nid": "8", "children":[
{"name": "test-name-9", "nid": "9", "children": []}]}]},
{"name": "test-name-2", "nid": "2", "children": []},
{"name": "test-name-5", "nid": "5", "children":[
{"name": "test-name-3", "nid": "3", "children": []}]}]}]}
{"name": "test-name-6", "nid": "6", "children": []}

Answer 3

También tengo una solución basada en 2 bucles (1 en caché, 1 en compilación), sin codificador JSON, y que proporciona exactamente la salida que requirió:

>>> import re
>>> from collections import defaultdict
>>> parents = defaultdict(list)
>>> for i, line in enumerate(file_.split(''/n'')):
if i != 0 and line.strip():
id_, parent, name = re.findall(r''[/d/w-]+'', line)
parents[parent].append((id_, name))
>>> parents
defaultdict(<type ''list''>, {''10'': [(''1'', ''test-name-1''), (''2'', ''test-name-2''), (''5'', ''test-name-5'')], ''none'': [(''4'', ''test-name-4''), (''6'', ''test-name-6'')], ''1'': [(''7'', ''test-name-7''), (''8'', ''test-name-8'')], ''5'': [(''3'', ''test-name-3'')], ''4'': [(''10'', ''test-name-10'')], ''8'': [(''9'', ''test-name-9'')]})

OK, ahora tenemos nuestro caché, la función recursiva construye fácilmente el resultado que nos gustaría:

>>> def build_tree(d, val):
return {''$'' + id_: {''name'': name, ''children'': build_tree(d, id_)} for id_, name in d[val]}

Solo tenemos que llamarlo en el dict construido previamente, con el valor ''none'' que es la raíz del árbol:

>>> from pprint import pprint
>>> pprint(build_tree(parents, ''none''))
{''$4'': {''children'': {''$10'': {''children'': {''$1'': {''children'': {''$7'': {''children'': {},
''name'': ''test-name-7''},
''$8'': {''children'': {''$9'': {''children'': {},
''name'': ''test-name-9''}},
''name'': ''test-name-8''}},
''name'': ''test-name-1''},
''$2'': {''children'': {},
''name'': ''test-name-2''},
''$5'': {''children'': {''$3'': {''children'': {},
''name'': ''test-name-3''}},
''name'': ''test-name-5''}},
''name'': ''test-name-10''}},
''name'': ''test-name-4''},
''$6'': {''children'': {}, ''name'': ''test-name-6''}}
>>>