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
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
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
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
35
36
37
58
72
73
74
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
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
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
108
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
121 cg['Source'] = list(set(self.benchmark.blocks) - children)
122 return cg
123
124
125 - def get_hcg(self, sequence_triple):
127
128
129 - def get_vcg(self, sequence_triple):
131
132
133 - def get_dcg(self, sequence_triple):
135
136
137
138
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
161
162
163 return packing
164
166 print "Not implemented and/or available!"
167
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
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
208 choice = randint(0,2)
209 st = list(representation[:3])
210
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
218 st[choice] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:]
219 return st+[representation[3]]
220
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
228 locii = st[i]
229 pos1 = locii.index(lab1)
230 pos2 = locii.index(lab2)
231 if pos1 > pos2:
232 pos1, pos2 = pos2, pos1
233
234 st[i] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:]
235 return st+[representation[3]]
236
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
246 locii = st[i]
247
248 st[i] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:]
249 return st+[representation[3]]
250
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
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