Aluode/PerceptionLabPortable

1# Authors: The scikit-learn developers
2# SPDX-License-Identifier: BSD-3-Clause
3
4import numpy as np
5
6
7class DrawTree:
8    def __init__(self, tree, parent=None, depth=0, number=1):
9        self.x = -1.0
10        self.y = depth
11        self.tree = tree
12        self.children = [
13            DrawTree(c, self, depth + 1, i + 1) for i, c in enumerate(tree.children)
14        ]
15        self.parent = parent
16        self.thread = None
17        self.mod = 0
18        self.ancestor = self
19        self.change = self.shift = 0
20        self._lmost_sibling = None
21        # this is the number of the node in its group of siblings 1..n
22        self.number = number
23
24    def left(self):
25        return self.thread or (len(self.children) and self.children[0])
26
27    def right(self):
28        return self.thread or (len(self.children) and self.children[-1])
29
30    def lbrother(self):
31        n = None
32        if self.parent:
33            for node in self.parent.children:
34                if node == self:
35                    return n
36                else:
37                    n = node
38        return n
39
40    def get_lmost_sibling(self):
41        if not self._lmost_sibling and self.parent and self != self.parent.children[0]:
42            self._lmost_sibling = self.parent.children[0]
43        return self._lmost_sibling
44
45    lmost_sibling = property(get_lmost_sibling)
46
47    def __str__(self):
48        return "%s: x=%s mod=%s" % (self.tree, self.x, self.mod)
49
50    def __repr__(self):
51        return self.__str__()
52
53    def max_extents(self):
54        extents = [c.max_extents() for c in self.children]
55        extents.append((self.x, self.y))
56        return np.max(extents, axis=0)
57
58
59def buchheim(tree):
60    dt = first_walk(DrawTree(tree))
61    min = second_walk(dt)
62    if min < 0:
63        third_walk(dt, -min)
64    return dt
65
66
67def third_walk(tree, n):
68    tree.x += n
69    for c in tree.children:
70        third_walk(c, n)
71
72
73def first_walk(v, distance=1.0):
74    if len(v.children) == 0:
75        if v.lmost_sibling:
76            v.x = v.lbrother().x + distance
77        else:
78            v.x = 0.0
79    else:
80        default_ancestor = v.children[0]
81        for w in v.children:
82            first_walk(w)
83            default_ancestor = apportion(w, default_ancestor, distance)
84        # print("finished v =", v.tree, "children")
85        execute_shifts(v)
86
87        midpoint = (v.children[0].x + v.children[-1].x) / 2
88
89        w = v.lbrother()
90        if w:
91            v.x = w.x + distance
92            v.mod = v.x - midpoint
93        else:
94            v.x = midpoint
95    return v
96
97
98def apportion(v, default_ancestor, distance):
99    w = v.lbrother()
100    if w is not None:
101        # in buchheim notation:
102        # i == inner; o == outer; r == right; l == left; r = +; l = -
103        vir = vor = v
104        vil = w
105        vol = v.lmost_sibling
106        sir = sor = v.mod
107        sil = vil.mod
108        sol = vol.mod
109        while vil.right() and vir.left():
110            vil = vil.right()
111            vir = vir.left()
112            vol = vol.left()
113            vor = vor.right()
114            vor.ancestor = v
115            shift = (vil.x + sil) - (vir.x + sir) + distance
116            if shift > 0:
117                move_subtree(ancestor(vil, v, default_ancestor), v, shift)
118                sir = sir + shift
119                sor = sor + shift
120            sil += vil.mod
121            sir += vir.mod
122            sol += vol.mod
123            sor += vor.mod
124        if vil.right() and not vor.right():
125            vor.thread = vil.right()
126            vor.mod += sil - sor
127        else:
128            if vir.left() and not vol.left():
129                vol.thread = vir.left()
130                vol.mod += sir - sol
131            default_ancestor = v
132    return default_ancestor
133
134
135def move_subtree(wl, wr, shift):
136    subtrees = wr.number - wl.number
137    # print(wl.tree, "is conflicted with", wr.tree, 'moving', subtrees,
138    # 'shift', shift)
139    # print wl, wr, wr.number, wl.number, shift, subtrees, shift/subtrees
140    wr.change -= shift / subtrees
141    wr.shift += shift
142    wl.change += shift / subtrees
143    wr.x += shift
144    wr.mod += shift
145
146
147def execute_shifts(v):
148    shift = change = 0
149    for w in v.children[::-1]:
150        # print("shift:", w, shift, w.change)
151        w.x += shift
152        w.mod += shift
153        change += w.change
154        shift += w.shift + change
155
156
157def ancestor(vil, v, default_ancestor):
158    # the relevant text is at the bottom of page 7 of
159    # "Improving Walker's Algorithm to Run in Linear Time" by Buchheim et al,
160    # (2002)
161    # https://citeseerx.ist.psu.edu/doc_view/pid/1f41c3c2a4880dc49238e46d555f16d28da2940d
162    if vil.ancestor in v.parent.children:
163        return vil.ancestor
164    else:
165        return default_ancestor
166
167
168def second_walk(v, m=0, depth=0, min=None):
169    v.x += m
170    v.y = depth
171
172    if min is None or v.x < min:
173        min = v.x
174
175    for w in v.children:
176        min = second_walk(w, m + v.mod, depth + 1, min)
177
178    return min
179
180
181class Tree:
182    def __init__(self, label="", node_id=-1, *children):
183        self.label = label
184        self.node_id = node_id
185        if children:
186            self.children = children
187        else:
188            self.children = []
189