的Python - 生成

Question

我有一個下面的列表元組的列表詞典（樹）： -

a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)] 

這是一個元組列表。元組內的元素的格式爲(Id, ParentId)其根節點爲Id == ParentId。該列表可以以元組的任何順序。

我想生成以下字典使用元組的上述名單，

output = [{ 
    'id': 1, 
    'children': [{ 
     { 
      'id': 3, 
      'children': [{ 
       { 
        'id': 5 
       }, 
       { 
        'id': 4 
       }, 
       { 
        'id': 6 
       } 
      }] 
     }, 
     { 
      'id': 2 
     } 
    }] 
}, { 
    'id': 7, 
    'children': [{ 
     { 
      'id': 9 
     }, 
     { 
      'id': 8 
     } 
    }] 
}] 

即（在graphs-一個阿甘而言）

1   7 
/\  /\ 
    2 3  8 9 
    /|\ 
    4 5 6 

我的最終輸出應詞典給出以上。

我試過如下： -

，我已經試過解決方案如下： -

# set the value of nested dictionary. 
def set_nested(d, path, value): 
    reduce(lambda d, k: d.setdefault(k, {}), path[:-1], d)[path[-1]] = value 
    return d 

# returns the path of any node in list format 
def return_parent(list, child): 
    for tuple in list: 
     id, parent_id = tuple 
     if parent_id == id == child: 
      return [parent_id] 
     elif id == child: 
      return [child] + return_parent(list, parent_id) 

paths = [] 
temp = {} 
for i in a: 
    id, parent_id = i 
    temp[id] = {'id': id} 
    path = return_parent(a, id)[::-1] 
    paths.append(path) # List of path is created 

d = {} 
for path in paths: 
    for n, id in enumerate(path): 
     set_nested(d, path[:n + 1], temp[id]) # setting the value of nested dictionary. 

print d 

，我得到的輸出是

{ 
    '1': { 
     '3': { 
      '6': { 
       'id': '6' 
      }, 
      '5': { 
       'id': '5' 
      }, 
      'id': '3', 
      '4': { 
       '10': { 
        'id': '10' 
       }, 
       'id': '4' 
      } 
     }, 
     '2': { 
      'id': '2' 
     }, 
     'id': '1' 
    }, 
    '7': { 
     '9': { 
      'id': '9' 
     }, 
     '8': { 
      'id': '8' 
     }, 
     'id': '7' 
    } 
} 

我很接近到它，但不能得到確切的輸出。另外，還有更好的解決方案嗎？

Answer 1

這是一個更簡單的方法。 （編輯，我從托馬斯回答說，節點可以以任意順序給出）：第1遍創建節點（即，將它們添加到節點字典），而第2遍然後創建父級< - >子級結構。

做出以下假設：沒有周期（不清楚在這種情況下預期的輸出是什麼，由Garret R指出），沒有缺失邊緣，沒有缺失樹根。

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 

編輯：爲什麼你的解決方案不能按預期工作？

這是關於頂層的提示：你想獲得的輸出是列表樹。然而，你正在處理的變量（d）需要是一個字典，因爲在函數set_nested中，你應用了setdefaults方法。

Answer 2

根據需要，此解決方案的工作方式與節點的順序無關。

a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)] 
b = [(8, 7), (5, 3), (2, 1), (1, 1), (3, 1), (7, 7), (4, 3), (6, 3), (9, 7)] 

def build_forest(nodelist): 
    forest = [] 
    nodes = {} 

    id = 'id' 
    children = 'children' 

    for node_id, parent_id in nodelist: 
     #create current node if necessary 
     if not node_id in nodes: 
      node = { id : node_id } 
      nodes[node_id] = node 
     else: 
      node = nodes[node_id] 

     if node_id == parent_id: 
      #add node to forrest 
      forest.append(node) 
     else: 
      #create parent node if necessary 
      if not parent_id in nodes: 
       parent = { id : parent_id } 
       nodes[parent_id] = parent 
      else: 
       parent = nodes[parent_id] 
      #create children if necessary 
      if not children in parent: 
       parent[children] = [] 
      #add node to children of parent 
      parent[children].append(node) 

    return forest  

print(build_forest(a)) 
print(build_forest(b)) 

Answer 3

爲了更方便，讓我們定義一個簡單的關係對象：

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) 

下一個定義如何與節點的集合彼此。我們將使用一個字典來保存指向每個單獨的節點：

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 

現在，把你的輸入數據，並涉及它：

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) 

最後，得到的輸出：有你想要的好機會將數據植根爲獨特樹的列表，而不是作爲字典 - 但您可以選擇自己喜歡的內容。

roots = [x for x in lookup.values() if x.parent is None] 

# and for nice visualization: 
import json 
print json.dumps(roots, indent=4) 

產生：

[ 
    { 
     "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": [] 
      } 
     ] 
    } ]