$darkmode
DENOPTIM
GraphLinkFinderTest.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.Arrays;
26import java.util.HashMap;
27import java.util.HashSet;
28import java.util.LinkedHashMap;
29import java.util.List;
30import java.util.Map;
31import java.util.Map.Entry;
32import java.util.Set;
33
34import org.junit.jupiter.api.Test;
35
36import denoptim.exception.DENOPTIMException;
37import denoptim.graph.APClass;
38import denoptim.graph.APMapping;
39import denoptim.graph.AttachmentPoint;
40import denoptim.graph.DGraph;
41import denoptim.graph.Edge;
42import denoptim.graph.EmptyVertex;
43import denoptim.graph.Vertex;
44import denoptim.graph.Vertex.BBType;
45
52public class GraphLinkFinderTest
53{
54 private static APClass APCA, APCB, APCC, APCD, APCE, APCF;
55
56//------------------------------------------------------------------------------
57
58 private FragmentSpace prepare() throws DENOPTIMException
59 {
60 APCA = APClass.make("A", 0);
61 APCB = APClass.make("B", 0);
62 APCC = APClass.make("C", 0);
63 APCD = APClass.make("D", 99);
64 APCE = APClass.make("E", 13);
65 APCF = APClass.make("F", 17);
66
67 HashMap<APClass,ArrayList<APClass>> cpMap =
68 new HashMap<APClass,ArrayList<APClass>>();
69 ArrayList<APClass> lstA = new ArrayList<APClass>();
70 lstA.add(APCA);
71 cpMap.put(APCA, lstA);
72 ArrayList<APClass> lstB = new ArrayList<APClass>();
73 lstB.add(APCB);
74 lstB.add(APCC);
75 cpMap.put(APCB, lstB);
76 ArrayList<APClass> lstC = new ArrayList<APClass>();
77 lstC.add(APCB);
78 lstC.add(APCC);
79 cpMap.put(APCC, lstC);
80 ArrayList<APClass> lstD = new ArrayList<APClass>();
81 lstD.add(APCD);
82 cpMap.put(APCD, lstD);
83 ArrayList<APClass> lstE = new ArrayList<APClass>();
84 lstE.add(APCE);
85 cpMap.put(APCE, lstE);
86
87
88 /* Compatibility matrix
89 *
90 * | A | B | C | D | E | F
91 * ---------------------------------
92 * A | T | | | | |
93 * ---------------------------------
94 * B | | T | T | | |
95 * ---------------------------------
96 * C | | T | T | | |
97 * ---------------------------------
98 * D | | | | T | |
99 * ---------------------------------
100 * E | | | | | T |
101 * ---------------------------------
102 * F | | | | | |
103 *
104 * NB: F has NONE!
105 */
106
107 HashMap<APClass,APClass> capMap = new HashMap<APClass,APClass>();
108 HashSet<APClass> forbEnds = new HashSet<APClass>();
109
110 FragmentSpaceParameters fsp = new FragmentSpaceParameters();
111 FragmentSpace fs = new FragmentSpace(fsp,
112 new ArrayList<Vertex>(),
113 new ArrayList<Vertex>(),
114 new ArrayList<Vertex>(),
115 cpMap, capMap, forbEnds, cpMap);
116 fs.setAPclassBasedApproach(true);
117
118 EmptyVertex s = new EmptyVertex();
119 s.setBuildingBlockType(BBType.SCAFFOLD);
120 s.addAP(APCA);
121 fs.appendVertexToLibrary(s, BBType.SCAFFOLD, fs.getScaffoldLibrary());
122
123 EmptyVertex v0 = new EmptyVertex();
124 v0.setBuildingBlockType(BBType.FRAGMENT);
125 v0.addAP(APCA);
126 v0.addAP(APCB);
127 v0.addAP(APCB);
128 fs.appendVertexToLibrary(v0, BBType.FRAGMENT, fs.getFragmentLibrary());
129
130 EmptyVertex v1 = new EmptyVertex();
131 v1.setBuildingBlockType(BBType.FRAGMENT);
132 v1.addAP(APCB);
133 fs.appendVertexToLibrary(v1, BBType.FRAGMENT, fs.getFragmentLibrary());
134
135 EmptyVertex v2 = new EmptyVertex();
136 v2.setBuildingBlockType(BBType.FRAGMENT);
137 v2.addAP(APCA);
138 v2.addAP(APCA);
139 fs.appendVertexToLibrary(v2, BBType.FRAGMENT,fs.getFragmentLibrary());
140
141 EmptyVertex v3 = new EmptyVertex();
142 v3.setBuildingBlockType(BBType.FRAGMENT);
143 v3.addAP(APCB);
144 v3.addAP(APCB);
145 fs.appendVertexToLibrary(v3, BBType.FRAGMENT, fs.getFragmentLibrary());
146
147 EmptyVertex v4 = new EmptyVertex();
148 v4.setBuildingBlockType(BBType.FRAGMENT);
149 v4.addAP(APCA);
150 v4.addAP(APCB);
151 v4.addAP(APCB);
152 fs.appendVertexToLibrary(v4, BBType.FRAGMENT, fs.getFragmentLibrary());
153
154 EmptyVertex v5 = new EmptyVertex();
155 v5.setBuildingBlockType(BBType.FRAGMENT);
156 v5.addAP(APCA);
157 v5.addAP(APCC);
158 v5.addAP(APCB);
159 fs.appendVertexToLibrary(v5, BBType.FRAGMENT, fs.getFragmentLibrary());
160
161 EmptyVertex v6 = new EmptyVertex();
162 v6.setBuildingBlockType(BBType.FRAGMENT);
163 v6.addAP(APCD);
164 v6.addAP(APCD);
165 fs.appendVertexToLibrary(v6, BBType.FRAGMENT, fs.getFragmentLibrary());
166
167 EmptyVertex v7 = new EmptyVertex();
168 v7.setBuildingBlockType(BBType.FRAGMENT);
169 v7.addAP(APCA);
170 fs.appendVertexToLibrary(v7, BBType.FRAGMENT, fs.getFragmentLibrary());
171
172 EmptyVertex v8 = new EmptyVertex();
173 v8.setBuildingBlockType(BBType.FRAGMENT);
174 v8.addAP(APCB);
175 fs.appendVertexToLibrary(v8, BBType.FRAGMENT, fs.getFragmentLibrary());
176
177 EmptyVertex v9 = new EmptyVertex();
178 v9.setBuildingBlockType(BBType.FRAGMENT);
179 v9.addAP(APCA);
180 v9.addAP(APCA);
181 v9.addAP(APCB);
182 v9.addAP(APCB);
183 fs.appendVertexToLibrary(v9, BBType.FRAGMENT, fs.getFragmentLibrary());
184
185 EmptyVertex v10 = new EmptyVertex();
186 v10.setBuildingBlockType(BBType.FRAGMENT);
187 v10.addAP(APCA);
188 v10.addAP(APCC);
189 v10.addAP(APCD);
190 v10.addAP(APCB);
191 fs.appendVertexToLibrary(v10, BBType.FRAGMENT, fs.getFragmentLibrary());
192
193 EmptyVertex v11 = new EmptyVertex();
194 v11.setBuildingBlockType(BBType.FRAGMENT);
195 v11.addAP(APCA);
196 v11.addAP(APCD);
197 v11.addAP(APCA);
198 v11.addAP(APCA);
199 v11.addAP(APCC);
200 v11.addAP(APCB);
201 v11.addAP(APCB);
202 v11.addAP(APCB);
203 fs.appendVertexToLibrary(v11, BBType.FRAGMENT, fs.getFragmentLibrary());
204
205 EmptyVertex v12 = new EmptyVertex();
206 v12.setBuildingBlockType(BBType.FRAGMENT);
207 v12.addAP(APCE);
208 v12.addAP(APCE);
209 v12.addAP(APCE);
210 fs.appendVertexToLibrary(v12, BBType.FRAGMENT, fs.getFragmentLibrary());
211
212 EmptyVertex v13 = new EmptyVertex();
213 v13.setBuildingBlockType(BBType.FRAGMENT);
214 v13.addAP(APCF);
215 v13.addAP(APCB);
216 v13.addAP(APCA);
217 fs.appendVertexToLibrary(v13, BBType.FRAGMENT, fs.getFragmentLibrary());
218 fs.groupAndClassifyFragments(true);
219
220 return fs;
221 }
222
223//------------------------------------------------------------------------------
224
230 private DGraph makeTestGraphA() throws DENOPTIMException
231 {
232 FragmentSpace fs = prepare();
233 DGraph graph = new DGraph();
234 Vertex s = fs.getVertexFromLibrary(BBType.SCAFFOLD,0);
235 graph.addVertex(s);
236 Vertex v0 = fs.getVertexFromLibrary(BBType.FRAGMENT,0);
237 graph.addVertex(v0);
238 Vertex v1 = fs.getVertexFromLibrary(BBType.FRAGMENT,1);
239 graph.addVertex(v1);
240 graph.addEdge(new Edge(s.getAP(0), v0.getAP(0)));
241 graph.addEdge(new Edge(v0.getAP(1), v1.getAP(0)));
242 graph.renumberGraphVertices();
243 return graph;
244 }
245
246//------------------------------------------------------------------------------
247
253 private DGraph makeTestGraphE() throws DENOPTIMException
254 {
255 FragmentSpace fs = prepare();
256 DGraph graph = new DGraph();
257 Vertex v0 = fs.getVertexFromLibrary(BBType.FRAGMENT,12);
258 graph.addVertex(v0);
259 Vertex v1 = fs.getVertexFromLibrary(BBType.FRAGMENT,12);
260 graph.addVertex(v1);
261 graph.addEdge(new Edge(v0.getAP(1), v1.getAP(1)));
262 graph.renumberGraphVertices();
263 return graph;
264 }
265
266//------------------------------------------------------------------------------
267
273 private DGraph makeTestGraphF() throws DENOPTIMException
274 {
275 FragmentSpace fs = prepare();
276 DGraph graph = new DGraph();
277 Vertex v0 = fs.getVertexFromLibrary(BBType.FRAGMENT,13);
278 graph.addVertex(v0);
279 Vertex v1 = fs.getVertexFromLibrary(BBType.FRAGMENT,13);
280 graph.addVertex(v1);
281 graph.addEdge(new Edge(v0.getAP(0), v1.getAP(0)));
282 graph.renumberGraphVertices();
283 return graph;
284 }
285
286//------------------------------------------------------------------------------
287
288 @Test
289 public void testLinkFromVertex() throws Exception
290 {
291 FragmentSpace fs = prepare();
292 DGraph graph = makeTestGraphA();
293 GraphLinkFinder glf = new GraphLinkFinder(fs,
294 graph.getVertexAtPosition(1), -1, true);
295 // NB: the boolean makes the search complete (within the limits that
296 // prevent combinatorial explosion)
297 // NB: "-1" is for "no selection of specific new building block".
298
299 // These are the expected numbers of AP mappings found for the three
300 // vertexes that can be alternative links.
301 Map<Integer,Integer> expected = new HashMap<Integer,Integer>();
302 expected.put(4, 4);
303 expected.put(5, 4);
304 expected.put(9, 12);
305 expected.put(10, 6);
306 expected.put(11, 84);
307 expected.put(13, 2);
308
309 LinkedHashMap<Vertex, List<APMapping>> allAltLinks =
310 glf.getAllAlternativesFound();
311 Set<Vertex> keys = allAltLinks.keySet();
312 for (Vertex k : keys)
313 {
314 int bbId = k.getBuildingBlockId();
315 assertTrue(expected.containsKey(bbId), "Vertex with building block "
316 + "ID '" + bbId + "' should not be among the results.");
317 assertEquals(expected.get(bbId), allAltLinks.get(k).size(),
318 "Number of APmapping is wrong for bbId '" + bbId + "'.");
319 }
320 }
321
322//------------------------------------------------------------------------------
323
324 @Test
325 public void testLinkFromEdge() throws Exception
326 {
327 FragmentSpace fs = prepare();
328 DGraph graph = makeTestGraphA();
329 Edge targetEdge = graph.getEdgeAtPosition(1);
330 GraphLinkFinder glf = new GraphLinkFinder(fs, targetEdge, -1, true);
331 // NB: the boolean makes the search complete (within the limits the
332 // prevent combinatorial explosion)
333 // NB: "-1" is for "no selection of specific new building block".
334
335 // Expected results in terms of <bbId:list of classes>
336 Map<Integer,List<APClass>> expected =
337 new HashMap<Integer,List<APClass>>();
338 expected.put(0, new ArrayList<APClass>(Arrays.asList(
339 APCB,APCB,APCB,APCB,APCB,APCB,APCB,APCB)));
340 expected.put(3, new ArrayList<APClass>(Arrays.asList(
341 APCB,APCB,APCB,APCB,APCB,APCB,APCB,APCB)));
342 expected.put(4, new ArrayList<APClass>(Arrays.asList(
343 APCB,APCB,APCB,APCB,APCB,APCB,APCB,APCB)));
344 expected.put(5, new ArrayList<APClass>(Arrays.asList(
345 APCB,APCC,APCB,APCB,APCB,APCB,APCB,APCC)));
346 expected.put(9, new ArrayList<APClass>(Arrays.asList(
347 APCB,APCB,APCB,APCB,APCB,APCB,APCB,APCB)));
348 expected.put(10, new ArrayList<APClass>(Arrays.asList(
349 APCB,APCC,APCB,APCB,APCB,APCB,APCB,APCC)));
350 expected.put(11, new ArrayList<APClass>(Arrays.asList(
351 APCB,APCC,APCB,APCB,
352 APCB,APCC,APCB,APCB,
353 APCB,APCC,APCB,APCB,
354 APCB,APCB,APCB,APCC,
355 APCB,APCB,APCB,APCB,
356 APCB,APCB,APCB,APCB,
357 APCB,APCB,APCB,APCC,
358 APCB,APCB,APCB,APCB,
359 APCB,APCB,APCB,APCB,
360 APCB,APCB,APCB,APCC,
361 APCB,APCB,APCB,APCB,
362 APCB,APCB,APCB,APCB)));
363
364 ensureConsistencyWithExpectations(expected,
365 glf.getAllAlternativesFound());
366 }
367
368//------------------------------------------------------------------------------
369
370 @Test
371 public void testLinkFromEdgeOneMatch() throws Exception
372 {
373 FragmentSpace fs = prepare();
374 DGraph graph = makeTestGraphE();
375 Edge targetEdge = graph.getEdgeAtPosition(0);
376 GraphLinkFinder glf = new GraphLinkFinder(fs, targetEdge, -1, true);
377 // NB: the boolean makes the search complete (within the limits the
378 // prevent combinatorial explosion)
379 // NB: "-1" is for "no selection of specific new building block".
380
381 // Expected results in terms of <bbId:list of classes>
382 Map<Integer,List<APClass>> expected =
383 new HashMap<Integer,List<APClass>>();
384 expected.put(12, new ArrayList<APClass>(Arrays.asList(
385 APCE,APCE,APCE,APCE,APCE,APCE,APCE,APCE,
386 APCE,APCE,APCE,APCE,APCE,APCE,APCE,APCE,
387 APCE,APCE,APCE,APCE,APCE,APCE,APCE,APCE)));
388
389 ensureConsistencyWithExpectations(expected,
390 glf.getAllAlternativesFound());
391 }
392
393//------------------------------------------------------------------------------
394
395 @Test
396 public void testLinkFromEdgeNoMatch() throws Exception
397 {
398 FragmentSpace fs = prepare();
399 DGraph graph = makeTestGraphF();
400 Edge targetEdge = graph.getEdgeAtPosition(0);
401 GraphLinkFinder glf = new GraphLinkFinder(fs, targetEdge, -1, true);
402 // NB: the boolean makes the search complete (within the limits the
403 // prevent combinatorial explosion)
404 // NB: "-1" is for "no selection of specific new building block".
405
406 // Expected results in terms of <bbId:list of classes>
407 Map<Integer,List<APClass>> expected =
408 new HashMap<Integer,List<APClass>>();
409
410 ensureConsistencyWithExpectations(expected,
411 glf.getAllAlternativesFound());
412 }
413
414//------------------------------------------------------------------------------
415
416 private void ensureConsistencyWithExpectations(
417 Map<Integer,List<APClass>> expected,
418 Map<Vertex, List<APMapping>> actual)
419 {
420 // Set this to true to print the mappings on stdout
421 boolean debug = false;
422
423 for (Vertex k : actual.keySet())
424 {
425 int bbId = k.getBuildingBlockId();
426
427 if (debug)
428 {
429 System.out.println("BBID: "+bbId);
430 }
431
432 List<APMapping> list = actual.get(k);
433
434 assertTrue(expected.containsKey(bbId), "Vertex with building block "
435 + "ID '" + bbId + "' should not among the results.");
436 assertEquals(expected.get(bbId).size() / 4, actual.get(k).size(),
437 "Number of APmappings is wrong for bbId '" + bbId + "'.");
438
439 int i=-1;
440 List<APClass> refList = expected.get(bbId);
441 for (APMapping apm : list)
442 {
443 if (debug)
444 {
445 System.out.println(" -> "+apm.toString());
446 }
447 for (Entry<AttachmentPoint, AttachmentPoint> e
448 : apm.entrySet())
449 {
450 if (debug)
451 {
452 System.out.println(" -> "+e.getKey().getAPClass()
453 +" "+e.getValue().getAPClass());
454 }
455 i++;
456 assertEquals(refList.get(i),e.getKey().getAPClass(),
457 "APClass in APMapping for bbId "+bbId+" entry " +i);
458 i++;
459 assertEquals(refList.get(i),e.getValue().getAPClass(),
460 "APClass in APMapping for bbId "+bbId+" entry " +i);
461 }
462 }
463 }
464
465 }
466
467//------------------------------------------------------------------------------
468
469}
denoptim.fragspace.FragmentSpace
Class defining a space of building blocks.
Definition: FragmentSpace.java:67
denoptim.fragspace.FragmentSpace.appendVertexToLibrary
void appendVertexToLibrary(Vertex v, Vertex.BBType bbt, ArrayList< Vertex > library)
Takes a vertex and add it to a given library.
Definition: FragmentSpace.java:1498
denoptim.fragspace.FragmentSpace.getVertexFromLibrary
Vertex getVertexFromLibrary(Vertex.BBType bbType, int bbIdx)
Returns a clone of the requested building block.
Definition: FragmentSpace.java:532
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.FragmentSpace.groupAndClassifyFragments
void groupAndClassifyFragments(boolean apClassBasedApproch)
Performs grouping and classification operations on the library of building blocks of BBType#FRAGMENT.
Definition: FragmentSpace.java:1894
denoptim.fragspace.FragmentSpace.getScaffoldLibrary
ArrayList< Vertex > getScaffoldLibrary()
Definition: FragmentSpace.java:726
denoptim.fragspace.FragmentSpace.getFragmentLibrary
ArrayList< Vertex > getFragmentLibrary()
Definition: FragmentSpace.java:733
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.getEdgeAtPosition
Edge getEdgeAtPosition(int pos)
Definition: DGraph.java:2649
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.getVertexAtPosition
Vertex getVertexAtPosition(int pos)
Returns the vertex that is in the given position of the list of vertices belonging to this graph.
Definition: DGraph.java:2514
denoptim.graph.DGraph.renumberGraphVertices
void renumberGraphVertices()
Reassign vertex IDs to all vertices of this graph.
Definition: DGraph.java:5283
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.addAP
void addAP()
Adds an attachment point with no APClass or other attribute.
Definition: EmptyVertex.java:298
denoptim.graph.Vertex
A vertex is a data structure that has an identity and holds a list of AttachmentPoints.
Definition: Vertex.java:61
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