Overlapped positions on tree when using reingold_tilford

[chamakov]

Describe the issue When generating positions using reingold_tilford where the tree has more than 6 depth with last 2 subrtrees with more than 15 leafs, the most left tree first sibiling its overlapping with the last sibiling of his right sibiling tree

Environment Describe your environment.

• Platform: Ubuntu
• Python version: 3.9
• bigtree version: 0.19.4

To Reproduce Generate a tree with more than 6 depth assigning at least 3 items per sub-level, and the las level need to have at least 15 leafs

Expected behaviour The subtree positions returned by reingold_tilford need to be separated and non overlapping

Additional Information Reviewing the algorithm, the last revision doesn't check the positions to see if something its overlapped

[kayjan]

Sorry your description of the tree is a little unclear

• “last 2 subtrees” are the subtrees split at depth 2 or depth 5?
• “last level need to have at least 15 leaves” this is referring to the whole depth=6 or just under one node?

I tried to create a tree of your description and did not find any overlap. Can you include the code to reproduce what you’re seeing and point out which nodes have coordinates that are overlapping?

[kayjan]

Deployed bigtree v0.21.0 that can perform tree_root.plot() to visualize the positions of (x,y) coordinates. Perhaps you can give it a try and let me know if there are any overlaps.

[kayjan]

Below are some sample codes I tried.

In this first example, I take it to the extreme where every node has 3 children. This means that at depth 6 I am expecting 3^6=729 children. It looks a little crowded.

from bigtree import Node

root = Node("root")
for depth_idx in range(6):  # depth
    descendants = list(root.leaves)
    for descendant in descendants:
        for child_idx in range(3):  # number of children per node
            Node(f"{depth_idx}.{child_idx}", parent=descendant)

fig = root.plot("-ok")
fig.savefig("tree_big.png")

In the second example, it is less extreme. I tried to stick to your description of "2 subtrees with more than 15 leaves".

from bigtree import Node

depth_to_children = {
    0: 2,
    1: 5,
    2: 2,
    3: 1,
    4: 2,
    5: 1,
}

root = Node("root")
for depth_idx in range(6):  # depth
    descendants = list(root.leaves)
    num_children = depth_to_children[depth_idx]
    for descendant in descendants:
        for child_idx in range(num_children):  # number of children per node
            Node(f"{depth_idx}.{child_idx}", parent=descendant)

fig = root.plot("-ok")
fig.savefig("tree_small.png")

---

I closely followed the Reingold Tilford paper, another Reingold Tilford paper, and my article which addresses some edge cases not in the original papers. There are 3 passes for the algorithm, I highly doubt that would be an "overlap in the last revision". Feel free to use my code snippet and make the adjustments. Will be closing this ticket as I cannot reproduce your error and due to lack of replies after a week.