Package dsc_suite :: Package ds :: Module slicing_tree
[hide private]
[frames] | no frames]

Source Code for Module dsc_suite.ds.slicing_tree

  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  # sta element format: [tag, parent, left_child, right_child, 
 11  #                      x, y, z, width, height, depth]     
 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  # nur noch zu verstaendnisszwecken 
24 -class SlicingTreeArrayCell():
25 # attributes: tag, parent, left_child, right_child, 26 # x, y, z, width, height, depth 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
41 - def __str__(self):
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 # nur noch zu verstaendnisszwecken
58 -class SlicingTreeArray():
59 __data = list() 60
61 - def __init__(self, operation_variation, module_permutation, 62 topology, widths, heights, depths):
63 #assert(len(operation_variation) + 1 == len(module_permutation)) 64 #assert(len(operation_variation) + len(module_permutation) == len(topology)) 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 # slicing operation, super module 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 # leaf cell, module 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
91 - def __getitem__(self, i):
92 return self.__data[i]
93
94 - def __len__(self):
95 return len(self.__data)
96
97 - def __str__(self):
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
105 - def calc_dimensions(self, u=0, x=0, y=0, z=0):
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 # u is a leaf cell 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: # self[u].tag == 'Z' 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 ##### SLICING TREE SUBCLASS ####################################################
136 -class SlicingTree(DataStructure):
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
150 - def __init__(self, benchmark):
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 #self.update_balancing() 163 164
165 - def get_part_of_representation(self, part_index, part_number):
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 # parameter part_index is not used here because all three 171 # sequences are equal, but for other data structures or by adding 172 # a rotation sequence, this parameter is useful 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 # sta element format: [tag, parent, left_child, right_child, 184 # x, y, z, width, height, depth]
185 - def calc_dimensions(self, sta, u=0, x=0, y=0, z=0):
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 # u is a leaf cell 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: # sta[u].tag == 'Z' 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
213 - def create_packing(self, representation):
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 # slicing operation, super module 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 # leaf cell, module 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
272 - def packing_to_representation(self, packing):
273 print "Not implemented and/or available!"
274 275
276 - def get_operations(self):
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
290 - def merge_representations(self, representation_a, representation_b):
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
314 - def rotate_module(self, representation):
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
323 - def exchange_two_modules(self, representation):
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
331 - def rotate_slicing_plane(self, representation):
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
341 - def exchange_two_tree_nodes(self, representation):
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