$darkmode
DENOPTIM
APMapFinderTest.java
Go to the documentation of this file.
1/*
2 * DENOPTIM
3 * Copyright (C) 2022 Marco Foscato <marco.foscato@uib.no>
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as published
7 * by the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19package denoptim.fragspace;
20
21import static org.junit.jupiter.api.Assertions.assertEquals;
22import static org.junit.jupiter.api.Assertions.assertTrue;
23
24import java.util.ArrayList;
25import java.util.HashMap;
26import java.util.HashSet;
27import java.util.LinkedHashMap;
28import java.util.List;
29
30import org.junit.jupiter.api.Test;
31
32import denoptim.exception.DENOPTIMException;
33import denoptim.graph.APClass;
34import denoptim.graph.APMapping;
35import denoptim.graph.AttachmentPoint;
36import denoptim.graph.DGraph;
37import denoptim.graph.Edge;
38import denoptim.graph.EmptyVertex;
39import denoptim.graph.Vertex;
40import denoptim.graph.Vertex.BBType;
41
48public class APMapFinderTest
49{
50 private static APClass APCA, APCB, APCC, APCD, APCE;
51
52//------------------------------------------------------------------------------
53
54 private FragmentSpace prepare() throws DENOPTIMException
55 {
56 APCA = APClass.make("A", 0);
57 APCB = APClass.make("B", 0);
58 APCC = APClass.make("C", 0);
59 APCD = APClass.make("D", 99);
60 APCE = APClass.make("E", 13);
61
62 HashMap<APClass,ArrayList<APClass>> cpMap =
63 new HashMap<APClass,ArrayList<APClass>>();
64 ArrayList<APClass> lstA = new ArrayList<APClass>();
65 lstA.add(APCA);
66 cpMap.put(APCA, lstA);
67 ArrayList<APClass> lstB = new ArrayList<APClass>();
68 lstB.add(APCB);
69 lstB.add(APCC);
70 cpMap.put(APCB, lstB);
71 ArrayList<APClass> lstC = new ArrayList<APClass>();
72 lstC.add(APCB);
73 lstC.add(APCC);
74 cpMap.put(APCC, lstC);
75 ArrayList<APClass> lstD = new ArrayList<APClass>();
76 lstD.add(APCD);
77 cpMap.put(APCD, lstD);
78 ArrayList<APClass> lstE = new ArrayList<APClass>();
79 lstE.add(APCE);
80 cpMap.put(APCE, lstE);
81
82
83 /* Compatibility matrix
84 *
85 * | A | B | C | D | E | F
86 * ---------------------------------
87 * A | T | | | | |
88 * ---------------------------------
89 * B | | T | T | | |
90 * ---------------------------------
91 * C | | T | T | | |
92 * ---------------------------------
93 * D | | | | T | |
94 * ---------------------------------
95 * E | | | | | T |
96 * ---------------------------------
97 * F | | | | | |
98 *
99 * NB: F has NONE!
100 */
101
102 HashMap<APClass,APClass> capMap = new HashMap<APClass,APClass>();
103 HashSet<APClass> forbEnds = new HashSet<APClass>();
104
105 FragmentSpaceParameters fsp = new FragmentSpaceParameters();
106 FragmentSpace fs = new FragmentSpace(fsp,
107 new ArrayList<Vertex>(),
108 new ArrayList<Vertex>(),
109 new ArrayList<Vertex>(),
110 cpMap, capMap, forbEnds, cpMap);
111 fs.setAPclassBasedApproach(true);
112
113 return fs;
114 }
115
116//------------------------------------------------------------------------------
117
118 @Test
119 public void testAPMapFinder_Constrained() throws Exception
120 {
121 FragmentSpace fs = prepare();
122 EmptyVertex vA = new EmptyVertex();
123 vA.setBuildingBlockType(BBType.FRAGMENT);
124 vA.addAP(APCA);
125 vA.addAP(APCA);
126 vA.addAP(APCA);
127 vA.addAP(APCD);
128
129 EmptyVertex vB = new EmptyVertex();
130 vB.setBuildingBlockType(BBType.FRAGMENT);
131 vB.addAP(APCD);
132 vB.addAP(APCD);
133 vB.addAP(APCA);
134 vB.addAP(APCA);
135 vB.addAP(APCA);
136
137 APMapping constrain = new APMapping();
138 constrain.put(vA.getAP(2), vB.getAP(4));
139 APMapFinder apmf = new APMapFinder(fs,vA,vB,constrain,true,false,false);
140
141 assertTrue(apmf.foundMapping());
142 assertEquals(21, apmf.getAllAPMappings().size());
143 for (APMapping apm : apmf.getAllAPMappings())
144 {
145 assertTrue(apm.containsKey(vA.getAP(2)));
146 assertEquals(vB.getAP(4), apm.get(vA.getAP(2)));
147 }
148 }
149
150//------------------------------------------------------------------------------
151
152 @Test
153 public void testAPMapFinder_ConstrainAll() throws Exception
154 {
155 FragmentSpace fs = prepare();
156 EmptyVertex vA = new EmptyVertex();
157 vA.setBuildingBlockType(BBType.FRAGMENT);
158 vA.addAP(APCA);
159
160 EmptyVertex vB = new EmptyVertex();
161 vB.setBuildingBlockType(BBType.FRAGMENT);
162 vB.addAP(APCA);
163
164 // NB "all" in "ConstrainAll" means that a single constraint covers all APs
165 APMapping constrain = new APMapping();
166 constrain.put(vA.getAP(0), vB.getAP(0));
167 APMapFinder apmf = new APMapFinder(fs,vA,vB,constrain,true,false,false);
168
169 assertTrue(apmf.foundMapping());
170 assertEquals(1, apmf.getAllAPMappings().size());
171 assertTrue(apmf.getChosenAPMapping().containsKey(vA.getAP(0)));
172 assertEquals(vB.getAP(0), apmf.getChosenAPMapping().get(vA.getAP(0)));
173 }
174
175//------------------------------------------------------------------------------
176
177 @Test
178 public void testAPMapFinder() throws Exception
179 {
180 FragmentSpace fs = prepare();
181 EmptyVertex vA = new EmptyVertex();
182 vA.setBuildingBlockType(BBType.FRAGMENT);
183 vA.addAP(APCA);
184 vA.addAP(APCD);
185
186 EmptyVertex vB = new EmptyVertex();
187 vB.setBuildingBlockType(BBType.FRAGMENT);
188 vB.addAP(APCA);
189 vB.addAP(APCD);
190
191 // NB: when APs are NOT used, the mapping is permissive and is happy
192 // to find "a" AP to map another AP with, irrespectively on the APClass
193
194 APMapFinder apmf = new APMapFinder(fs, vA, vB, true);
195
196 assertTrue(apmf.foundMapping());
197 assertEquals(6, apmf.getAllAPMappings().size());
198 assertEquals(4, apmf.getAllAPMappings()
199 .stream().filter(m -> m.size()==1)
200 .count());
201 assertEquals(2, apmf.getAllAPMappings()
202 .stream().filter(m -> m.size()==2)
203 .count());
204 assertEquals(4, apmf.getAllAPMappings()
205 .stream()
206 .filter(m -> m.containsKey(vA.getAP(0)))
207 .count());
208 assertEquals(2, apmf.getAllAPMappings()
209 .stream()
210 .filter(m -> m.size()==2)
211 .filter(m -> m.containsKey(vA.getAP(0)))
212 .count());
213
214 //: we can restrict to all mappings that cover all APs on first vertex
215 apmf = new APMapFinder(fs, vA, vB, null, true, true, true);
216
217 assertTrue(apmf.foundMapping());
218 assertEquals(2, apmf.getAllAPMappings().size());
219
220 // testing for handling of used APs
221
222 EmptyVertex vC = new EmptyVertex();
223 vC.setBuildingBlockType(BBType.FRAGMENT);
224 vC.addAP(APCA);
225 vC.addAP(APCD);
226
227 EmptyVertex vD = new EmptyVertex();
228 vD.setBuildingBlockType(BBType.FRAGMENT);
229 vD.addAP(APCA);
230 vD.addAP(APCD);
231
232 DGraph g = new DGraph();
233 g.addVertex(vA);
234 g.addVertex(vB);
235 g.addVertex(vC);
236 g.addVertex(vD);
237 g.addEdge(new Edge(vA.getAP(0), vC.getAP(0)));
238 g.addEdge(new Edge(vA.getAP(1), vD.getAP(1)));
239 g.addEdge(new Edge(vB.getAP(1), vC.getAP(1)));
240 g.addEdge(new Edge(vB.getAP(0), vD.getAP(0)));
241
242 // NB: when APs are used the mapping is much more restrictive,
243 // because it is forced to respect the APClass compatibility rules.
244
245 apmf = new APMapFinder(fs, vA, vB, true);
246
247 assertTrue(apmf.foundMapping());
248 assertEquals(1, apmf.getAllAPMappings().size());
249 assertEquals(1, apmf.getAllAPMappings()
250 .stream().filter(m -> m.size()==2)
251 .count());
252 assertEquals(1, apmf.getAllAPMappings()
253 .stream()
254 .filter(m -> m.containsKey(vA.getAP(0)))
255 .count());
256
257 // When considering different APClasses, the compatibility matrix matters.
258
259 EmptyVertex vF = new EmptyVertex();
260 vF.setBuildingBlockType(BBType.FRAGMENT);
261 vF.addAP(APCB);
262
263 EmptyVertex vG = new EmptyVertex();
264 vG.setBuildingBlockType(BBType.FRAGMENT);
265 vG.addAP(APCC);
266
267 DGraph g2 = new DGraph();
268 g2.addVertex(vF);
269 g2.addVertex(vG);
270 g2.addEdge(new Edge(vF.getAP(0), vG.getAP(0)));
271
272 apmf = new APMapFinder(fs, vF, vG, true);
273
274 assertTrue(apmf.foundMapping());
275 assertEquals(vG.getAP(0), apmf.getChosenAPMapping().get(vF.getAP(0)));
276 }
277
278//------------------------------------------------------------------------------
279
280 /*
281 * Here we test the change of mapping with different APClass compatibility
282 * matrixes.
283 */
284 @Test
285 public void testFindMappingCompatibileAPs() throws Exception
286 {
287 APClass APCO0 = APClass.make("o", 0);
288 APClass APCP0 = APClass.make("p", 0);
289 APClass APCO1 = APClass.make("o", 1);
290 APClass APCP1 = APClass.make("p", 1);
291 APClass APCQ0 = APClass.make("q", 0);
292 APClass APCQ1 = APClass.make("q", 1);
293
294 // Build a pair naked vertexes
295 EmptyVertex f0 = new EmptyVertex(0);
296 f0.addAP(APCO0);
297 f0.addAP(APCP0);
298 f0.addAP(APCP1);
299
300 EmptyVertex f1 = new EmptyVertex(0);
301 f1.addAP(APCO0);
302 f1.addAP(APCP0);
303 f1.addAP(APCP1);
304
305 EmptyVertex f2 = new EmptyVertex(0);
306 f2.addAP(APCP0);
307 f2.addAP(APCQ0);
308 f2.addAP(APCQ1);
309
310 EmptyVertex f3 = new EmptyVertex(0);
311 f3.addAP(APCQ0);
312 f3.addAP(APCQ1);
313
314 EmptyVertex f4 = new EmptyVertex(0);
315 f4.addAP(APCQ1);
316
317 // Build a simple graph
318 EmptyVertex v0 = new EmptyVertex(0);
319 v0.addAP(APCO0);
320 v0.addAP(APCP0);
321
322 EmptyVertex v1 = new EmptyVertex(1);
323 v1.addAP(APCO1);
324
325 EmptyVertex v2 = new EmptyVertex(2);
326 v2.addAP(APCP1);
327
328 DGraph gA = new DGraph();
329 gA.addVertex(v0);
330 gA.appendVertexOnAP(v0.getAP(0), v1.getAP(0));
331 gA.appendVertexOnAP(v0.getAP(1), v2.getAP(0));
332
333
334 /*
335 * No APClass compatibility: all is compatible with all!
336 */
337 HashMap<APClass,APClass> capMap = new HashMap<APClass,APClass>();
338 HashSet<APClass> forbEnds = new HashSet<APClass>();
339 HashMap<APClass,ArrayList<APClass>> cpMap =
340 new HashMap<APClass,ArrayList<APClass>>();
341
342 FragmentSpaceParameters fsp = new FragmentSpaceParameters();
343 FragmentSpace fs = new FragmentSpace(fsp,
344 new ArrayList<Vertex>(),
345 new ArrayList<Vertex>(),
346 new ArrayList<Vertex>(),
347 cpMap, capMap, forbEnds, cpMap);
348
349 LinkedHashMap<AttachmentPoint,List<AttachmentPoint>> apCompatilities =
350 APMapFinder.findMappingCompatibileAPs(
351 v0.getAttachmentPoints(),
352 f0.getAttachmentPoints(), false, fs);
353
354 assertEquals(2, apCompatilities.size()); // must be equal to #APs
355 assertEquals(3, apCompatilities.get(v0.getAP(0)).size());
356 assertEquals(3, apCompatilities.get(v0.getAP(1)).size());
357
358 apCompatilities = APMapFinder.findMappingCompatibileAPs(
359 f0.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
360
361 assertEquals(3, apCompatilities.size());
362 assertEquals(3, apCompatilities.get(f0.getAP(0)).size());
363 assertEquals(3, apCompatilities.get(f0.getAP(1)).size());
364 assertEquals(3, apCompatilities.get(f0.getAP(2)).size());
365
366 apCompatilities = APMapFinder.findMappingCompatibileAPs(
367 f0.getAttachmentPoints(), f2.getAttachmentPoints(), false, fs);
368
369 assertEquals(3, apCompatilities.size());
370 assertEquals(3, apCompatilities.get(f0.getAP(0)).size());
371 assertEquals(3, apCompatilities.get(f0.getAP(1)).size());
372 assertEquals(3, apCompatilities.get(f0.getAP(2)).size());
373
374 apCompatilities = APMapFinder.findMappingCompatibileAPs(
375 f2.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
376
377 assertEquals(3, apCompatilities.size());
378 assertEquals(3, apCompatilities.get(f2.getAP(0)).size());
379 assertEquals(3, apCompatilities.get(f2.getAP(1)).size());
380 assertEquals(3, apCompatilities.get(f2.getAP(2)).size());
381
382 apCompatilities = APMapFinder.findMappingCompatibileAPs(
383 v2.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
384
385 assertEquals(1, apCompatilities.size());
386 assertEquals(3, apCompatilities.get(v2.getAP(0)).size());
387
388 apCompatilities = APMapFinder.findMappingCompatibileAPs(
389 f0.getAttachmentPoints(), f1.getAttachmentPoints(), false, fs);
390
391 assertEquals(3, apCompatilities.size()); // must be equal to #APs
392 assertEquals(3, apCompatilities.get(f0.getAP(0)).size());
393 assertEquals(3, apCompatilities.get(f0.getAP(1)).size());
394 assertEquals(3, apCompatilities.get(f0.getAP(2)).size());
395
396 apCompatilities = APMapFinder.findMappingCompatibileAPs(
397 f0.getAttachmentPoints(), f3.getAttachmentPoints(), false, fs);
398
399 assertEquals(3, apCompatilities.size()); // must be equal to #APs
400 assertEquals(2, apCompatilities.get(f0.getAP(0)).size());
401 assertEquals(2, apCompatilities.get(f0.getAP(1)).size());
402 assertEquals(2, apCompatilities.get(f0.getAP(2)).size());
403
404 /*
405 * Compatibility matrix is empty: AP mapping is guided only by APClasses
406 * being equal.
407 */
408
409 fs.setAPclassBasedApproach(true);
410
411 apCompatilities = APMapFinder.findMappingCompatibileAPs(
412 v0.getAttachmentPoints(),
413 f0.getAttachmentPoints(), false, fs);
414
415 assertEquals(2, apCompatilities.size());
416 // the sole AP with same APClass
417 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
418 // the sole AP with same APClass
419 assertEquals(1, apCompatilities.get(v0.getAP(1)).size());
420
421 apCompatilities = APMapFinder.findMappingCompatibileAPs(
422 f0.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
423
424 assertEquals(3, apCompatilities.size());
425 assertEquals(1, apCompatilities.get(f0.getAP(0)).size());
426 assertEquals(1, apCompatilities.get(f0.getAP(1)).size());
427 assertEquals(1, apCompatilities.get(f0.getAP(2)).size());
428
429 apCompatilities = APMapFinder.findMappingCompatibileAPs(
430 f0.getAttachmentPoints(), f0.getAttachmentPoints(), true, fs);
431
432 assertEquals(3, apCompatilities.size());
433 assertEquals(3, apCompatilities.get(f0.getAP(0)).size());
434 assertEquals(3, apCompatilities.get(f0.getAP(1)).size());
435 assertEquals(3, apCompatilities.get(f0.getAP(2)).size());
436
437 apCompatilities = APMapFinder.findMappingCompatibileAPs(
438 f0.getAttachmentPoints(), f2.getAttachmentPoints(), false, fs);
439
440 assertEquals(1, apCompatilities.size()); //only the one with same APClass
441
442 apCompatilities = APMapFinder.findMappingCompatibileAPs(
443 f2.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
444
445 assertEquals(1, apCompatilities.size());
446
447 apCompatilities = APMapFinder.findMappingCompatibileAPs(
448 f0.getAttachmentPoints(), f2.getAttachmentPoints(), true, fs);
449
450 assertEquals(3, apCompatilities.size());
451 assertEquals(3, apCompatilities.get(f0.getAP(0)).size());
452 assertEquals(3, apCompatilities.get(f0.getAP(1)).size());
453 assertEquals(3, apCompatilities.get(f0.getAP(2)).size());
454
455 apCompatilities = APMapFinder.findMappingCompatibileAPs(
456 f0.getAttachmentPoints(), f1.getAttachmentPoints(), false, fs);
457
458 assertEquals(3, apCompatilities.size());
459 assertEquals(1, apCompatilities.get(f0.getAP(0)).size());
460 assertEquals(1, apCompatilities.get(f0.getAP(1)).size());
461 assertEquals(1, apCompatilities.get(f0.getAP(2)).size());
462
463 apCompatilities = APMapFinder.findMappingCompatibileAPs(
464 v0.getAttachmentPoints(),
465 f0.getAttachmentPoints(), false, fs);
466
467 assertEquals(2, apCompatilities.size());
468 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
469 assertEquals(f0.getAP(0), apCompatilities.get(v0.getAP(0)).get(0));
470 assertEquals(1, apCompatilities.get(v0.getAP(1)).size());
471 assertEquals(f0.getAP(1), apCompatilities.get(v0.getAP(1)).get(0));
472
473 apCompatilities = APMapFinder.findMappingCompatibileAPs(
474 v2.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
475
476 assertEquals(1, apCompatilities.size());
477 assertEquals(1, apCompatilities.get(v2.getAP(0)).size());
478
479 apCompatilities = APMapFinder.findMappingCompatibileAPs(
480 f0.getAttachmentPoints(), f3.getAttachmentPoints(), false, fs);
481
482 assertEquals(0, apCompatilities.size());
483
484 /*
485 * Filling APClass compatibility (to some extent)
486 */
487 cpMap = new HashMap<APClass,ArrayList<APClass>>();
488 ArrayList<APClass> lstO = new ArrayList<APClass>();
489 lstO.add(APCO1);
490 cpMap.put(APCO0, lstO);
491 ArrayList<APClass> lstP = new ArrayList<APClass>();
492 lstP.add(APCO1);
493 cpMap.put(APCP0, lstP);
494
495 /* Compatibility matrix
496 *
497 * | O0 | O1 | P0 | P1 | Q0 | Q1 |
498 * -----------------------------------
499 * O0 | | T | | | | |
500 * -----------------------------------
501 * O1 | | | | | | |
502 * -----------------------------------
503 * P0 | | T | | | | |
504 * -----------------------------------
505 * P1 | | | | | | |
506 * -----------------------------------
507 * Q0 | | | | | | |
508 * -----------------------------------
509 * Q1 | | | | | | |
510 */
511
512 fsp = new FragmentSpaceParameters();
513 fs = new FragmentSpace(fsp,
514 new ArrayList<Vertex>(),
515 new ArrayList<Vertex>(),
516 new ArrayList<Vertex>(),
517 cpMap, capMap, forbEnds, cpMap);
518
519 apCompatilities = APMapFinder.findMappingCompatibileAPs(
520 v0.getAttachmentPoints(),
521 f0.getAttachmentPoints(), false, fs);
522
523 assertEquals(2, apCompatilities.size());
524 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
525 assertEquals(f0.getAP(0), apCompatilities.get(v0.getAP(0)).get(0));
526 assertEquals(1, apCompatilities.get(v0.getAP(1)).size());
527 assertEquals(f0.getAP(1), apCompatilities.get(v0.getAP(1)).get(0));
528
529 apCompatilities = APMapFinder.findMappingCompatibileAPs(
530 f0.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
531
532 assertEquals(3, apCompatilities.size());
533 assertEquals(1, apCompatilities.get(f0.getAP(0)).size());
534 assertEquals(1, apCompatilities.get(f0.getAP(1)).size());
535 assertEquals(1, apCompatilities.get(f0.getAP(2)).size());
536
537 apCompatilities = APMapFinder.findMappingCompatibileAPs(
538 v2.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
539
540 assertEquals(1, apCompatilities.size());
541 assertEquals(1, apCompatilities.get(v2.getAP(0)).size());
542
543 apCompatilities = APMapFinder.findMappingCompatibileAPs(
544 f0.getAttachmentPoints(), f1.getAttachmentPoints(), false, fs);
545
546 assertEquals(3, apCompatilities.size());
547 assertEquals(1, apCompatilities.get(f0.getAP(0)).size());
548 assertEquals(1, apCompatilities.get(f0.getAP(1)).size());
549 assertEquals(1, apCompatilities.get(f0.getAP(2)).size());
550
551 apCompatilities = APMapFinder.findMappingCompatibileAPs(
552 f0.getAttachmentPoints(), f3.getAttachmentPoints(), false, fs);
553
554 assertEquals(0, apCompatilities.size());
555
556 /*
557 * Filling APClass compatibility (to some larger extent)
558 */
559 cpMap = new HashMap<APClass,ArrayList<APClass>>();
560 lstO = new ArrayList<APClass>();
561 lstO.add(APCO1);
562 lstO.add(APCP1);
563 cpMap.put(APCO0, lstO);
564 lstP = new ArrayList<APClass>();
565 lstP.add(APCO1);
566 lstP.add(APCP1);
567 cpMap.put(APCP0, lstP);
568 ArrayList<APClass> lstQ = new ArrayList<APClass>();
569 lstQ.add(APCO1);
570 lstQ.add(APCP1);
571 cpMap.put(APCQ0, lstQ);
572
573 /* Compatibility matrix
574 *
575 * | O0 | O1 | P0 | P1 | Q0 | Q1 |
576 * -----------------------------------
577 * O0 | | T | | T | | |
578 * -----------------------------------
579 * O1 | | | | | | |
580 * -----------------------------------
581 * P0 | | T | | T | | |
582 * -----------------------------------
583 * P1 | | | | | | |
584 * -----------------------------------
585 * Q0 | | T | | T | | |
586 * -----------------------------------
587 * Q1 | | | | | | |
588 */
589
590 fsp = new FragmentSpaceParameters();
591 fs = new FragmentSpace(fsp,
592 new ArrayList<Vertex>(),
593 new ArrayList<Vertex>(),
594 new ArrayList<Vertex>(),
595 cpMap, capMap, forbEnds, cpMap);
596
597 apCompatilities = APMapFinder.findMappingCompatibileAPs(
598 v0.getAttachmentPoints(),
599 f0.getAttachmentPoints(), false, fs);
600
601 assertEquals(2, apCompatilities.size());
602 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
603 assertEquals(f0.getAP(0), apCompatilities.get(v0.getAP(0)).get(0));
604 assertEquals(1, apCompatilities.get(v0.getAP(1)).size());
605 assertEquals(f0.getAP(1), apCompatilities.get(v0.getAP(1)).get(0));
606
607 apCompatilities = APMapFinder.findMappingCompatibileAPs(
608 f0.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
609
610 assertEquals(3, apCompatilities.size());
611 assertEquals(1, apCompatilities.get(f0.getAP(0)).size());
612 assertEquals(1, apCompatilities.get(f0.getAP(1)).size());
613 assertEquals(1, apCompatilities.get(f0.getAP(2)).size());
614
615 apCompatilities = APMapFinder.findMappingCompatibileAPs(
616 v2.getAttachmentPoints(), f0.getAttachmentPoints(), false, fs);
617
618 assertEquals(1, apCompatilities.size());
619 assertEquals(1, apCompatilities.get(v2.getAP(0)).size());
620
621 apCompatilities = APMapFinder.findMappingCompatibileAPs(
622 f0.getAttachmentPoints(), f1.getAttachmentPoints(), false, fs);
623
624 assertEquals(3, apCompatilities.size());
625 assertEquals(1, apCompatilities.get(f0.getAP(0)).size());
626 assertEquals(1, apCompatilities.get(f0.getAP(1)).size());
627 assertEquals(1, apCompatilities.get(f0.getAP(2)).size());
628
629 apCompatilities = APMapFinder.findMappingCompatibileAPs(
630 f0.getAttachmentPoints(), f3.getAttachmentPoints(), false, fs);
631
632 assertEquals(0, apCompatilities.size());
633
634
635 /*
636 * Forom here I build exactly the system that I want to test, because
637 * this way it is easier to see what the expected result should be.
638 */
639
640 gA = new DGraph();
641
642 v0 = new EmptyVertex(0);
643 v0.addAP(APCO0);
644
645 v1 = new EmptyVertex(1);
646 v1.addAP(APCO1);
647
648 gA.addVertex(v0);
649 gA.appendVertexOnAP(v0.getAP(0), v1.getAP(0));
650
651 DGraph gB = new DGraph();
652
653 v2 = new EmptyVertex(2);
654 v2.addAP(APCP0);
655
656 EmptyVertex v3 = new EmptyVertex(3);
657 v3.addAP(APCP1);
658
659 gB.addVertex(v2);
660 gB.appendVertexOnAP(v2.getAP(0), v3.getAP(0));
661
662 cpMap = new HashMap<APClass,ArrayList<APClass>>();
663 lstO = new ArrayList<APClass>();
664 lstO.add(APCO1);
665 cpMap.put(APCO0, lstO);
666 lstP = new ArrayList<APClass>();
667 lstP.add(APCP1);
668 cpMap.put(APCP0, lstP);
669
670 /* Compatibility matrix
671 *
672 * | O0 | O1 | P0 | P1 | Q0 | Q1 |
673 * -----------------------------------
674 * O0 | | T | | | | |
675 * -----------------------------------
676 * O1 | | | | | | |
677 * -----------------------------------
678 * P0 | | | | T | | |
679 * -----------------------------------
680 * P1 | | | | | | |
681 * -----------------------------------
682 * Q0 | | | | | | |
683 * -----------------------------------
684 * Q1 | | | | | | |
685 */
686
687 fsp = new FragmentSpaceParameters();
688 fs = new FragmentSpace(fsp,
689 new ArrayList<Vertex>(),
690 new ArrayList<Vertex>(),
691 new ArrayList<Vertex>(),
692 cpMap,
693 new HashMap<APClass,APClass>(),
694 new HashSet<APClass>(),
695 new HashMap<APClass,ArrayList<APClass>>());
696
697 // Both fragment have only one AP and has SRC role,
698 // but CPMap says incompatible
699 apCompatilities = APMapFinder.findMappingCompatibileAPs(
700 v0.getAttachmentPoints(),
701 v2.getAttachmentPoints(), false, fs);
702 assertEquals(0, apCompatilities.size());
703
704 // SRC and TRG roles,
705 // but CPMap says incompatible
706 apCompatilities = APMapFinder.findMappingCompatibileAPs(
707 v0.getAttachmentPoints(),
708 v3.getAttachmentPoints(), false, fs);
709 assertEquals(0, apCompatilities.size());
710
711 // TRG and SRC roles,
712 // but CPMap says incompatible
713 apCompatilities = APMapFinder.findMappingCompatibileAPs(
714 v1.getAttachmentPoints(),
715 v2.getAttachmentPoints(), false, fs);
716 assertEquals(0, apCompatilities.size());
717
718 // Both fragment have only one AP and has TRG role,
719 // but CPMap says incompatible
720 apCompatilities = APMapFinder.findMappingCompatibileAPs(
721 v1.getAttachmentPoints(),
722 v3.getAttachmentPoints(), false, fs);
723 assertEquals(0, apCompatilities.size());
724
725 // Add Compatibility, but incomplete)
726
727 cpMap = new HashMap<APClass,ArrayList<APClass>>();
728 lstO = new ArrayList<APClass>();
729 lstO.add(APCO1);
730 cpMap.put(APCO0, lstO);
731 lstP = new ArrayList<APClass>();
732 lstP.add(APCO1);
733 lstP.add(APCP1);
734 cpMap.put(APCP0, lstP);
735
736 /* Compatibility matrix
737 *
738 * | O0 | O1 | P0 | P1 | Q0 | Q1 |
739 * -----------------------------------
740 * O0 | | T | | | | |
741 * -----------------------------------
742 * O1 | | | | | | |
743 * -----------------------------------
744 * P0 | | T | | T | | |
745 * -----------------------------------
746 * P1 | | | | | | |
747 * -----------------------------------
748 * Q0 | | | | | | |
749 * -----------------------------------
750 * Q1 | | | | | | |
751 */
752
753 fsp = new FragmentSpaceParameters();
754 fs = new FragmentSpace(fsp,
755 new ArrayList<Vertex>(),
756 new ArrayList<Vertex>(),
757 new ArrayList<Vertex>(),
758 cpMap,
759 new HashMap<APClass,APClass>(),
760 new HashSet<APClass>(),
761 new HashMap<APClass,ArrayList<APClass>>());
762
763 // Both fragment have only one AP and has SRC role,
764 // but CPMap says incompatible
765 apCompatilities = APMapFinder.findMappingCompatibileAPs(
766 v0.getAttachmentPoints(),
767 v2.getAttachmentPoints(), false, fs);
768 assertEquals(0, apCompatilities.size());
769
770 // SRC and TRG roles,
771 // but CPMap says incompatible
772 apCompatilities = APMapFinder.findMappingCompatibileAPs(
773 v0.getAttachmentPoints(),
774 v3.getAttachmentPoints(), false, fs);
775 assertEquals(0, apCompatilities.size());
776
777 // TRG and SRC roles,
778 // but CPMap says incompatible
779 apCompatilities = APMapFinder.findMappingCompatibileAPs(
780 v1.getAttachmentPoints(),
781 v2.getAttachmentPoints(), false, fs);
782 assertEquals(0, apCompatilities.size());
783
784 // Both fragment have only one AP and has TRG role,
785 // but CPMap says incompatible
786 apCompatilities = APMapFinder.findMappingCompatibileAPs(
787 v1.getAttachmentPoints(),
788 v3.getAttachmentPoints(), false, fs);
789 assertEquals(0, apCompatilities.size());
790
791
792 // Add Cross-compatibility
793
794 cpMap = new HashMap<APClass,ArrayList<APClass>>();
795 lstO = new ArrayList<APClass>();
796 lstO.add(APCO1);
797 lstO.add(APCP1);
798 cpMap.put(APCO0, lstO);
799 lstP = new ArrayList<APClass>();
800 lstP.add(APCO1);
801 lstP.add(APCP1);
802 cpMap.put(APCP0, lstP);
803
804 /* Compatibility matrix
805 *
806 * | O0 | O1 | P0 | P1 | Q0 | Q1 |
807 * -----------------------------------
808 * O0 | | T | | T | | |
809 * -----------------------------------
810 * O1 | | | | | | |
811 * -----------------------------------
812 * P0 | | T | | T | | |
813 * -----------------------------------
814 * P1 | | | | | | |
815 * -----------------------------------
816 * Q0 | | | | | | |
817 * -----------------------------------
818 * Q1 | | | | | | |
819 */
820
821 fsp = new FragmentSpaceParameters();
822 fs = new FragmentSpace(fsp,
823 new ArrayList<Vertex>(),
824 new ArrayList<Vertex>(),
825 new ArrayList<Vertex>(),
826 cpMap,
827 new HashMap<APClass,APClass>(),
828 new HashSet<APClass>(),
829 new HashMap<APClass,ArrayList<APClass>>());
830
831 // Both fragment have only one AP and has SRC role,
832 // and CPMap says they are compatible
833 apCompatilities = APMapFinder.findMappingCompatibileAPs(
834 v0.getAttachmentPoints(),
835 v2.getAttachmentPoints(), false, fs);
836 assertEquals(1, apCompatilities.size());
837 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
838 assertEquals(v2.getAP(0), apCompatilities.get(v0.getAP(0)).get(0));
839 apCompatilities = APMapFinder.findMappingCompatibileAPs(
840 v2.getAttachmentPoints(),
841 v0.getAttachmentPoints(), false, fs);
842 assertEquals(1, apCompatilities.size());
843 assertEquals(1, apCompatilities.get(v2.getAP(0)).size());
844 assertEquals(v0.getAP(0), apCompatilities.get(v2.getAP(0)).get(0));
845
846 // SRC and TRG roles,
847 // but CPMap says incompatible
848 apCompatilities = APMapFinder.findMappingCompatibileAPs(
849 v0.getAttachmentPoints(),
850 v3.getAttachmentPoints(), false, fs);
851 assertEquals(0, apCompatilities.size());
852
853 // TRG and SRC roles,
854 // but CPMap says incompatible
855 apCompatilities = APMapFinder.findMappingCompatibileAPs(
856 v1.getAttachmentPoints(),
857 v2.getAttachmentPoints(), false, fs);
858 assertEquals(0, apCompatilities.size());
859
860 // Both fragment have only one AP and has TRG role,
861 // and CPMap says they are compatible
862 apCompatilities = APMapFinder.findMappingCompatibileAPs(
863 v1.getAttachmentPoints(),
864 v3.getAttachmentPoints(), false, fs);
865 assertEquals(1, apCompatilities.size());
866 assertEquals(1, apCompatilities.get(v1.getAP(0)).size());
867 assertEquals(v3.getAP(0), apCompatilities.get(v1.getAP(0)).get(0));
868 apCompatilities = APMapFinder.findMappingCompatibileAPs(
869 v3.getAttachmentPoints(),
870 v1.getAttachmentPoints(), false, fs);
871 assertEquals(1, apCompatilities.size());
872 assertEquals(1, apCompatilities.get(v3.getAP(0)).size());
873 assertEquals(v1.getAP(0), apCompatilities.get(v3.getAP(0)).get(0));
874
875
876 // Add cross and backwards compatibility
877
878 cpMap = new HashMap<APClass,ArrayList<APClass>>();
879 ArrayList<APClass> lstO0 = new ArrayList<APClass>();
880 lstO0.add(APCO1);
881 lstO0.add(APCP1);
882 lstO0.add(APCP0);
883 lstO0.add(APCQ1);
884 cpMap.put(APCO0, lstO0);
885 ArrayList<APClass> lstP0 = new ArrayList<APClass>();
886 lstP0.add(APCO1);
887 lstP0.add(APCP1);
888 lstP0.add(APCO0);
889 cpMap.put(APCP0, lstP0);
890 ArrayList<APClass> lstO1 = new ArrayList<APClass>();
891 lstO1.add(APCO0);
892 lstO1.add(APCP0);
893 lstO1.add(APCP1);
894 cpMap.put(APCO1, lstO1);
895 ArrayList<APClass> lstP1 = new ArrayList<APClass>();
896 lstP1.add(APCO0);
897 lstP1.add(APCP0);
898 lstP1.add(APCO1);
899 cpMap.put(APCP1, lstP1);
900 ArrayList<APClass> lstQ1 = new ArrayList<APClass>();
901 lstQ1.add(APCO0);
902 lstQ1.add(APCO1);
903 lstQ1.add(APCP0);
904 lstQ1.add(APCP1);
905 cpMap.put(APCQ1, lstQ1);
906
907 /* Compatibility matrix
908 *
909 * | O0 | O1 | P0 | P1 | Q0 | Q1 |
910 * -----------------------------------
911 * O0 | | T | | T | | T |
912 * -----------------------------------
913 * O1 | T | | T | | | |
914 * -----------------------------------
915 * P0 | | T | | T | | |
916 * -----------------------------------
917 * P1 | T | | T | | | |
918 * -----------------------------------
919 * Q0 | | | | | | |
920 * -----------------------------------
921 * Q1 | T | T | T | T | | |
922 */
923
924 fsp = new FragmentSpaceParameters();
925 fs = new FragmentSpace(fsp,
926 new ArrayList<Vertex>(),
927 new ArrayList<Vertex>(),
928 new ArrayList<Vertex>(),
929 cpMap,
930 new HashMap<APClass,APClass>(),
931 new HashSet<APClass>(),
932 new HashMap<APClass,ArrayList<APClass>>());
933
934 // Both fragment have only one AP and has SRC role,
935 // and CPMap says they are compatible
936 apCompatilities = APMapFinder.findMappingCompatibileAPs(
937 v0.getAttachmentPoints(),
938 v2.getAttachmentPoints(), false, fs);
939 assertEquals(1, apCompatilities.size());
940 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
941 assertEquals(v2.getAP(0), apCompatilities.get(v0.getAP(0)).get(0));
942 apCompatilities = APMapFinder.findMappingCompatibileAPs(
943 v2.getAttachmentPoints(),
944 v0.getAttachmentPoints(), false, fs);
945 assertEquals(1, apCompatilities.size());
946 assertEquals(1, apCompatilities.get(v2.getAP(0)).size());
947 assertEquals(v0.getAP(0), apCompatilities.get(v2.getAP(0)).get(0));
948
949 // SRC and TRG roles,
950 // but CPMap says incompatible
951 apCompatilities = APMapFinder.findMappingCompatibileAPs(
952 v0.getAttachmentPoints(),
953 v3.getAttachmentPoints(), false, fs);
954 assertEquals(1, apCompatilities.size());
955 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
956 assertEquals(v3.getAP(0), apCompatilities.get(v0.getAP(0)).get(0));
957 apCompatilities = APMapFinder.findMappingCompatibileAPs(
958 v3.getAttachmentPoints(),
959 v0.getAttachmentPoints(), false, fs);
960 assertEquals(1, apCompatilities.size());
961 assertEquals(1, apCompatilities.get(v3.getAP(0)).size());
962 assertEquals(v0.getAP(0), apCompatilities.get(v3.getAP(0)).get(0));
963
964 // TRG and SRC roles,
965 // but CPMap says incompatible
966 apCompatilities = APMapFinder.findMappingCompatibileAPs(
967 v1.getAttachmentPoints(),
968 v2.getAttachmentPoints(), false, fs);
969 assertEquals(1, apCompatilities.size());
970 assertEquals(1, apCompatilities.get(v1.getAP(0)).size());
971 assertEquals(v2.getAP(0), apCompatilities.get(v1.getAP(0)).get(0));
972 apCompatilities = APMapFinder.findMappingCompatibileAPs(
973 v2.getAttachmentPoints(),
974 v1.getAttachmentPoints(), false, fs);
975 assertEquals(1, apCompatilities.size());
976 assertEquals(1, apCompatilities.get(v2.getAP(0)).size());
977 assertEquals(v1.getAP(0), apCompatilities.get(v2.getAP(0)).get(0));
978
979 // Both fragment have only one AP and has TRG role,
980 // and CPMap says they are compatible
981 apCompatilities = APMapFinder.findMappingCompatibileAPs(
982 v1.getAttachmentPoints(),
983 v3.getAttachmentPoints(), false, fs);
984 assertEquals(1, apCompatilities.size());
985 assertEquals(1, apCompatilities.get(v1.getAP(0)).size());
986 assertEquals(v3.getAP(0), apCompatilities.get(v1.getAP(0)).get(0));
987 apCompatilities = APMapFinder.findMappingCompatibileAPs(
988 v3.getAttachmentPoints(),
989 v1.getAttachmentPoints(), false, fs);
990 assertEquals(1, apCompatilities.size());
991 assertEquals(1, apCompatilities.get(v3.getAP(0)).size());
992 assertEquals(v1.getAP(0), apCompatilities.get(v3.getAP(0)).get(0));
993
994 // One is free other is SRC, and CPMap says compatible
995 apCompatilities = APMapFinder.findMappingCompatibileAPs(
996 f4.getAttachmentPoints(),
997 v0.getAttachmentPoints(), false, fs);
998 assertEquals(0, apCompatilities.size());
999 apCompatilities = APMapFinder.findMappingCompatibileAPs(
1000 f4.getAttachmentPoints(),
1001 v0.getAttachmentPoints(), true, fs);
1002 assertEquals(1, apCompatilities.size());
1003 assertEquals(1, apCompatilities.size());
1004 assertEquals(1, apCompatilities.get(f4.getAP(0)).size());
1005 assertEquals(v0.getAP(0), apCompatilities.get(f4.getAP(0)).get(0));
1006 apCompatilities = APMapFinder.findMappingCompatibileAPs(
1007 v0.getAttachmentPoints(),
1008 f4.getAttachmentPoints(), false, fs);
1009 assertEquals(0, apCompatilities.size());
1010 apCompatilities = APMapFinder.findMappingCompatibileAPs(
1011 v0.getAttachmentPoints(),
1012 f4.getAttachmentPoints(), true, fs);
1013 assertEquals(1, apCompatilities.size());
1014 assertEquals(1, apCompatilities.size());
1015 assertEquals(1, apCompatilities.get(v0.getAP(0)).size());
1016 assertEquals(f4.getAP(0), apCompatilities.get(v0.getAP(0)).get(0));
1017
1018 // One is free other is TRG, and CPMap says compatible
1019 apCompatilities = APMapFinder.findMappingCompatibileAPs(
1020 f4.getAttachmentPoints(),
1021 v1.getAttachmentPoints(), false, fs);
1022 assertEquals(0, apCompatilities.size());
1023 apCompatilities = APMapFinder.findMappingCompatibileAPs(
1024 f4.getAttachmentPoints(),
1025 v1.getAttachmentPoints(), true, fs);
1026 assertEquals(1, apCompatilities.size());
1027 assertEquals(1, apCompatilities.size());
1028 assertEquals(1, apCompatilities.get(f4.getAP(0)).size());
1029 assertEquals(v1.getAP(0), apCompatilities.get(f4.getAP(0)).get(0));
1030 apCompatilities = APMapFinder.findMappingCompatibileAPs(
1031 v1.getAttachmentPoints(),
1032 f4.getAttachmentPoints(), false, fs);
1033 assertEquals(0, apCompatilities.size());
1034 apCompatilities = APMapFinder.findMappingCompatibileAPs(
1035 v1.getAttachmentPoints(),
1036 f4.getAttachmentPoints(), true, fs);
1037 assertEquals(1, apCompatilities.size());
1038 assertEquals(1, apCompatilities.size());
1039 assertEquals(1, apCompatilities.get(v1.getAP(0)).size());
1040 assertEquals(f4.getAP(0), apCompatilities.get(v1.getAP(0)).get(0));
1041
1042 }
1043
1044//------------------------------------------------------------------------------
1045
1046}
denoptim.fragspace.APMapFinder
An utility class to encapsulate the search for an AttachmentPoint-AttachmentPoint mapping.
Definition: APMapFinder.java:42
denoptim.fragspace.APMapFinder.getChosenAPMapping
APMapping getChosenAPMapping()
Returns the AttachmentPoint-AttachmentPoint mapping chosen among the possible mappings.
Definition: APMapFinder.java:557
denoptim.fragspace.APMapFinder.findMappingCompatibileAPs
static LinkedHashMap< AttachmentPoint, List< AttachmentPoint > > findMappingCompatibileAPs(List< AttachmentPoint > lstA, List< AttachmentPoint > lstB, boolean compatibleIfFree, FragmentSpace fragSpace)
Compares the AttachmentPoint of two lists searching for all the APs of the second list that are "comp...
Definition: APMapFinder.java:404
denoptim.fragspace.APMapFinder.foundMapping
boolean foundMapping()
Returns true if any mapping has been found.
Definition: APMapFinder.java:542
denoptim.fragspace.APMapFinder.getAllAPMappings
List< APMapping > getAllAPMappings()
Returns all AttachmentPoint-AttachmentPoint mapping found.
Definition: APMapFinder.java:572
denoptim.fragspace.FragmentSpace
Class defining a space of building blocks.
Definition: FragmentSpace.java:67
denoptim.fragspace.FragmentSpace.setAPclassBasedApproach
void setAPclassBasedApproach(boolean useAPC)
Set the fragment space to behave according to APClass-based approach.
Definition: FragmentSpace.java:466
denoptim.fragspace.FragmentSpaceParameters
Parameters defining the fragment space.
Definition: FragmentSpaceParameters.java:39
denoptim.graph.APClass.make
static APClass make(String ruleAndSubclass)
Creates an APClass if it does not exist already, or returns the reference to the existing instance.
Definition: APClass.java:136
denoptim.graph.APMapping
Class representing a mapping between attachment points (APs).
Definition: APMapping.java:42
denoptim.graph.DGraph
Container for the list of vertices and the edges that connect them.
Definition: DGraph.java:102
denoptim.graph.DGraph.addVertex
void addVertex(Vertex vertex)
Appends a vertex to this graph without creating any edge.
Definition: DGraph.java:1097
denoptim.graph.DGraph.appendVertexOnAP
void appendVertexOnAP(AttachmentPoint srcAP, AttachmentPoint trgAP)
Append a vertex to this graph: adds the new vertex to the list of vertices belonging to the graph,...
Definition: DGraph.java:5776
denoptim.graph.DGraph.addEdge
void addEdge(Edge edge)
Adds the edge to the list of edges belonging to this graph.
Definition: DGraph.java:1021
denoptim.graph.Edge
This class represents the edge between two vertices.
Definition: Edge.java:38
denoptim.graph.EmptyVertex
An empty vertex has the behaviors of a vertex, but has no molecular structure.
Definition: EmptyVertex.java:45
denoptim.graph.EmptyVertex.getAttachmentPoints
List< AttachmentPoint > getAttachmentPoints()
Definition: EmptyVertex.java:124
denoptim.graph.EmptyVertex.addAP
void addAP()
Adds an attachment point with no APClass or other attribute.
Definition: EmptyVertex.java:298
denoptim.graph.Vertex.setBuildingBlockType
void setBuildingBlockType(Vertex.BBType buildingBlockType)
Definition: Vertex.java:305
denoptim.graph.Vertex.getAP
AttachmentPoint getAP(int i)
Get attachment point i on this vertex.
Definition: Vertex.java:920
denoptim.graph.Vertex.BBType
The type of building block.
Definition: Vertex.java:86