Python создает вложенную структуру из плоской подсказки с «родительским» ключом - PullRequest
Новая
       12

Python создает вложенную структуру из плоской подсказки с «родительским» ключом

0 голосов
/ 06 ноября 2019

Давайте рассмотрим этот пример в Python 3: 

class SimpleObj:
    def __init__(self, own_id: int, parent_id: int):
        self.parent_id = parent_id
        self.own_id = own_id
        self.children_objects = []  # type: List[SimpleObj]

test_dict = {}
test_dict[0] = SimpleObj(own_id=0, parent_id=-1)  # -1 will mean root node
test_dict[1] = SimpleObj(own_id=1, parent_id=0)
test_dict[123] = SimpleObj(own_id=123, parent_id=1)
test_dict[5] = SimpleObj(own_id=5, parent_id=123)

Каков наиболее питонический способ создания рекурсивной вложенной структуры, где, например, SimpleObj с own_id=1 будет иметь заполненный список children_objectsс одним элементом, который был бы SimpleObj с own_id=123? Пахнет так похоже на проблему двоичного дерева, но мне действительно не удалось найти работающее решение, чтобы превратить этот вид словаря в структуру древовидных объектов.

Ответы [ 2 ]

1 голос
/ 06 ноября 2019

Может быть, вы можете создать небольшую функцию для обработки нового SimpleObj: 

class SimpleObj:
    def __init__(self, own_id: int, parent_id: int):
        self.parent_id = parent_id
        self.own_id = own_id
        self.children_objects = []


def addSimpleObj(struct, own_id, parent_id):
    struct[own_id] = SimpleObj(own_id=own_id, parent_id=parent_id)
    if parent_id != -1:
        try:
            struct[parent_id].children_objects.append(struct[own_id])
        except IndexError:
            print('the parent_id does not exists')

test_dict = {}
addSimpleObj(test_dict, 0, -1)
addSimpleObj(test_dict, 1, 0)
addSimpleObj(test_dict, 123, 1)
addSimpleObj(test_dict, 5, 123)

Это только начало, но, похоже, оно сработает. Вы можете изменить его для обработки, например, случая, когда вы пытаетесь воссоздать SimpleObj для ключа, который уже существует.

0 голосов
/ 07 ноября 2019

Покопавшись, я нашел собственное решение. Нужно было преодолеть две основные проблемы - рекурсию и работу с узлами, которые относятся к еще не присутствующим родителям. Вот мое решение. Он пытается рекурсивно присваивать объекты своим родителям, а в случае неудачи создает список сирот. Затем он перебирает список потерянных узлов, пока все они не будут на месте. Я проверил это на нескольких конфигах, и похоже, что он всегда работает (при условии, что ввод правильный, то есть без повторений или циклических ссылок и т. Д.). 

from __future__ import annotations
from typing import List


class SimpleObj:
    def __init__(self, parent_id: int, own_id: int):
        self.own_id = own_id
        self.parent_id = parent_id
        self.children_objects = []  # type: List[SimpleObj]

    def assign_to_children(self, what_to_assign: SimpleObj):
        if what_to_assign.parent_id == self.own_id:
            self.children_objects.append(what_to_assign)
            return True
        else:
            for child in self.children_objects:
                if child.assign_to_children(what_to_assign=what_to_assign):
                    return True

    def __repr__(self):
        return f"ID: {self.own_id}, PARENT: {self.parent_id}"

test_objects_list = [SimpleObj(own_id=69, parent_id=70),
                     SimpleObj(own_id=59, parent_id=71),
                     SimpleObj(own_id=70, parent_id=71),
                     SimpleObj(own_id=71, parent_id=1),
                     SimpleObj(own_id=1, parent_id=0),
                     SimpleObj(own_id=2, parent_id=1),
                     SimpleObj(own_id=44, parent_id=1),
                     SimpleObj(own_id=6, parent_id=44),
                     SimpleObj(own_id=14, parent_id=10),
                     SimpleObj(own_id=10, parent_id=1)]

def create_tree_from_list_of_obj(list_in: List[SimpleObj]):
    # find root
    root = [obj for obj in list_in if obj.parent_id == 0][0]
    list_in.remove(root)
    print(root)

    orphans = []
    # do the actual work
    for obj in list_in:
        found = root.assign_to_children(obj)
        print(f"Found {obj.own_id}") if found else print(f"Not found {obj.own_id}")
        if not found:
            orphans.append(obj)
            print(f"Adding orphaned node with id {obj.own_id}")

    while orphans:
        print(f"\nTrying to fill in {len(orphans)} orphaned nodes...")
        for orphaned_node in orphans[:]:
            found = root.assign_to_children(orphaned_node)
            if found:
                print(f"Found {orphaned_node.own_id}")
                orphans.remove(orphaned_node)
            else:
                print(f"Not found {orphaned_node.own_id}")
    return root

tree = create_tree_from_list_of_obj(test_objects_list)
...