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 создает узлы (то есть добавляет их в словарь узлов), а Pass 2 создает родительскую структуру < -> children.

Выполнены следующие допущения: нет циклов (неясно, какой ожидаемый результат был бы в таком случае, указывается 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 

EDIT: Почему ваше решение не работает так, как вы ожидали?

Вот подсказка относительно верхнего уровня: Вывод, который вы хотите получить, представляет собой список деревьев. Однако переменная, с которой вы имеете дело (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) 

Далее определяют, как связать коллекцию узлов друг с другом. Мы будем использовать Dict для хранения указателей на каждый отдельный узел:

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