-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdtwc
177 lines (160 loc) · 6.07 KB
/
dtwc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
## parse with newick
def newick(file):
return newick.read(file) # returns a list of newick.Node
## parse with ete3
def ete3(file,format):
return Tree(file,format=format)
## init functions
def get_lvl(node):
lvl = 1
while (node.is_root() == False):
lvl += 1
node = node.up
return lvl
def induce_order(tree):
print('inducing order')
i = 0 # maybe set to 1 initially
for node in tree.traverse():
# set depth and index
node.add_features(depth=get_lvl(node), idx=i)
#print('set depth=' + str(node.depth) + "and idx=" + str(node.idx) + 'for node ' + str(node.name))
# for binary trees
if len(node.get_children()) == 2:
node.add_features(left=node.children[0],right=node.children[1])
# set lmost and rmost sibling for all nodes not leaves
if not node.is_leaf() or len(node.get_children()) != 0:
node.add_features(lmost_sibling=node.children[0], rmost_sibling=node.children[len(node.get_children())-1])
# set features for buchheim
node.add_features(mod=0, thread=0, shift=0, change=0, prelim_x=0)
node.add_features(ancestor=node)
i += 1
print('successfully induced order')
## some test functions
def left_sibling(node):
left_sibling = None
if node.up:
for children in node.up.get_children():
if children == node : return left_sibling
else: left_sibling = children
return left_sibling
def set_lrmost_level(tree):
for node in tree.traverse():
return iter(node.depth)
def set_prelim_coords(tree):
for node in tree.traverse():
if node.is_leaf(): node.add_features(prelim_x=node.depth)
# if len(node.get_children()) == 1 && (node.idx+1 && node.depth ==
##
## buchheim
def next_left(node):
if len(node.get_children()) != 0:
return node.children[0]
else:
return node.thread
def next_right(node):
if len(node.get_children()) != 0:
return node.children[len(node.get_children())-1]
else:
return node.thread
def move_subtree(w_minus,w_plus,shift):
subtrees = w_plus.idx - w_minus.idx
w_plus.change = w_plus.change - shift / subtrees
w_plus.shift = w_plus.shift + shift
w_minus.change = w_minus.change + shift / subtrees
w_plus.prelim_x = w_plus.prelim_x + shift
w_plus.mod = w_plus.mod + shift
def execute_shifts(node):
shift = 0
change = 0
for children in reversed(node.get_descendants()):
children.prelim_x += shift
children.mod += shift
change += children.change
shift += children.shift + change
def ancestor(v_i_minus,node,default_ancestor):
if v_i_minus.up in node.up.get_children():
return v_i_minus.up
else:
return default_ancestor
def has_left_child(node):
node.idx != node.up.children[0].idx
node
def apportion(node,default_ancestor):
w = left_sibling(node)
if w != None:
v_i_plus = v_o_plus = node
v_i_minus = w
v_o_minus = v_i_plus.up.children[0] # left most sibling
s_i_plus = v_i_plus.mod
s_o_plus = v_o_plus.mod
s_i_minus = v_i_minus.mod
s_o_minus = v_o_minus.mod
while next_right(v_i_minus) != 0 and next_left(v_i_plus) != 0:
v_i_minus = next_right(v_i_minus)
v_i_plus = next_left(v_i_plus)
v_o_minus = next_left(v_o_minus)
v_o_plus = next_right(v_o_plus)
v_o_plus.add_features(ancestor=node)
shift = (v_i_minus.prelim_x + s_i_minus) - (v_i_plus.prelim_x + s_i_plus) + distance
if shift > 0:
move_subtree(ancestor(v_i_minus,node,default_ancestor),node,shift)
s_i_plus += shift
s_o_plus += shift
s_i_minus += v_i_minus.mod
s_i_plus += v_i_plus.mod
s_o_minus += v_o_minus.mod
s_o_plus += v_o_plus.mod
if next_right(v_i_minus) != 0 and next_right(v_o_plus) == 0:
v_o_plus.thread = next_right(v_i_minus)
v_o_plus.mod += s_i_minus - s_o_plus
if next_left(v_i_plus) != 0 and next_left(v_o_minus) == 0:
v_o_minus.thread = next_left(v_i_plus)
v_o_minus.mod += s_i_plus - s_o_minus
default_ancestor = node
return default_ancestor
def first_walk(node):
print('start first walk for' + str(node.name))
if node.is_leaf():
node.add_features(prelim_x=0)
print('reached leafs')
else:
default_ancestor = node.children[0] # left most child
print('set default ancestor' + str(default_ancestor.name))
for children in node:
print('start first walk for' + str(children.name))
first_walk(children)
print('start apportion for' + str(children.name) + 'with default ancestor' + str(default_ancestor.name))
apportion(children,default_ancestor)
print('execute shifts for node' + str(node.name))
execute_shifts(node)
midpoint = 1/2*(node.children[0].prelim_x + node.children[len(node.get_children())-1].prelim_x)
if left_sibling(node):
node.add_features(prelim_x=left_sibling().prelim_x + distance,mod=node.prelim_x - midpoint)
else:
node.add_features(prelim_x=midpoint)
def second_walk(node,m):
node.add_features(x=node.prelim_x + m, \
y=node.depth)
for children in node:
second_walk(children,m + node.mod)
def buchheim(tree):
print('start buchheim walk')
induce_order(tree)
root = tree.get_tree_root()
print('set root=' + str(root.name))
print('start first walk for root' + str(root.name))
first_walk(root)
print('start second walk for root' + str(root.name))
second_walk(root,-root.prelim_x)
#return tree
print('finished')
# create nx graph
def DrawTree(tree):
buchheim(tree)
print('start drawing')
NX = nx.Graph()
for node in tree.traverse():
NX.add_node(node)
for children in node:
NX.add_edge(node, children)
nx.draw(NX, with_labels=True, font_weight='bold')