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

Source Code for Module dsc_suite.ds.sequence_quintuple

  1  """module sequence_quintuple 
  2   
  3  module implementing the sequence quintuple data structure 
  4  """ 
  5  from dsc_suite.ds.data_structure import DataStructure 
  6  from dsc_suite.tools.combinatorics import EnumerativeCombinatorics 
  7  from dsc_suite.tools.graphtheory import longest_path 
  8  from dsc_suite.tools.geometry import overlap1d 
  9  from random import randint 
 10   
 11   
 12  ##### SEQUENCE TRIPLE SUBCLASS ################################################# 
13 -class SequenceQuintuple(DataStructure):
14 """ class SequenceQuintuple(DataStructure) - Sequence Quintuple implementation 15 16 Three sequences used similar as sequence pair. Published by the same group 17 in 2000 (Yamazaki2000). 18 19 based on five sequences, so called locii 20 sequence_quintuple format : [locii_1, locii_2, locii_3, locii_4, locii_5, block_rotations] 21 22 TODO: detailed docstring 23 """ 24 name = 'Sequence Quintuple' 25
26 - def __init__(self, benchmark):
27 assert(benchmark.status['number of dimensions'] == 3) 28 DataStructure.__init__(self, benchmark) 29 from operator import mul 30 from dsc_suite.tools.math import fak 31 # maybe better combined in a status dictionary 32 self.num_blocks = len(benchmark.blocks) 33 self.num_parts = 5 + 1 34 self.part_lengths = [fak(self.num_blocks)]*5 + [2**self.num_blocks] 35 self.num_representations = reduce(mul, self.part_lengths)
36 # if constructor call takes to long comment out 37 #self.update_balancing() 38 39
40 - def get_all_representations(self):
41 """ generate_abstract_soltioins() -> abstract_solutions 42 43 abstract_solutions ... list of all possible sequence triples 44 45 This method generates all possible sequence triples. 46 len(abstract_solutions) = n!^3, where n is the number of modules 47 """ 48 locii_1 = EnumerativeCombinatorics.permute(self.benchmark.blocks) 49 locii_2 = EnumerativeCombinatorics.permute(self.benchmark.blocks) 50 locii_3 = EnumerativeCombinatorics.permute(self.benchmark.blocks) 51 locii_4 = EnumerativeCombinatorics.permute(self.benchmark.blocks) 52 locii_5 = EnumerativeCombinatorics.permute(self.benchmark.blocks) 53 rotations = EnumerativeCombinatorics.vary([self.ORIGINAL, self.ROTATED], 54 len(self.benchmark.blocks)) 55 representations = [] 56 for L1 in locii_1: 57 for L2 in locii_2: 58 for L3 in locii_3: 59 for L4 in locii_4: 60 for L5 in locii_5: 61 for r in rotations: 62 representations.append([L1,L2,L3,L4,L5,r]) 63 return representations
64
65 - def get_part_of_representation(self, part_index, part_number):
66 """ 67 get a single element out of a part of the abstract 68 representation, part_number between 0 and part_lengths[part_index] 69 """ 70 # parameter part_index is not used here because all three 71 # sequences are equal, but for other data structures or by adding 72 # a rotation sequence, this parameter is useful 73 if 0 <= part_index <= 4: 74 return EnumerativeCombinatorics.get_permutation(self.benchmark.blocks, part_number) 75 elif part_index == 5: 76 return EnumerativeCombinatorics.get_variation([self.ORIGINAL, self.ROTATED], 77 len(self.benchmark.blocks), part_number)
78 79 # geometric relations 80 # x-direction, a left to b, b right to a
81 - def left_to(self, sequence_quintuple, a, b, 82 x_distance=None, y_distance=None, widths=None, heights=None):
83 locii1, locii2 = sequence_quintuple[0:2] 84 if ((locii1.index(a) < locii1.index(b)) and 85 (locii2.index(a) < locii2.index(b))): 86 return True 87 else: 88 return False
89 90 # y-direction, a in front of b, b behind a
91 - def in_front_of(self, sequence_quintuple, a, b, 92 x_distance=None, y_distance=None, widths=None, heights=None):
93 locii3, locii4 = sequence_quintuple[2:4] 94 if ((locii3.index(a) < locii3.index(b)) and 95 (locii4.index(a) < locii4.index(b))): 96 return True 97 else: 98 return False
99 100 101 # z-direction, a below b, b above a
102 - def below(self, sequence_quintuple, a, b, 103 x_distance=None, y_distance=None, widths=None, heights=None):
104 locii5 = sequence_quintuple[4] 105 if ((locii5.index(a) < locii5.index(b)) and 106 overlap1d(x_distance[a]-widths[a], x_distance[a], 107 x_distance[b]-widths[b], x_distance[b]) and 108 overlap1d(y_distance[a]-heights[a], y_distance[a], 109 y_distance[b]-heights[b], y_distance[b])): 110 return True 111 else: 112 return False
113 114 115 # i need to construct the constraint graphs 116 # the following constructs a constraint graph with transient edges
117 - def get_constraint_graph(self, sequence_quintuple, relation_function, 118 x_distance=None, y_distance=None, widths=None, heights=None):
119 cg = dict() 120 children = set() 121 for a in self.benchmark.blocks: 122 cg[a] = [] 123 b_list = list(self.benchmark.blocks) 124 b_list.remove(a) 125 for b in b_list: 126 if relation_function(sequence_quintuple, a, b, 127 x_distance, y_distance, widths, heights): 128 cg[a].append(b) 129 children.add(b) 130 # TODO: Attention! If Source is a module name it will overwriten. 131 cg['Source'] = list(set(self.benchmark.blocks) - children) 132 return cg
133 134 # depth, z-direction
135 - def get_dcg(self, sequence_triple):
137 138 # vielleicht doch lieber solution als parameter und dann 139 # sequence_triple und rotations, ... in ein tupel packen 140 # flexible (soft) blocks, rectilinear
141 - def create_packing(self, representation):
142 sequence_quintuple = representation[:5] 143 rotations = representation[5] 144 dims = self.benchmark.dimensions 145 widths = dict(zip(dims.keys(), zip(*dims.values())[0])) 146 heights = dict(zip(dims.keys(), zip(*dims.values())[1])) 147 depths = dict(zip(dims.keys(), zip(*dims.values())[2])) 148 for i in range(len(rotations)): 149 if rotations[i] == self.ROTATED: 150 block = self.benchmark.blocks[i] 151 widths[block], heights[block] = heights[block], widths[block] 152 x_distance, x_parent = longest_path(self.get_constraint_graph(sequence_quintuple, self.left_to), widths) 153 y_distance, y_parent = longest_path(self.get_constraint_graph(sequence_quintuple, self.in_front_of), heights) 154 z_distance, z_parent = longest_path(self.get_constraint_graph(sequence_quintuple, self.below, 155 x_distance, y_distance, 156 widths, heights), depths) 157 packing = dict() 158 for b in self.benchmark.blocks: 159 packing[b] = [x_distance[b]-widths[b], 160 y_distance[b]-heights[b], 161 z_distance[b]-depths[b], 162 widths[b], heights[b], depths[b]] 163 # TODO: Currently unused property of Sequence Triple, that while 164 # generating longest path, the outer dimensions are already 165 # obtained. This could simplify the cost evaluation. 166 return packing
167
168 - def packing_to_representation(self, packing):
169 print "Not implemented and/or available!"
170 171
172 - def get_operations(self):
173 """ 174 returns a dict of possible operations onto a abstract representation 175 {'name' : [function, globality_factor]} 176 globality_factor ... the higher, the bigger is the solution change 177 this factor is given by the authors but it also can be determined 178 in test runs evaluation the cost influences caused by applying the 179 according function. 180 """ 181 return {'Exchange 2 labels in 1 locii' : [self.exchange_two_labels_in_one_locii, 8], 182 'Exchange 2 labels in all locii' : [self.exchange_two_labels_in_all_locii, 4], 183 'Exchange 2 positions in all locii' : [self.exchange_two_positions_in_all_locii, 10], 184 'Exchange 2 locii' : [self.exchange_two_locii, 10], 185 'Rotate single block in z-plane': [self.rotate_single_block, 2]}
186 187
188 - def merge_representations(self, representation_a, representation_b):
189 """ Merge two representations into all possible children. 190 191 Typically, used for genetic and/or evolutionary algorithms. 192 Returns a list with all possible children. 193 194 In case of Sequence Quintuple all possible combinations of the 195 first, second, third, fourth and fifth sequence as well as the 196 rotation_list are generated. Rotations are currently completely 197 taken from representation a or b, respectively. 198 Thus 2^6 == 64 different children are possible. 199 """ 200 result = [] 201 for n in range(2**6): 202 child = [] 203 print '' 204 for i in range(6): 205 if n // 2**(5-i): 206 print '0', 207 child.append(representation_a[i]) 208 else: 209 print '1', 210 child.append(representation_b[i]) 211 n = n % 2**(5-i) 212 result.append(child) 213 return result
214 215
216 - def exchange_two_labels_in_one_locii(self, representation):
217 choice = randint(0,4) 218 sq = list(representation[:5]) 219 # old locii 220 locii = sq[choice] 221 pos1 = pos2 = randint(0, len(locii)-1) 222 while pos1 == pos2: 223 pos2 = randint(0, len(locii)-1) 224 if pos1 > pos2: 225 pos1, pos2 = pos2, pos1 226 # new locii 227 sq[choice] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:] 228 return sq+[representation[5]]
229
230 - def exchange_two_labels_in_all_locii(self, representation):
231 sq = list(representation[:5]) 232 lab1 = lab2 = sq[0][randint(0, len(sq[0])-1)] 233 while lab1 == lab2: 234 lab2 = sq[0][randint(0, len(sq[0])-1)] 235 for i in range(5): 236 # old locii 237 locii = sq[i] 238 pos1 = locii.index(lab1) 239 pos2 = locii.index(lab2) 240 if pos1 > pos2: 241 pos1, pos2 = pos2, pos1 242 # new locii 243 sq[i] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:] 244 return sq+[representation[5]]
245
246 - def exchange_two_positions_in_all_locii(self, representation):
247 sq = list(representation[:5]) 248 pos1 = pos2 = randint(0, len(sq[0])-1) 249 while pos1 == pos2: 250 pos2 = randint(0, len(sq[0])-1) 251 if pos1 > pos2: 252 pos1, pos2 = pos2, pos1 253 for i in range(5): 254 # old locii 255 locii = sq[i] 256 # new locii 257 sq[i] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:] 258 return sq+[representation[5]]
259
260 - def exchange_two_locii(self, representation):
261 sq = list(representation[:5]) 262 choice1 = choice2 = randint(0,4) 263 while choice1 == choice2: 264 choice2 = randint(0, 4) 265 temp = sq[choice1] 266 sq[choice1] = sq[choice2] 267 sq[choice2] = temp 268 return sq+[representation[5]]
269
270 - def rotate_single_block(self, representation):
271 rotations = list(representation[5]) 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[:5]+[rotations]
278