未知のルート

Question

とJSONツリーを作成しますI持って最小スパニングツリーアルゴリズムから作成された次のデータ：私が持っている

{ 
    "id": "Earl", 
    "name": "Earl", 
    "children": [ 
     { 
      "id": "Bob", 
      "name": "Bob", 
      "children": [ 
       { 
        "id": "Leroy", 
        "name": "Leroy", 
        "children": [ 
         { 
          "id": "Harry", 
          "name": "Harry" 
         } 
        ] 
       }, 
       { 
        "id": "Sam", 
        "name": "Sam" 
       } 
      ] 
     } 
    ] 
} 

：

links = [("Earl","Bob"),("Bob","Sam"),("Bob","Leroy"),("Leroy","Harry")] 

は、私は次のようなJSONツリーにデータを変換する必要があります私が欲しくないツリーに「Root」というルートノードを追加する以外は、次のスクリプトを実行します。

import json 
links = [("Earl","Bob"),("Bob","Sam"),("Bob","Leroy"),("Leroy","Harry")] 
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['id'] = node 
    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=2)) 

### output below ### 

{ 
    "children": [ 
    { 
     "children": [ 
     { 
      "children": [ 
      { 
       "id": "Sam", 
       "name": "Sam" 
      }, 
      { 
       "children": [ 
       { 
        "id": "Harry", 
        "name": "Harry" 
       } 
       ], 
       "id": "Leroy", 
       "name": "Leroy" 
      } 
      ], 
      "id": "Bob", 
      "name": "Bob" 
     } 
     ], 
     "id": "Earl", 
     "name": "Earl" 
    } 
    ], 
    "id": "Root", 
    "name": "Root" 
} 

私が必要とするのは、ルートノードとして偽の「ルート」を追加しないことです。ルートは、（最初​​のjsonの例によると）linksに親を持たない既存のノードでなければなりません。言い換えれば、樹木の根は必ずしも伯爵である必要はなく、親を持たないどのノードでもよい。ツリーはそこから拡大を開始することができます。

おそらく、これを修正する代わりにこれを行うためのより良いアルゴリズムがありますか？

Answer 1

tree = get_nodes('Root'); 
tree = tree.children[0]; 
print(json.dumps(tree, indent=2)); 

Answer 2

アールをルートの子として追加したためではありませんか？ ：あなたはnode = 'Root'ためchildren = get_children(node)を実行したときに

links.append(('Root', node)) 
print links # [('Earl', 'Bob'), ('Bob', 'Sam'), ('Bob', 'Leroy'), ('Leroy', 'Harry'), ('Root', 'Earl')] 

だから今、あなたはTrueを取得します。