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

Source Code for Module dsc_suite.ds.sequence_triple

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