Costruire ricorsivamente un albero JSON gerarchico?

Question

Ho un database di connessioni padre-figlio. I dati appaiono come i seguenti, ma potrebbero essere presentati in qualsiasi modo (dizionari, liste di liste, JSON, ecc.).

links=(("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl")) 

L'output di cui ho bisogno è un albero JSON gerarchico, che verrà reso con d3. Ci sono sotto-alberi discreti nei dati, che collegherò a un nodo radice. Quindi ho bisogno di ricorsivamente andare attraverso i collegamenti e costruire la struttura ad albero. Il più lontano che posso ottenere è di scorrere tutte le persone e aggiungere i loro figli, ma non riesco a capire di fare i collegamenti di ordine superiore (ad esempio come aggiungere una persona con figli al figlio di qualcun altro). È simile a un'altra domanda here, ma non ho modo di conoscere i nodi radice in anticipo, quindi non posso implementare la soluzione accettata.

Vado per la seguente struttura ad albero dai miei dati di esempio.

{ 
"name":"Root", 
"children":[ 
    { 
    "name":"Tom", 
    "children":[ 
     { 
     "name":"Dick", 
     "children":[ 
      {"name":"Harry"} 
     ] 
     }, 
     { 
      "name":"Larry"} 
    ] 
    }, 
    { 
    "name":"Bob", 
    "children":[ 
     { 
     "name":"Leroy" 
     }, 
     { 
     "name":"Earl" 
     } 
    ] 
    } 
] 
} 

Questa struttura si presenta così nel mio layout d3.

Answer 1

Per identificare le note fondamentali È possibile decomprimere links e cercare i genitori che non sono i bambini:

parents, children = zip(*links) 
root_nodes = {x for x in parents if x not in children} 

allora si può applicare il metodo ricorsivo:

import json 

links = [("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl")] 
parents, children = zip(*links) 
root_nodes = {x for x in parents if x not in children} 
for node in root_nodes: 
    links.append(('Root', node)) 

def get_nodes(node): 
    d = {} 
    d['name'] = node 
    children = get_children(node) 
    if children: 
     d['children'] = [get_nodes(child) for child in children] 
    return d 

def get_children(node): 
    return [x[1] for x in links if x[0] == node] 

tree = get_nodes('Root') 
print json.dumps(tree, indent=4) 

ho usato un set per ottenere i nodi radice, ma se l'ordine è importante è possibile utilizzare un elenco e remove the duplicates.

Answer 2

Prova Codice follwing:

import json 

links = (("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Tom","Hurbert"),("Tom","Neil"),("Bob","Leroy"),("Bob","Earl"),("Tom","Reginald")) 

name_to_node = {} 
root = {'name': 'Root', 'children': []} 
for parent, child in links: 
    parent_node = name_to_node.get(parent) 
    if not parent_node: 
     name_to_node[parent] = parent_node = {'name': parent} 
     root['children'].append(parent_node) 
    name_to_node[child] = child_node = {'name': child} 
    parent_node.setdefault('children', []).append(child_node) 

print json.dumps(root, indent=4) 

Answer 3

Nel caso in cui si desidera formattare i dati come una gerarchia nel codice HTML/JS per sé, dare un'occhiata a:

Generate (multilevel) flare.json data format from flat json

Nel caso in cui hai tonnellate di dati la conversione Web sarà più veloce poiché utilizza la funzionalità di riduzione mentre Python manca di programmazione funzionale.

BTW: Sto anche lavorando sullo stesso argomento, cioè generando la struttura ad albero pieghevole in d3.js. Se vuoi lavorare insieme, la mia email è: erprateek.vit@gmail.com.