1 """module slicing_tree
2
3 Module implementing the T-Tree data structure [Yuh2004a, Yuh2009].
4 """
5 from dsc_suite.ds.data_structure import DataStructure
6 from dsc_suite.tools.combinatorics import EnumerativeCombinatorics as EC
7 from dsc_suite.tools.graphtheory import TernaryTrees as TT
8 from dsc_suite.tools.geometry import overlap2d
9 from random import randrange, randint
10
11
12
13 -class TTree(DataStructure):
14 """ class TTree(DataStructure) - T-Tree implementation
15
16 t_tree format : [module_permutation, topology, module_rotations]
17
18 ternary tree topology is in a list format where each entry
19 represents a node. The index of the root node is also returned.
20 panholzer = ([[LEFT, MIDDLE, RIGHT, PARENT, INTERNAL, DEPTH], ...], root)
21 topology = TT.transform_panholzer_to_topology(T, root)
22
23 rotations only 0 and 90 degrees
24
25 TODO: detailed docstring,
26 verification and rectification step needed after applying permutation operations
27 """
28 name = 'T-Tree'
29
30
31 __H_NAME = 0
32 __H_PARENT = 1
33 __H_LEFT_CHILD = 2
34 __H_MIDDLE_CHILD = 3
35 __H_RIGHT_CHILD = 4
36 __H_WIDTH = 5
37 __H_HEIGHT = 6
38 __H_DEPTH = 7
39 __H_X = 8
40 __H_Y = 9
41 __H_Z = 10
42
44 assert(benchmark.status['number of dimensions'] == 3)
45 DataStructure.__init__(self, benchmark)
46 from operator import mul
47 self.num_blocks = len(benchmark.blocks)
48 self.num_slices = self.num_blocks - 1
49 self.num_parts = 2 + 1
50 self.part_lengths = [EC.get_num_permutations(benchmark.blocks),
51 TT.get_num_ternary_trees(self.num_blocks),
52 2**self.num_blocks]
53 self.num_representations = reduce(mul, self.part_lengths)
54
55
57 """ insert into horizontal contour
58 c ... contour, initially c = [[0,0]]
59 """
60 temp = list(c)
61 temp.sort()
62 y = 0
63 y_old = -1
64 corner = False
65 for i in temp:
66 if i[0] >= x1 and i[0] < x2:
67 y_old = i[1]
68 y = max(y, y_old)
69 c.remove(i)
70 elif i[0] == x2:
71 y_old = i[1]
72 c.remove(i)
73 if i[0] == x1:
74 corner = True
75 c.append([x1, y+height])
76 c.append([x2, y_old])
77 c.sort()
78 i = c.index([x1, y+height])
79 if i > 0 and not corner:
80 y = max(y, c[i-1][1])
81 c[i][1] = y+height
82 if y_old < 0:
83 c[i+1][1] = c[i-1][1]
84 if c[i][1] == c[i+1][1]:
85 c.remove(c[i+1])
86 if i > 0 and c[i-1][1] == c[i][1]:
87 c.remove(c[i])
88 return y
89
91 """
92 S ... a stack
93 n ... a node of T-Tree
94 """
95 S_ = []
96 b_root = n
97 S_.append(n)
98 while len(S_) > 0:
99 m = S_.pop()
100 m_mc = H[m][self.__H_MIDDLE_CHILD]
101 m_lc = H[m][self.__H_LEFT_CHILD]
102 m_rc = H[m][self.__H_RIGHT_CHILD]
103 if not m_mc == None:
104 S_.append(m_mc)
105 if not m_lc == None:
106 S_.append(m_lc)
107 if not m_rc == None:
108 S.append(m_rc)
109 return b_root
110
118
144
145
165
166
179
181 """ DFS list structure used by t-tree packing algorithm.
182 H = [[name, parent, left, middle, right, width, height, depth, x, y, z], ...]
183 """
184 module_permutation, topology, module_rotations = t_tree
185 H = []
186 for i in range(len(topology)):
187 name = module_permutation[i]
188 parent, left_child, middle_child, right_child = topology[i]
189 width, height, depth = dimensions[name]
190 if module_rotations[i] == 1:
191 width, height = height, width
192 H.append([name, parent, left_child, middle_child, right_child,
193 width, height, depth, 0, 0, 0])
194 return H
195
197 """Return packing in dict format.
198
199 packing = {'name' : [x, y, z, w, h, d], ...}
200
201 """
202 """ packing algorithm needs topology in DFS order format """
203 H = self.__CreateH(representation, self.benchmark.dimensions)
204 self.__TreePacking(H)
205 packing = {}
206 for node in H:
207 packing[node[self.__H_NAME]] = [node[self.__H_X],
208 node[self.__H_Y],
209 node[self.__H_Z],
210 node[self.__H_WIDTH],
211 node[self.__H_HEIGHT],
212 node[self.__H_DEPTH]]
213 return packing
214
228
230 print "Not implemented and/or available!"
231
233 """
234 returns a dict of possible operations onto a abstract representation
235 {'name' : [function, globality_factor]}
236 globality_factor ... the higher, the bigger is the solution change
237 this factor is given by the authors but it also can be determined
238 in test runs evaluation the cost influences caused by applying the
239 according function.
240 """
241 return {'Move node' : [self.move_node_in_topology, 30],
242 'Swap two modules' : [self.swap_two_modules, 20],
243 'Rotate single block in plane (keep z)': [self.rotate_module, 10]}
244
245
247 """ Merge two representations into all possible children.
248
249 Typically, used for genetic and/or evolutionary algorithms.
250 Returns a list with all possible children.
251
252 In case of T-Tree all possible combinations of the
253 module permutations, topologies second and rotations
254 are generated. Rotations are currently completely taken from
255 representation a or b, respectively. Thus 2^3 different children
256 are possible.
257 """
258 result = []
259 for n in range(2**3):
260 child = []
261 for i in range(3):
262 if n // 2**(2-i):
263 child.append(representation_a[i])
264 else:
265 child.append(representation_b[i])
266 n = n % 2**(2-i)
267 result.append(child)
268 return result
269
271 rotations = list(representation[2])
272 index = randint(0, len(rotations)-1)
273 if rotations[index] == self.ORIGINAL:
274 rotations[index] = self.ROTATED
275 else:
276 rotations[index] = self.ORIGINAL
277 return representation[:2]+[rotations]
278
280 module_permutations = list(representation[0])
281 pos1 = pos2 = randint(0, len(module_permutations)-1)
282 while pos1 == pos2:
283 pos2 = randint(0, len(module_permutations)-1)
284 module_permutations[pos1], module_permutations[pos2] = module_permutations[pos2], module_permutations[pos1]
285 return [module_permutations] + representation[1:]
286
288 """ Decrease value by 1 if not None. """
289 if value == None or value < boundary:
290 return value
291 else:
292 return value - 1
293
295 """ Increase value by 1 if not None. """
296 if value == None or value < boundary:
297 return value
298 else:
299 return value + 1
300
302 RETURN_POSITIONS = False
303 module_permutations = list(representation[0])
304 topology = list(representation[1])
305
306 pos = randint(0, len(module_permutations)-1)
307 initial_pos = pos
308
309 if topology[pos][1:] == [None, None, None]:
310 module_name = module_permutations.pop(pos)
311 parent = topology[pos][0]
312 index = topology[parent].index(pos)
313 topology[parent] = topology[parent][0:index] + [None] + topology[parent][index+1:]
314 del topology[pos]
315 for i in range(len(topology)):
316 topology[i] = map(lambda x: self.__decrease(x, pos), topology[i])
317
318 elif topology[pos][1:].count(None) == 2:
319 module_name = module_permutations.pop(pos)
320 child = filter(lambda x: not x == None, topology[pos][1:])[0]
321 parent = topology[pos][0]
322 if not parent == None:
323 index = topology[parent].index(pos)
324 topology[parent] = topology[parent][0:index] + [child] + topology[parent][index+1:]
325 topology[child] = [parent] + topology[child][1:]
326 del topology[pos]
327 for i in range(len(topology)):
328 topology[i] = map(lambda x: self.__decrease(x, pos), topology[i])
329
330 else:
331 module_name = module_permutations.pop(pos)
332 children = filter(lambda x: not x == None, topology[pos][1:])
333 while len(children) > 0:
334 child = children[randrange(len(children))]
335 child_name = module_permutations.pop(child-1)
336 module_permutations.insert(pos, child_name)
337 pos = child
338 children = filter(lambda x: not x == None, topology[pos][1:])
339 parent = topology[pos][0]
340 index = topology[parent].index(pos)
341 topology[parent] = topology[parent][0:index] + [None] + topology[parent][index+1:]
342 del topology[pos]
343 for i in range(len(topology)):
344 topology[i] = map(lambda x: self.__decrease(x, pos), topology[i])
345
346
347
348 pos = randint(0, 5*len(module_permutations))
349
350 if pos < 2*len(module_permutations)+1:
351 counter = -1
352 for i in range(len(topology)):
353 for j in range(3):
354 if topology[i][j+1] == None:
355 counter += 1
356 if counter == pos:
357 insert_pos = i
358 insert_branch = j
359 break
360 if counter == pos:
361 break
362 next_left = [topology[insert_pos][1:][i] for i in range(insert_branch)]
363 next_left = filter(lambda x: not x == None, next_left)
364 if next_left == []:
365 new_pos = insert_pos + 1
366 else:
367 next = next_left[-1]
368 while not topology[next][1:] == [None, None, None]:
369 next = filter(lambda x: not x == None, topology[next][1:])[-1]
370 new_pos = next + 1
371 for i in range(len(topology)):
372 topology[i] = map(lambda x: self.__increase(x, new_pos), topology[i])
373 topology.insert(new_pos, [insert_pos, None, None, None])
374 topology[insert_pos] = topology[insert_pos][0:insert_branch+1] + [new_pos] + topology[insert_pos][insert_branch+2:]
375 module_permutations.insert(new_pos, module_name)
376 modified_pos = new_pos
377
378 else:
379 pos -= 2*len(module_permutations)+1
380 branch = pos % 3
381 pos = pos // 3
382 parent = topology[pos][0]
383 for i in range(len(topology)):
384 topology[i] = map(lambda x: self.__increase(x, pos), topology[i])
385 topology.insert(pos, [parent, None, None, None])
386 topology[pos] = topology[pos][0:branch+1] + [pos+1] + topology[pos][branch+2:]
387 topology[pos+1] = [pos] + topology[pos+1][1:]
388 if not parent == None:
389 ref_index = topology[parent].index(pos+1)
390 topology[parent] = topology[parent][0:ref_index] + [pos] + topology[parent][ref_index+1:]
391 module_permutations.insert(pos, module_name)
392 modified_pos = pos
393 if RETURN_POSITIONS:
394 return initial_pos, modified_pos, [module_permutations, topology, representation[2]]
395 else:
396 return [module_permutations, topology, representation[2]]
397