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
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
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
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
37
38
39
64
78
79
80
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
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
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
116
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
131 cg['Source'] = list(set(self.benchmark.blocks) - children)
132 return cg
133
134
135 - def get_dcg(self, sequence_triple):
137
138
139
140
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
164
165
166 return packing
167
169 print "Not implemented and/or available!"
170
171
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
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
217 choice = randint(0,4)
218 sq = list(representation[:5])
219
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
227 sq[choice] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:]
228 return sq+[representation[5]]
229
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
237 locii = sq[i]
238 pos1 = locii.index(lab1)
239 pos2 = locii.index(lab2)
240 if pos1 > pos2:
241 pos1, pos2 = pos2, pos1
242
243 sq[i] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:]
244 return sq+[representation[5]]
245
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
255 locii = sq[i]
256
257 sq[i] = locii[:pos1]+[locii[pos2]]+locii[pos1+1:pos2]+[locii[pos1]]+locii[pos2+1:]
258 return sq+[representation[5]]
259
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
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