N-арные деревья в Нумбе - PullRequest
Новая
       7

N-арные деревья в Нумбе

0 голосов
/ 12 февраля 2020

Мне нужно реализовать древовидную структуру, где каждый узел имеет произвольное количество дочерних элементов. Это кажется простым, когда известно число детей (связанный список, двоичное дерево и т. Д. c.), Но мне не удалось реализовать его в более общем случае.

Например, я попытался расширить этот пример связанного списка , изменив параметр next в список. Тем не менее, кажется, что нельзя иметь список deferred_type. Есть идеи, как это реализовать? 

from collections import OrderedDict 
from numba import njit, jitclass, types, int32, deferred_type, optional
import numpy as np 

node_type = deferred_type()

spec = OrderedDict() 
spec['data'] = int32 
spec['next'] = optional(types.ListType(node_type))


@jitclass(spec) 
class LinkedNode:
    def __init__(self, data, next):
        self.data = data
        self.next = next

    def prepend(self, data):
        return LinkedNode(data, self)


@njit def make_linked_node(data):
    return LinkedNode(data, None)


node_type.define(LinkedNode.class_type.instance_type)

1 Ответ

0 голосов
/ 13 февраля 2020

Я нашел альтернативу, которая, хотя и не совсем то, что я хотел, все же выполняет свою работу. По сути, это стандартное расширение двоичного дерева, которое включает больше узлов между левым и правым узлами (см. эту статью ).

Эти структуры обычно отслеживают только первые ( left) child, но у меня также есть указатель на последний (right), поскольку он облегчает расположение всех ребер, используя только родительский узел. 

from collections import OrderedDict
from numba import jitclass, int64, deferred_type, optional

node_type = deferred_type()

spec = OrderedDict()
spec['id'] = int64
spec['parent'] = optional(node_type)
spec['left_child'] = optional(node_type)  # first child
spec['right_child'] = optional(node_type) # last child
spec['sibling'] = optional(node_type)  # next sibling


@jitclass(spec)
class Node:
    def __init__(self, id, parent):
        self.id = id
        self.parent = parent
        # initialize parent and left right children as None
        self.left_child = None
        self.right_child = None
        self.sibling = None
        if parent is not None:
            parent.add_child(self)

    @property
    def children(self):
    """ A list with all children. """
        children = []
        child = self.left_child
        while child is not None:
            children.append(child)
            child = child.sibling
        return children

    def add_sibling(self, sibling):
        self.sibling = sibling

    def add_child(self, child):
        # if parent has no children
        if self.left_child is None:
            # this node is it first child
            self.left_child = child
            self.right_child = child
        else:
            # the last (now right) child will have this node as sibling
            self.right_child.add_sibling(child)
            self.right_child = child


node_type.define(Node.class_type.instance_type)
...