Rekursywnie buduj hierarchiczne drzewo JSON?

Question

Mam bazę danych połączeń rodzic-dziecko. Dane wyglądają następująco, ale mogą być prezentowane w dowolny sposób (słowniki, lista list, JSON itp.).

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

Dane wyjściowe, których potrzebuję, to hierarchiczne drzewo JSON, które zostanie zrenderowane przy pomocy d3. W danych są dyskretne pod-drzewa, które podłączę do węzła głównego. Muszę rekurencyjnie przejść przez linki i zbudować strukturę drzewa. Najdalej mogę dostać, to powtarzać przez wszystkich ludzi i dołączać ich dzieci, ale nie mogę wymyślić, aby wykonać linki wyższego rzędu (np. Jak dołączyć osobę z dziećmi do dziecka kogoś innego). Jest to podobne do innego pytania: here, ale nie mam możliwości wcześniejszego poznania węzłów głównych, więc nie mogę zaimplementować zaakceptowanego rozwiązania.

Przejdę do poniższej struktury drzewa z moich przykładowych danych.

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

Ta struktura renderuje się tak w moim układzie D3.

Answer 1

Aby zidentyfikować Prymy można rozpakować links i wyglądają dla rodziców, którzy nie mają dzieci:

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

Następnie można zastosować rekurencyjną metodę:

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) 

użyłem zestawu, aby uzyskać węzły główne, ale jeśli zamówienie jest ważne, możesz użyć listy i remove the duplicates.

Answer 2

Spróbuj kodu 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

W przypadku, gdy chcesz sformatować dane jako hierarchia w HTML/sama JS, przyjrzeć:

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

w przypadku masz mnóstwo danych, konwersja w Internecie będzie szybsza, ponieważ używa funkcji zmniejszania, podczas gdy w Pythonie brakuje funkcjonalnego programowania.

BTW: Pracuję również nad tym samym tematem, tj. Generowanie składanej struktury drzewa w pliku d3.js. Jeśli chcesz pracować razem, mój adres e-mail to: erprateek.vit@gmail.com.