-
Notifications
You must be signed in to change notification settings - Fork 0
/
summary.py
271 lines (253 loc) · 11.3 KB
/
summary.py
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
__author__ = "Lars Berling"
from findpath import *
import sys
import globals
def sort_trees(trees):
# For a set of trees returned the sorted trees
output = list()
for i in trees:
newtree = []
for j in i:
cur = sorted(j)
newtree.append(cur)
output.append(newtree)
return (output)
def expand(tree):
# Takes a tree in list of lists format, adds leave clusters and returns it in list of sets format
if (len(tree[0]) == 1):
return (sort_tree(tree))
else:
tree = add_leaves(tree)
tree = sort_tree(tree)
return (tree)
def collapse(tree):
# Takes a tree and returns list of list format without the leaf cluster
if (len(tree[0]) == 1):
output = []
for i in tree:
if (len(i) > 1):
output.append(list(i))
return (output)
else:
return (tree)
################### Alex Algorithm ######################
def update_tracking(path):
# Update the gloabal dict to track the already computed distances
# For all trees on the given path, save the distance in the tracking dict
for i in range(len(path)-1):
for j in range(i,len(path)):
if str(expand(path[i])) in globals.tracking_paths:
# tree i in path has already been visited before
if str(expand(path[j])) in globals.tracking_paths[str(expand(path[i]))]:
# print('ERR: Already computed path gets computed again!')
if not globals.tracking_paths[str(expand(path[i]))][str(expand(path[j]))] == j-i:
# Check if the distance was already computed and if so check if it is equal
print('ERR!: update_tracking() found shortest paths with different lengths!')
else:
globals.tracking_paths[str(expand(path[i]))][str(expand(path[j]))] = j-i
elif str(path[j]) in globals.tracking_paths:
# tree j in path has already been visited before
if str(expand(path[i])) in globals.tracking_paths[str(expand(path[j]))]:
# print('ERR: Already computed path gets computed again!')#
if not globals.tracking_paths[str(expand(path[j]))][str(expand(path[i]))] == j-i:
# Check if the distance was already computed and if so check if it is equal
print('ERR!: update_tracking() found shortest paths with different lengths!')
else:
globals.tracking_paths[str(expand(path[j]))][str(expand(path[i]))] = j-i
else:
# New entry i.e. neither path[i] nor path[j] were in the tracking dict before
globals.tracking_paths[str(expand(path[i]))] = {str(expand(path[j])) : j-i}
#####
# update_tracking_m() only puts the start and end node of the path in the tracking dict:
# Improvement similar to saving all trees on the path but not as good --> may be relevant if the memory of the tracking dict gets to big
#####
# def update_tracking_m(path):
# if str(expand(path[0])) in globals.tracking_paths:
# if str(expand(path[len(path)-1])) in globals.tracking_paths[str(expand(path[0]))]:
# if not globals.tracking_paths[str(expand(path[0]))][str(expand(path[len(path)-1]))] == len(path)-1:
# print('ERR!')
# else:
# globals.tracking_paths[str(expand(path[0]))][str(expand(path[len(path)-1]))] = len(path)-1
# elif str(expand(path[len(path)-1])) in globals.tracking_paths:
# if str(expand(path[0])) in globals.tracking_paths[str(expand(path[len(path)-1]))]:
# if not globals.tracking_paths[str(expand(path[len(path)-1]))][str(expand(path[0]))] == len(path)-1:
# print('ERR!')
# else:
# globals.tracking_paths[str(expand(path[len(path)-1]))][str(expand(path[0]))] = len(path)-1
# else:
# globals.tracking_paths[str(expand(path[0]))] = {str(expand(path[len(path)-1])) : len(path)-1}
def check_tracking(tree1,tree2):
# Check if the path between the trees tree1 and tree2 has already been computed before, if not return -1
out = -1
if str(tree1) in globals.tracking_paths:
if str(tree2) in globals.tracking_paths[str(tree1)]:
out = globals.tracking_paths[str(tree1)][str(tree2)]
elif str(tree2) in globals.tracking_paths:
if str(tree1) in globals.tracking_paths[str(tree2)]:
out = globals.tracking_paths[str(tree2)][str(tree1)]
return out
def get_closer(s, trees, distance):
# Given a set of trees, a starting vertex and a current distance
# --> compute trees within one neighbourhood of that vertex that make the distance smaller
Nei = one_neighbourhood(expand(s))
output = []
for i in Nei:
# For each Neibour of start compute trees i that make distance smaller than it is currently
cur = 0
for j in trees:
# check tracking_paths
# check expand(i) and expand(j) is already in tracking_paths
check = check_tracking(expand(i),expand(j))
if check == -1:
cur_p = findpath(collapse(i), collapse(j))
path = len(cur_p) - 1
update_tracking(cur_p)
# update_tracking_m(cur_p) # Just saving start and end node of the path
globals.fp_count += 1
else:
path = check
cur += path ** 2
# cur += path
# maybe only sum of distances -> think if that even makes sense
# cur += path
if (cur < distance):
# Maybe <= but that would be weird, look into that
output.append([i, cur])
return (output)
def centroid(trees, s):
# Centroid search starting from s
# Initialization to run get_closer_function
globals.fp_count = 0
# tracking_paths = {}
startdist = 0
for i in trees:
# check tracking_paths
check = check_tracking(expand(s),expand(i))
if check == -1:
cur_p = findpath(collapse(s), collapse(i))
path = len(cur_p) - 1
update_tracking(cur_p)
# update_tracking_m(cur_p) # Just saving start and end node of the path
globals.fp_count += 1
else:
path = check
startdist += path ** 2
closer = get_closer(s, trees, startdist)
output = {}
if not closer:
output[str(expand(s))] = startdist
else:
while bool(closer):
update = []
for i in range(len(closer)):
# for each tree that is closer
cur = get_closer(closer[i][0], trees, closer[i][1])
if bool(cur):
# there are trees that give a smaller distance = cur
# we need to add each tree to closer, i.e. check if there is anything in their neighbourhood
# which gives better distance
for j in cur:
update.append(j)
else:
# No tree in one neighbourhood of i is getting any better distance
# --> i is a local optimum and gets put into the output and deleted from things to work on
if not str(closer[i][0]) in output:
output[str(closer[i][0])] = closer[i][1]
# else:
# This would be the case if there are multiple paths that are considered to get
# to this optimal node
# print('Err: Found an interesting example?')
#closer.pop(i)
closer = update
# print('#FP Calculations : ', fp_count)
return (output)
# get_closer_o is a version without keeping track of already computed paths
def get_closer_o(s, trees, distance):
# Given a set of trees, a starting vertex and a current distance
# --> compute trees within one neighbourhood of that vertex that make the distance smaller
Nei = one_neighbourhood(expand(s))
output = []
for i in Nei:
# For each Neibour of start compute trees i that make distance smaller than it is currently
cur = 0
for j in trees:
path = len(findpath(collapse(i), collapse(j)))-1
globals.fp_count += 1
cur += path ** 2
# cur += path
# maybe only sum of distances -> think if that even makes sense
# cur += path
if (cur < distance):
# Maybe <= but that would be weird, look into that
output.append([i, cur])
return (output)
# centroid_o is a version without keeping track of already computed paths
def centroid_o(trees, s):
# Centroid search starting from s
# Initialization to run get_closer_function
globals.fp_count = 0
startdist = 0
for i in trees:
path = len(findpath(collapse(s), collapse(i)))-1
globals.fp_count += 1
startdist += path ** 2
closer = get_closer_o(s, trees, startdist)
output = {}
if not closer:
output[str(expand(s))] = startdist
else:
while bool(closer):
update = []
for i in range(len(closer)):
# for each tree that is closer
cur = get_closer_o(closer[i][0], trees, closer[i][1])
if bool(cur):
# there are trees that give a smaller distance = cur
# we need to add each tree to closer, i.e. check if there is anything in their neighbourhood
# which gives better distance
for j in cur:
update.append(j)
else:
# No tree in one neighbourhood of i is getting any better distance
# --> i is a local optimum and gets put into the output and deleted from things to work on
if not str(closer[i][0]) in output:
output[str(closer[i][0])] = closer[i][1]
# else:
# This would be the case if there are multiple paths that are considered to get
# to this optimal node
# print('Err: Found an interesting example?')
#closer.pop(i)
closer = update
# print('#FP Calculations : ',fp_count)
return (output)
######### Functions for Checking Centroid() #########
# for a set of trees compute the global minimum sum of squares in the treegraph(whole tree space graph)
def global_opt(trees,treegraph):
opt = sys.maxsize
for t in treegraph:
startdist = 0
for i in trees:
check = check_tracking(expand(t), expand(i))
if check == -1:
cur_p = findpath(collapse(t), collapse(i))
path = len(cur_p) - 1
update_tracking(cur_p)
else:
path = check
startdist += path ** 2
if startdist < opt:
opt = startdist
return(opt)
# for a set of trees compute the global minimum sum of squares in the treegraph(whole tree space graph)
# Version without tracking already computed paths
def slow_global_opt(trees,treegraph):
opt = sys.maxsize
for t in treegraph:
startdist = 0
for i in trees:
cur_p = findpath(collapse(t), collapse(i))
path = len(cur_p) - 1
startdist += path ** 2
if startdist < opt:
opt = startdist
return(opt)