1 """module slicing_tree
2
3 module implementing the slicing tree data structure
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 BinaryTrees as BT
8 from random import randint, randrange
9
10
11
12 STAE_TAG = 0
13 STAE_PARENT = 1
14 STAE_LEFT_CHILD = 2
15 STAE_RIGHT_CHILD = 3
16 STAE_X = 4
17 STAE_Y = 5
18 STAE_Z = 6
19 STAE_WIDTH = 7
20 STAE_HEIGHT = 8
21 STAE_DEPTH = 9
22
23
25
26
27
28 - def __init__(self, tag, parent, left_child, right_child,
29 x, y, z, width, height, depth):
30 self.tag = tag
31 self.parent = parent
32 self.left_child = left_child
33 self.right_child = right_child
34 self.x = x
35 self.y = y
36 self.z = z
37 self.width = width
38 self.height = height
39 self.depth = depth
40
42 if self.left_child:
43 return '%s-slice (%s, %s, %s) (%s x %s x %s)' % (self.tag,
44 self.parent,
45 self.left_child,
46 self.right_child,
47 self.width,
48 self.height,
49 self.depth)
50 else:
51 return '%s @ (%s, %s, %s) (%s x %s x %s)' % (self.tag, self.x,
52 self.y, self.z,
53 self.width,
54 self.height,
55 self.depth)
56
57
59 __data = list()
60
61 - def __init__(self, operation_variation, module_permutation,
62 topology, widths, heights, depths):
63
64
65 operation_variation = list(operation_variation)
66 module_permutation = list(module_permutation)
67 topology_relations = BT.generate_relations(topology)
68 i = 0
69 while i < len(topology):
70 if topology[i] == '1':
71
72 self.__data.append(SlicingTreeArrayCell(operation_variation.pop(0),
73 topology_relations[i][0],
74 topology_relations[i][1],
75 topology_relations[i][2],
76 None, None, None,
77 None, None, None))
78 else:
79
80 module_name = module_permutation.pop(0)
81 self.__data.append(SlicingTreeArrayCell(module_name,
82 topology_relations[i][0],
83 topology_relations[i][1],
84 topology_relations[i][2],
85 0, 0, 0,
86 widths[module_name],
87 heights[module_name],
88 depths[module_name]))
89 i += 1
90
93
96
98 temp = ''
99 i = 0
100 while i < len(self.__data):
101 temp += '%2i: %s\n' % (i, self.__data[i].__str__())
102 i += 1
103 return temp
104
106 self[u].x = x
107 self[u].y = y
108 self[u].z = z
109 if self[u].left_child:
110 left_child = self[u].left_child
111 right_child = self[u].right_child
112 else:
113 return
114 if self[u].tag == 'X':
115 self.calc_dimensions(left_child, x, y, z)
116 self.calc_dimensions(right_child, x + self[left_child].width, y, z)
117 self[u].width = self[left_child].width + self[right_child].width
118 self[u].height = max(self[left_child].height, self[right_child].height)
119 self[u].depth = max(self[left_child].depth, self[right_child].depth)
120 elif self[u].tag == 'Y':
121 self.calc_dimensions(left_child, x, y, z)
122 self.calc_dimensions(right_child, x, y + self[left_child].height, z)
123 self[u].width = max(self[left_child].width, self[right_child].width)
124 self[u].height = self[left_child].height + self[right_child].height
125 self[u].depth = max(self[left_child].depth, self[right_child].depth)
126 else:
127 self.calc_dimensions(left_child, x, y, z)
128 self.calc_dimensions(right_child, x, y, z + self[left_child].depth)
129 self[u].width = max(self[left_child].width, self[right_child].width)
130 self[u].height = max(self[left_child].height, self[right_child].height)
131 self[u].depth = self[left_child].depth + self[right_child].depth
132
133
134
135
137 """ class SlicingTree(DataStructure) - Slicing Tree implementation
138
139 Currently implemented as static array representation
140
141 slicing_tree format : [operation_variation, module_permutation,
142 topology, block_rotations]
143
144 rotations only 0 and 90 degrees
145
146 TODO: detailed docstring
147 """
148 name = '3D Slicing Tree'
149
151 assert(benchmark.status['number of dimensions'] == 3)
152 DataStructure.__init__(self, benchmark)
153 from operator import mul
154 self.num_blocks = len(benchmark.blocks)
155 self.num_slices = self.num_blocks - 1
156 self.num_parts = 3 + 1
157 self.part_lengths = [EC.get_num_variations(['X', 'Y', 'Z'], self.num_slices),
158 EC.get_num_permutations(benchmark.blocks),
159 BT.get_num_binary_trees(self.num_slices),
160 2**self.num_blocks]
161 self.num_representations = reduce(mul, self.part_lengths)
162
163
164
166 """
167 get a single element out of a part of the abstract
168 representation, part_number between 0 and part_lengths[part_index]
169 """
170
171
172
173 if part_index == 0:
174 return EC.get_variation(['X', 'Y', 'Z'], self.num_slices, part_number)
175 elif part_index == 1:
176 return EC.get_permutation(self.benchmark.blocks, part_number)
177 elif part_index == 2:
178 return BT.get_binary_tree(self.num_slices, part_number)
179 elif part_index == 3:
180 return EC.get_variation([self.ORIGINAL, self.ROTATED],
181 self.num_blocks, part_number)
182
183
184
186 sta[u][STAE_X] = x
187 sta[u][STAE_Y] = y
188 sta[u][STAE_Z] = z
189 if sta[u][STAE_LEFT_CHILD]:
190 left_child = sta[u][STAE_LEFT_CHILD]
191 right_child = sta[u][STAE_RIGHT_CHILD]
192 else:
193 return
194 if sta[u][STAE_TAG] == 'X':
195 self.calc_dimensions(sta, left_child, x, y, z)
196 self.calc_dimensions(sta, right_child, x + sta[left_child][STAE_WIDTH], y, z)
197 sta[u][STAE_WIDTH] = sta[left_child][STAE_WIDTH] + sta[right_child][STAE_WIDTH]
198 sta[u][STAE_HEIGHT] = max(sta[left_child][STAE_HEIGHT], sta[right_child][STAE_HEIGHT])
199 sta[u][STAE_DEPTH] = max(sta[left_child][STAE_DEPTH], sta[right_child][STAE_DEPTH])
200 elif sta[u][STAE_TAG] == 'Y':
201 self.calc_dimensions(sta, left_child, x, y, z)
202 self.calc_dimensions(sta, right_child, x, y + sta[left_child][STAE_HEIGHT], z)
203 sta[u][STAE_WIDTH] = max(sta[left_child][STAE_WIDTH], sta[right_child][STAE_WIDTH])
204 sta[u][STAE_HEIGHT] = sta[left_child][STAE_HEIGHT] + sta[right_child][STAE_HEIGHT]
205 sta[u][STAE_DEPTH] = max(sta[left_child][STAE_DEPTH], sta[right_child][STAE_DEPTH])
206 else:
207 self.calc_dimensions(sta, left_child, x, y, z)
208 self.calc_dimensions(sta, right_child, x, y, z + sta[left_child][STAE_DEPTH])
209 sta[u][STAE_WIDTH] = max(sta[left_child][STAE_WIDTH], sta[right_child][STAE_WIDTH])
210 sta[u][STAE_HEIGHT] = max(sta[left_child][STAE_HEIGHT], sta[right_child][STAE_HEIGHT])
211 sta[u][STAE_DEPTH] = sta[left_child][STAE_DEPTH] + sta[right_child][STAE_DEPTH]
212
214 """Return packing in dict format.
215
216 packing = {'name' : [x, y, z, w, h, d], ...}
217
218 """
219 operation_variation = list(representation[0])
220 module_permutation = list(representation[1])
221 topology = representation[2]
222 rotations = representation[3]
223 topology_relations = BT.generate_relations(topology)
224 dims = self.benchmark.dimensions
225 widths = dict(zip(dims.keys(), zip(*dims.values())[0]))
226 heights = dict(zip(dims.keys(), zip(*dims.values())[1]))
227 depths = dict(zip(dims.keys(), zip(*dims.values())[2]))
228 for i in range(len(rotations)):
229 if rotations[i] == self.ROTATED:
230 block = self.benchmark.blocks[i]
231 widths[block], heights[block] = heights[block], widths[block]
232 sta = list()
233 packing = dict()
234 i = 0
235 i_max = len(topology)
236 while i < i_max:
237 if topology[i] == '1':
238
239 sta.append([operation_variation.pop(0),
240 topology_relations[i][0],
241 topology_relations[i][1],
242 topology_relations[i][2],
243 None, None, None,
244 None, None, None])
245 else:
246
247 module_name = module_permutation.pop(0)
248 sta.append([module_name,
249 topology_relations[i][0],
250 topology_relations[i][1],
251 topology_relations[i][2],
252 0, 0, 0,
253 widths[module_name],
254 heights[module_name],
255 depths[module_name]])
256 i += 1
257 self.calc_dimensions(sta)
258 i = 0
259 i_max = len(sta)
260 while i < i_max:
261 if sta[i][STAE_TAG] in self.benchmark.blocks:
262 packing[sta[i][STAE_TAG]] = [sta[i][STAE_X],
263 sta[i][STAE_Y],
264 sta[i][STAE_Z],
265 sta[i][STAE_WIDTH],
266 sta[i][STAE_HEIGHT],
267 sta[i][STAE_DEPTH]]
268 i += 1
269 return packing
270
271
273 print "Not implemented and/or available!"
274
275
277 """
278 returns a dict of possible operations onto a abstract representation
279 {'name' : [function, globality_factor]}
280 globality_factor ... the higher, the bigger is the solution change
281 this factor is given by the authors but it also can be determined
282 in test runs evaluation the cost influences caused by applying the
283 according function.
284 """
285 return {'Exchange 2 modules' : [self.exchange_two_modules, 10],
286 'Rotate a slicing plane' : [self.rotate_slicing_plane, 20],
287 'Exchange 2 tree nodes' : [self.exchange_two_tree_nodes, 30],
288 'Rotate single block in plane (keep z)': [self.rotate_module, 1]}
289
291 """ Merge two representations into all possible children.
292
293 Typically, used for genetic and/or evolutionary algorithms.
294 Returns a list with all possible children.
295
296 In case of Slicing Tree all possible combinations of the
297 first, second and third sequence as well as the rotation_list
298 are generated. Rotations are currently completely taken from
299 representation a or b, respectively. Thus 2^4 different children
300 are possible.
301 """
302 result = []
303 for n in range(2**4):
304 child = []
305 for i in range(4):
306 if n // 2**(3-i):
307 child.append(representation_a[i])
308 else:
309 child.append(representation_b[i])
310 n = n % 2**(3-i)
311 result.append(child)
312 return result
313
315 rotations = list(representation[3])
316 index = randint(0, len(rotations)-1)
317 if rotations[index] == self.ORIGINAL:
318 rotations[index] = self.ROTATED
319 else:
320 rotations[index] = self.ORIGINAL
321 return representation[:3]+[rotations]
322
324 module_permutations = list(representation[1])
325 pos1 = pos2 = randint(0, len(module_permutations)-1)
326 while pos1 == pos2:
327 pos2 = randint(0, len(module_permutations)-1)
328 module_permutations[pos1], module_permutations[pos2] = module_permutations[pos2], module_permutations[pos1]
329 return [representation[0]] + [module_permutations] + representation[2:]
330
332 operation_variation = list(representation[0])
333 pos = randint(0, len(operation_variation)-1)
334 shift = randint(1, 2)
335 operations = ['X', 'Y', 'Z']
336 old_index = operations.index(operation_variation[pos])
337 new_index = (old_index + shift) % 3
338 operation_variation[pos] = operations[new_index]
339 return [operation_variation] + representation[1:]
340
342 """
343 includes the special case where two modules are exchanged
344 so maybe the exclusive module exchange function can be ommited
345 """
346 slicings = representation[0]
347 module_names = representation[1]
348 topology = representation[2]
349 first_pos = randint(1, len(topology)-1)
350 counter = 2
351 pos = 0
352 ones = 1
353 zeros = 0
354 while pos < first_pos:
355 pos = pos + 1
356 if topology[pos] == '1':
357 ones += 1
358 else:
359 zeros += 1
360 if topology[pos] == '0':
361 first_module_start = zeros-1
362 first_module_end = zeros
363 first_slicing_start = ones
364 first_slicing_end = ones
365 else:
366 first_module_start = zeros
367 first_slicing_start = ones-1
368 while counter > 0:
369 pos = pos + 1
370 if topology[pos] == '1':
371 counter += 1
372 ones += 1
373 else:
374 counter -=1
375 zeros += 1
376 first_module_end = zeros
377 first_slicing_end = ones
378 first_end = pos
379 second_choice = range(1, first_pos) + range(first_end+1, len(topology))
380 overlap = True
381 while overlap:
382 overlap = False
383 second_pos = second_choice[randrange(len(second_choice))]
384 counter = 2
385 pos = 0
386 ones = 1
387 zeros = 0
388 while pos < second_pos:
389 pos = pos + 1
390 if topology[pos] == '1':
391 ones += 1
392 else:
393 zeros += 1
394 if topology[pos] == '0':
395 second_module_start = zeros-1
396 second_module_end = zeros
397 second_slicing_start = ones
398 second_slicing_end = ones
399 else:
400 second_module_start = zeros
401 second_slicing_start = ones-1
402 while counter > 0:
403 pos = pos + 1
404 if pos == first_pos:
405 second_choice.remove(second_pos)
406 overlap = True
407 break
408 if topology[pos] == '1':
409 counter += 1
410 ones += 1
411 else:
412 counter -=1
413 zeros += 1
414 second_module_end = zeros
415 second_slicing_end = ones
416 second_end = pos
417 if first_pos < second_pos:
418 to = topology[:first_pos] + topology[second_pos:second_end] + \
419 topology[first_end:second_pos] + topology[first_pos:first_end] + \
420 topology[second_end:]
421 mn = module_names[:first_module_start] + module_names[second_module_start:second_module_end] + \
422 module_names[first_module_end:second_module_start] + module_names[first_module_start:first_module_end] + \
423 module_names[second_module_end:]
424 sl = slicings[:first_slicing_start] + slicings[second_slicing_start:second_slicing_end] + \
425 slicings[first_slicing_end:second_slicing_start] + slicings[first_slicing_start:first_slicing_end] + \
426 slicings[second_slicing_end:]
427 else:
428 to = topology[:second_pos] + topology[first_pos:first_end] + \
429 topology[second_end:first_pos] + topology[second_pos:second_end] + \
430 topology[first_end:]
431 mn = module_names[:second_module_start] + module_names[first_module_start:first_module_end] + \
432 module_names[second_module_end:first_module_start] + module_names[second_module_start:second_module_end] + \
433 module_names[first_module_end:]
434 sl = slicings[:second_slicing_start] + slicings[first_slicing_start:first_slicing_end] + \
435 slicings[second_slicing_end:first_slicing_start] + slicings[second_slicing_start:second_slicing_end] + \
436 slicings[first_slicing_end:]
437 return [sl, mn, to] + representation[3:]
438