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

Source Code for Module dsc_suite.ds.t_tree

  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  ##### T-TREE SUBCLASS #################################################### 
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 # H data constants 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
43 - def __init__(self, benchmark):
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 #self.update_balancing() 55
56 - def __UpdateContour(self, c, x1, x2, height):
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
90 - def __TreeDecomposition(self, n, S, H):
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
111 - def __FindMaxX(self, n, L, H):
112 temp = filter(lambda m: overlap2d(H[n][self.__H_Y], H[n][self.__H_Y] + H[n][self.__H_HEIGHT], 113 H[n][self.__H_Z], H[n][self.__H_Z] + H[n][self.__H_DEPTH], 114 H[m][self.__H_Y], H[m][self.__H_Y] + H[m][self.__H_HEIGHT], 115 H[m][self.__H_Z], H[m][self.__H_Z] + H[m][self.__H_DEPTH]), L) 116 temp = map(lambda m: H[m][self.__H_X] + H[m][self.__H_WIDTH], temp) + [0] 117 return max(temp)
118
119 - def __PlaceModule(self, n, L, H, contour):
120 """ 121 n ... a node of a binary tree 122 L ... a list to store nodes 123 """ 124 if H[n][self.__H_PARENT] == None: 125 H[n][self.__H_Z] = 0 126 H[n][self.__H_Y] = self.__UpdateContour(contour, 0, 127 H[n][self.__H_WIDTH], 128 H[n][self.__H_HEIGHT]) 129 H[n][self.__H_X] = 0 130 L.append(n) 131 return 132 # n is left child 133 parent = H[n][self.__H_PARENT] 134 if H[parent][self.__H_LEFT_CHILD] == n: 135 H[n][self.__H_Z] = H[parent][self.__H_Z] + H[parent][self.__H_DEPTH] 136 else: 137 H[n][self.__H_Z] = H[parent][self.__H_Z] 138 H[n][self.__H_Y] = self.__UpdateContour(contour, 139 H[n][self.__H_Z], 140 H[n][self.__H_Z] + H[n][self.__H_DEPTH], 141 H[n][self.__H_HEIGHT]) 142 H[n][self.__H_X] = self.__FindMaxX(n, L, H) 143 L.append(n)
144 145
146 - def __BinaryTreePacking(self, b_root, H, L):
147 S = [] 148 p = b_root 149 if H[p][self.__H_PARENT] == None: 150 contour = [[0,0]] 151 else: 152 contour = [[0,H[H[p][self.__H_PARENT]][self.__H_Y]]] 153 self.__PlaceModule(p, L, H, contour) 154 if not H[p][self.__H_MIDDLE_CHILD] == None: 155 S.append(H[p][self.__H_MIDDLE_CHILD]) 156 if not H[p][self.__H_LEFT_CHILD] == None: 157 S.append(H[p][self.__H_LEFT_CHILD]) 158 while len(S) > 0: 159 p = S.pop() 160 self.__PlaceModule(p, L, H, contour) 161 if not H[p][self.__H_MIDDLE_CHILD] == None: 162 S.append(H[p][self.__H_MIDDLE_CHILD]) 163 if not H[p][self.__H_LEFT_CHILD] == None: 164 S.append(H[p][self.__H_LEFT_CHILD])
165 166
167 - def __TreePacking(self, H):
168 """ Tree packing process described in [Yuh2009] 169 H ... a T-Tree 170 """ 171 S = [] 172 L = [] 173 b_root = self.__TreeDecomposition(0, S, H) 174 self.__BinaryTreePacking(b_root, H, L) 175 while len(S) > 0: 176 n = S.pop() 177 b_root = self.__TreeDecomposition(n, S, H) 178 self.__BinaryTreePacking(b_root, H, L)
179
180 - def __CreateH(self, t_tree, dimensions):
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
196 - def create_packing(self, representation):
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
216 # generate random module permutation 217 module_permutation = EC.get_permutation(self.benchmark.blocks, 218 randrange(self.part_lengths[0])) 219 # generate random ternary tree topology 220 T, root = TT.get_random_ternary_tree(self.num_blocks) 221 topology = TT.transform_panholzer_to_topology(T, root) 222 # generate random module_rotations 223 module_rotations = EC.get_variation([self.ORIGINAL, self.ROTATED], 224 self.num_blocks, 225 randrange(self.part_lengths[2])) 226 # return as t_tree format 227 return [module_permutation, topology, module_rotations]
228
229 - def packing_to_representation(self, packing):
230 print "Not implemented and/or available!"
231
232 - def get_operations(self):
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 # + evtl. exchange subtrees 245
246 - def merge_representations(self, representation_a, representation_b):
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
270 - def rotate_module(self, representation):
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
279 - def swap_two_modules(self, representation):
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
287 - def __decrease(self, value, boundary):
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
294 - def __increase(self, value, boundary):
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
301 - def move_node_in_topology(self, representation):
302 RETURN_POSITIONS = False 303 module_permutations = list(representation[0]) 304 topology = list(representation[1]) # in DFS order 305 # pick node X and cut it out 306 pos = randint(0, len(module_permutations)-1) 307 initial_pos = pos 308 # X is leaf node -> cut it 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 # X is inner node with only one child 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 # X has two or three children 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 # paste this node somewhere else 346 # either inner node with a random branch (n*3 possibilities ) 347 # or external node (n*2+1 possibilities) 348 pos = randint(0, 5*len(module_permutations)) 349 # insert as external node 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 # insert as new internal node (including root) 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