小能豆

Why is my binary K-dimensional tree not rendered properly?

py

I’m working with anytree package in Python for creating and displaying a K-dimension tree, however the tree is not rendered properly.

This is part of my source code for my K-dimensional node:

import numpy as np
from anytree import NodeMixin


class KdData:
    def __init__(self) -> None:
        self.key = None


class KdNode(KdData, NodeMixin):
    def __init__(self, parent=None, children=None, axis: int = 0) -> None:
        super().__init__()
        self.axis = axis
        self.parent = parent
        if children:
            self.children = children

    def set_key(self, key):
        self.key = np.array(key)
        if self.key is not None:
            self.children = [
                KdNode(axis=(self.axis + 1) % self.key.shape[0]),
                KdNode(axis=(self.axis + 1) % self.key.shape[0])
            ]

    def get_left_node(self):
        if self.key is None:
            return None
        return self.children[0]

    def get_right_node(self):
        if self.key is None:
            return None
        return self.children[1]

    def insert(self, key):
        if self.key is None:
            self.set_key(key)
        elif key[self.axis] < self.key[self.axis]:
            self.get_left_node().insert(key)
        else:
            self.get_right_node().insert(key)

    # Other functions are omitted because it's not relavant to the question

Then this is the tree I created.

tree = KdNode()
tree.set_key(np.array([5,6]))
tree.insert([4,7])
tree.insert([17,16])
tree.insert([7,8])
tree.insert([1,4])
tree.insert([9,13])

And this is my exporter:

def node_attribute(node):
    att = ""
    att += "shape=plaintext"
    return att

def edge_att(source, target):
    att = ""
    if target.key is None:
        att += "style=invis"
    return att

from anytree.exporter.dotexporter import DotExporter, UniqueDotExporter

dot_obj = UniqueDotExporter(tree,
    nodenamefunc=lambda node: node.key if node.key is not None else "",
    nodeattrfunc=lambda node: node_attribute(node),
    edgeattrfunc=lambda src, tgt: edge_att(src, tgt))

My obtained result is here. The expected result is that [4 7] node and [17 16] node are in the same rank.

Why was my K-dimensional tree not rendered properly?


阅读 68

收藏
2023-12-17

共1个答案

小能豆

The issue seems to be related to how you are setting the style attribute in the edge_att function. The style attribute should be set to "invis" for the edge between the parent and its left child, but not for the edge between the parent and its right child.

Here’s an updated version of your edge_att function:

def edge_att(source, target):
    att = ""
    if target.key is None:
        att += "style=invis"
    elif target == source.get_left_node():
        att += "style=invis"
    return att

This ensures that the style attribute is set to "invis" only for the edge between the parent and its left child. The edges between the parent and its right child or between the parent and a leaf node should not have the "invis" style.

With this modification, the nodes [4 7] and [17 16] should be displayed on the same rank in the rendered tree.

2023-12-17