1 /*
2  * Copyright (C) 2012 John May <jwmay@users.sf.net>
3  *
4  * Contact: cdk-devel@lists.sourceforge.net
5  *
6  * This program is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU Lesser General Public License as published by the
8  * Free Software Foundation; either version 2.1 of the License, or (at your
9  * option) any later version. All we ask is that proper credit is given for our
10  * work, which includes - but is not limited to - adding the above copyright
11  * notice to the beginning of your source code files, and to any copyright
12  * notice that you may distribute with programs based on this work.
13  *
14  * This program is distributed in the hope that it will be useful, but WITHOUT
15  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
17  * for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public License
20  * along with this program; if not, write to the Free Software Foundation, Inc.,
21  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
22  */
23 package org.openscience.cdk.ringsearch;
24 
25 import org.junit.Test;
26 
27 import java.util.BitSet;
28 
29 import static org.hamcrest.CoreMatchers.is;
30 import static org.junit.Assert.assertFalse;
31 import static org.junit.Assert.assertNotNull;
32 import static org.junit.Assert.assertThat;
33 import static org.junit.Assert.assertTrue;
34 
35 /**
36  * @author John May
37  * @cdk.module test-core
38  */
39 public class JumboCyclicVertexSearchTest {
40 
41     @Test
testEmpty()42     public void testEmpty() {
43         CyclicVertexSearch search = new JumboCyclicVertexSearch(new int[0][0]);
44         assertNotNull(search);
45     }
46 
47     @Test
testCyclic()48     public void testCyclic() {
49         // cyclohexane like
50         int[][] g = new int[][]{{5, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 0}};
51         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
52         assertThat(search.cyclic(), is(new int[]{0, 1, 2, 3, 4, 5}));
53     }
54 
55     @Test
testCyclic_Int()56     public void testCyclic_Int() {
57         // cyclohexane like
58         int[][] g = new int[][]{{5, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 0}};
59         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
60         for (int v = 0; v < g.length; v++)
61             assertTrue(search.cyclic(v));
62     }
63 
64     @Test
testCyclic_IntInt()65     public void testCyclic_IntInt() {
66         int[][] g = new int[][]{{5, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 0, 6}, {5}};
67         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
68         assertTrue(search.cyclic(0, 1));
69         assertTrue(search.cyclic(1, 2));
70         assertTrue(search.cyclic(2, 3));
71         assertTrue(search.cyclic(3, 4));
72         assertTrue(search.cyclic(4, 5));
73         assertTrue(search.cyclic(5, 0));
74         assertFalse(search.cyclic(5, 6));
75     }
76 
77     @Test
vertexColor()78     public void vertexColor() {
79         // medium size spiro cyclo hexane like
80         int[][] g = new int[][]{{1, 5}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {0, 4, 7, 8}, {7, 10}, {5, 6}, {5, 9}, {8, 10},
81                 {6, 9, 12, 13}, {12, 15}, {10, 11}, {10, 14}, {13, 15}, {11, 14, 17, 18}, {17, 20}, {15, 16}, {15, 19},
82                 {18, 20}, {16, 19, 22, 23}, {22, 25}, {20, 21}, {20, 24}, {23, 25}, {21, 24, 27, 28}, {27, 30},
83                 {25, 26}, {25, 29}, {28, 30}, {26, 29, 32, 33}, {32, 35}, {30, 31}, {30, 34}, {33, 35},
84                 {31, 34, 37, 38}, {37, 40}, {35, 36}, {35, 39}, {38, 40}, {36, 39, 42, 43}, {42, 45}, {40, 41},
85                 {40, 44}, {43, 45}, {41, 44, 47, 48}, {47, 50}, {45, 46}, {45, 49}, {48, 50}, {46, 49, 52, 53},
86                 {52, 55}, {50, 51}, {50, 54}, {53, 55}, {51, 54, 57, 58}, {57, 60}, {55, 56}, {55, 59}, {58, 60},
87                 {56, 59}};
88         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
89         int[] colors = search.vertexColor();
90     }
91 
92     @Test
testIsolated()93     public void testIsolated() {
94         // cyclohexane like
95         int[][] g = new int[][]{{5, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 0}};
96         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
97         assertThat(search.isolated(), is(new int[][]{{0, 1, 2, 3, 4, 5}}));
98     }
99 
100     @Test
testIsolated_NonCyclic()101     public void testIsolated_NonCyclic() {
102         int[][] g = new int[][]{{1}, {0, 2}, {1, 3}, {2, 4}, {3}};
103         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
104         assertThat(search.cyclic(), is(new int[0]));
105     }
106 
107     @Test
testIsolated_Empty()108     public void testIsolated_Empty() {
109         CyclicVertexSearch search = new JumboCyclicVertexSearch(new int[0][0]);
110         assertThat(search.cyclic(), is(new int[0]));
111         assertThat(search.isolated(), is(new int[0][0]));
112         assertThat(search.fused(), is(new int[0][0]));
113     }
114 
115     /**
116      * C1CCC2(CC1)CCCCC2
117      */
118     @Test
testIsolated_Spiro()119     public void testIsolated_Spiro() {
120         // spiro cyclo hexane like
121         int[][] g = new int[][]{{1, 5}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {0, 4, 7, 8}, {7, 10}, {5, 6}, {5, 9}, {8, 10},
122                 {6, 9}};
123         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
124         int[][] isolated = search.isolated();
125         assertThat(isolated.length, is(2));
126         assertThat(isolated[0], is(new int[]{0, 1, 2, 3, 4, 5}));
127         assertThat(isolated[1], is(new int[]{5, 6, 7, 8, 9, 10}));
128     }
129 
130     /**
131      * C1CCC2(CC1)CCC1(CC2)CCC2(CC1)CCC1(CC2)CCC2(CC1)CCC1(CC2)CCC2(CCC3(CCC4(CCC5(CCC6(CCCCC6)CC5)CC4)CC3)CC2)CC1
132      */
133     @Test
testIsolated_SpiroMedium()134     public void testIsolated_SpiroMedium() {
135         // medium size spiro cyclo hexane like
136         int[][] g = new int[][]{{1, 5}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {0, 4, 7, 8}, {7, 10}, {5, 6}, {5, 9}, {8, 10},
137                 {6, 9, 12, 13}, {12, 15}, {10, 11}, {10, 14}, {13, 15}, {11, 14, 17, 18}, {17, 20}, {15, 16}, {15, 19},
138                 {18, 20}, {16, 19, 22, 23}, {22, 25}, {20, 21}, {20, 24}, {23, 25}, {21, 24, 27, 28}, {27, 30},
139                 {25, 26}, {25, 29}, {28, 30}, {26, 29, 32, 33}, {32, 35}, {30, 31}, {30, 34}, {33, 35},
140                 {31, 34, 37, 38}, {37, 40}, {35, 36}, {35, 39}, {38, 40}, {36, 39, 42, 43}, {42, 45}, {40, 41},
141                 {40, 44}, {43, 45}, {41, 44, 47, 48}, {47, 50}, {45, 46}, {45, 49}, {48, 50}, {46, 49, 52, 53},
142                 {52, 55}, {50, 51}, {50, 54}, {53, 55}, {51, 54, 57, 58}, {57, 60}, {55, 56}, {55, 59}, {58, 60},
143                 {56, 59}};
144         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
145         int[][] isolated = search.isolated();
146         assertThat(isolated.length, is(12));
147         assertThat(isolated[0], is(new int[]{0, 1, 2, 3, 4, 5}));
148         assertThat(isolated[1], is(new int[]{5, 6, 7, 8, 9, 10}));
149         assertThat(isolated[2], is(new int[]{10, 11, 12, 13, 14, 15}));
150         assertThat(isolated[3], is(new int[]{15, 16, 17, 18, 19, 20}));
151         assertThat(isolated[4], is(new int[]{20, 21, 22, 23, 24, 25}));
152         assertThat(isolated[5], is(new int[]{25, 26, 27, 28, 29, 30}));
153         assertThat(isolated[6], is(new int[]{30, 31, 32, 33, 34, 35}));
154         assertThat(isolated[7], is(new int[]{35, 36, 37, 38, 39, 40}));
155         assertThat(isolated[8], is(new int[]{40, 41, 42, 43, 44, 45}));
156         assertThat(isolated[9], is(new int[]{45, 46, 47, 48, 49, 50}));
157         assertThat(isolated[10], is(new int[]{50, 51, 52, 53, 54, 55}));
158         assertThat(isolated[11], is(new int[]{55, 56, 57, 58, 59, 60}));
159     }
160 
161     @Test
testIsolated_Biphenyl()162     public void testIsolated_Biphenyl() {
163         // biphenyl like
164         int[][] g = new int[][]{{5, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 0, 6}, {11, 7, 5}, {6, 8}, {7, 9}, {8, 10},
165                 {9, 11}, {10, 7}};
166         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
167         assertThat(search.cyclic(), is(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}));
168         int[][] isolated = search.isolated();
169         assertThat(isolated.length, is(2));
170         assertThat(isolated[0], is(new int[]{0, 1, 2, 3, 4, 5}));
171         assertThat(isolated[1], is(new int[]{6, 7, 8, 9, 10, 11}));
172     }
173 
174     /**
175      * C(C1CCCCC1)C1CCCCC1
176      */
177     @Test
testIsolated_BenzylBenzene()178     public void testIsolated_BenzylBenzene() {
179         // benzylbenzene like
180         int[][] g = new int[][]{{1, 5}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {0, 4, 12}, {7, 11}, {6, 8}, {7, 9, 12},
181                 {8, 10}, {9, 11}, {6, 10}, {8, 5}};
182         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
183         int[][] isolated = search.isolated();
184         assertThat(isolated.length, is(2));
185         assertThat(isolated[0], is(new int[]{0, 1, 2, 3, 4, 5}));
186         assertThat(isolated[1], is(new int[]{6, 7, 8, 9, 10, 11}));
187     }
188 
189     @Test
testIsolatedFragments()190     public void testIsolatedFragments() {
191         // two disconnected cyclohexanes
192         int[][] g = new int[][]{{5, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 0}, {11, 7}, {6, 8}, {7, 9}, {8, 10},
193                 {9, 11}, {10, 7}};
194         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
195         assertThat(search.cyclic(), is(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}));
196         int[][] isolated = search.isolated();
197         assertThat(isolated.length, is(2));
198         assertThat(isolated[0], is(new int[]{0, 1, 2, 3, 4, 5}));
199         assertThat(isolated[1], is(new int[]{6, 7, 8, 9, 10, 11}));
200     }
201 
202     /**
203      * C1CC2CCC1CC2
204      */
205     @Test
testFused()206     public void testFused() {
207         int[][] g = new int[][]{{1, 5, 6}, {0, 2}, {1, 3}, {2, 4, 7}, {3, 5}, {0, 4}, {0, 7}, {6, 3}};
208         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
209         int[][] isolated = search.isolated();
210         int[][] fused = search.fused();
211         assertThat(isolated.length, is(0));
212         assertThat(fused.length, is(1));
213         assertThat(fused[0].length, is(g.length));
214     }
215 
216     /**
217      * two fused systems which are edge disjoint with respect to each other but
218      * have a (non cyclic) edge which connects them C1CC2(CCC1CC2)C12CCC(CC1)CC2
219      */
220     @Test
testFused_BiocycloEdgeLinked()221     public void testFused_BiocycloEdgeLinked() {
222         // biocyclooctanylbiocylooctane like
223         int[][] g = new int[][]{{1, 5, 6}, {0, 2}, {1, 3}, {2, 4, 7, 8}, {3, 5}, {0, 4}, {0, 7}, {6, 3},
224                 {9, 13, 14, 3}, {8, 10}, {9, 11}, {10, 12, 15}, {11, 13}, {8, 12}, {8, 15}, {11, 14}};
225         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
226         int[][] isolated = search.isolated();
227         int[][] fused = search.fused();
228         assertThat(isolated.length, is(0));
229         assertThat(fused.length, is(2));
230         assertThat(fused[0], is(new int[]{0, 1, 2, 3, 4, 5, 6, 7}));
231         assertThat(fused[1], is(new int[]{8, 9, 10, 11, 12, 13, 14, 15}));
232     }
233 
234     /**
235      * two fused systems which are edge disjoint with respect to each other
236      * however in between the two fused cycle systems there is a single non
237      * cyclic vertex which is adjacent to both C(C12CCC(CC1)CC2)C12CCC(CC1)CC2
238      */
239     @Test
testFused_BiocycloVertexLinked()240     public void testFused_BiocycloVertexLinked() {
241         // biocyclooctanylbiocylooctane like
242         int[][] g = new int[][]{{1, 5}, {0, 2}, {1, 3, 6, 16}, {2, 4}, {3, 5}, {4, 0, 7}, {2, 7}, {6, 5}, {9, 13},
243                 {8, 10}, {9, 11, 14}, {10, 12}, {11, 13}, {12, 8, 15, 16}, {10, 15}, {14, 13}, {13, 2}};
244         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
245         int[][] isolated = search.isolated();
246         int[][] fused = search.fused();
247         assertThat(isolated.length, is(0));
248         assertThat(fused.length, is(2));
249         assertThat(fused[0], is(new int[]{0, 1, 2, 3, 4, 5, 6, 7}));
250         assertThat(fused[1], is(new int[]{8, 9, 10, 11, 12, 13, 14, 15}));
251     }
252 
253     /**
254      * C1CCC2CCCCC2C1
255      */
256     @Test
testFused_Orthofused()257     public void testFused_Orthofused() {
258         // napthalene like
259         int[][] g = new int[][]{{1, 5}, {0, 2}, {1, 3}, {2, 4}, {3, 5, 7}, {0, 6, 4}, {5, 9}, {4, 8}, {7, 9}, {6, 8}};
260         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
261         int[][] isolated = search.isolated();
262         int[][] fused = search.fused();
263         assertThat(isolated.length, is(0));
264         assertThat(fused.length, is(1));
265         assertThat(fused[0].length, is(g.length));
266     }
267 
268     /**
269      * C1CCC2CC3CCCCC3CC2C1
270      */
271     @Test
testFused_Biorthofused()272     public void testFused_Biorthofused() {
273         // 3 fused rings
274         int[][] g = new int[][]{{1, 5}, {0, 2, 10}, {3, 13, 1}, {2, 4}, {3, 5, 7}, {0, 6, 4}, {5, 9}, {4, 8}, {7, 9},
275                 {6, 8}, {1, 11}, {10, 12}, {11, 13}, {2, 12}};
276         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
277         int[][] isolated = search.isolated();
278         int[][] fused = search.fused();
279         assertThat(isolated.length, is(0));
280         assertThat(fused.length, is(1));
281         assertThat(fused[0].length, is(g.length));
282     }
283 
284     /**
285      * C1CC23CCC4(CC2)CCC2(CCCC5(CCCC6(CCC7(CCCC8(CCC9(CC8)CCC8(CCCC%10(CCCC%11(CCC(C1)(CC%11)C3)C%10)C8)CC9)C7)CC6)C5)C2)CC4
286      */
287     @Test
testFused_Cylclophane()288     public void testFused_Cylclophane() {
289         // medium size spiro cyclophane
290         int[][] g = new int[][]{{1, 5}, {0, 2}, {1, 3, 50, 46}, {2, 4}, {3, 5}, {0, 4, 7, 8}, {7, 10}, {5, 6}, {5, 9},
291                 {8, 10}, {6, 9, 12, 13}, {12, 15}, {10, 11}, {10, 14}, {13, 15, 16, 17}, {11, 14}, {14, 20}, {14, 18},
292                 {17, 19}, {18, 20, 21, 22}, {16, 19}, {19, 25}, {19, 23}, {22, 24, 26, 30}, {23, 25}, {21, 24},
293                 {23, 27}, {26, 28, 35, 31}, {27, 29}, {28, 30}, {23, 29}, {27, 32}, {31, 33}, {32, 34, 40, 36},
294                 {33, 35}, {27, 34}, {33, 37}, {36, 38}, {37, 39, 45, 41}, {38, 40}, {33, 39}, {38, 42},
295                 {41, 43, 58, 59}, {42, 44}, {43, 45}, {38, 44}, {2, 47}, {46, 48}, {47, 49}, {48, 50, 51, 55}, {2, 49},
296                 {49, 52}, {51, 53}, {52, 54}, {53, 55, 56, 57}, {49, 54}, {54, 59}, {54, 58}, {42, 57}, {42, 56}};
297         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
298         int[][] isolated = search.isolated();
299         int[][] fused = search.fused();
300         assertThat(isolated.length, is(0));
301         assertThat(fused.length, is(1));
302         assertThat(fused[0].length, is(g.length));
303     }
304 
305     /**
306      * CHEBI:33128
307      */
308     @Test
testFused_Fullerene()309     public void testFused_Fullerene() {
310         int[][] g = new int[][]{{1, 4, 8}, {0, 2, 11}, {1, 3, 14}, {2, 4, 17}, {3, 0, 5}, {4, 6, 19}, {5, 7, 21},
311                 {6, 8, 24}, {7, 0, 9}, {8, 10, 25}, {9, 11, 28}, {10, 1, 12}, {11, 13, 29}, {12, 14, 32}, {13, 2, 15},
312                 {14, 16, 33}, {15, 17, 36}, {16, 3, 18}, {17, 19, 37}, {18, 5, 20}, {19, 21, 39}, {20, 6, 22},
313                 {21, 23, 41}, {22, 24, 43}, {23, 7, 25}, {24, 9, 26}, {25, 27, 44}, {26, 28, 46}, {27, 10, 29},
314                 {28, 12, 30}, {29, 31, 47}, {30, 32, 49}, {31, 13, 33}, {32, 15, 34}, {33, 35, 50}, {34, 36, 52},
315                 {35, 16, 37}, {36, 18, 38}, {37, 39, 53}, {38, 20, 40}, {39, 41, 54}, {40, 22, 42}, {41, 43, 56},
316                 {42, 23, 44}, {43, 26, 45}, {44, 46, 57}, {45, 27, 47}, {46, 30, 48}, {47, 49, 58}, {48, 31, 50},
317                 {49, 34, 51}, {50, 52, 59}, {51, 35, 53}, {52, 38, 54}, {53, 40, 55}, {54, 56, 59}, {55, 42, 57},
318                 {56, 45, 58}, {57, 48, 59}, {58, 51, 55}};
319         CyclicVertexSearch search = new JumboCyclicVertexSearch(g);
320         int[][] isolated = search.isolated();
321         int[][] fused = search.fused();
322         assertThat(isolated.length, is(0));
323         assertThat(fused.length, is(1));
324         assertThat(fused[0].length, is(g.length));
325     }
326 
327     @Test
testToArray()328     public void testToArray() throws Exception {
329         BitSet s = new BitSet();
330         s.set(0);
331         s.set(6);
332         assertThat(JumboCyclicVertexSearch.toArray(s), is(new int[]{0, 6}));
333     }
334 
335     @Test
testToArray_Empty()336     public void testToArray_Empty() throws Exception {
337         BitSet empty = new BitSet();
338         assertThat(JumboCyclicVertexSearch.toArray(empty), is(new int[0]));
339     }
340 
341     @Test
testXor()342     public void testXor() throws Exception {
343         BitSet s = new BitSet();
344         BitSet t = new BitSet();
345 
346         s.set(0);
347         s.set(1);
348         t.set(1);
349         t.set(2);
350 
351         BitSet u = JumboCyclicVertexSearch.xor(s, t);
352 
353         assertTrue(s.get(0));
354         assertTrue(s.get(1));
355         assertFalse(s.get(2));
356 
357         assertFalse(t.get(0));
358         assertTrue(t.get(1));
359         assertTrue(t.get(2));
360 
361         assertTrue(u.get(0));
362         assertFalse(u.get(1));
363         assertTrue(u.get(2));
364 
365     }
366 
367     @Test
testAnd()368     public void testAnd() throws Exception {
369 
370         BitSet s = new BitSet();
371         BitSet t = new BitSet();
372 
373         s.set(0);
374         s.set(1);
375         t.set(1);
376         t.set(2);
377 
378         BitSet u = JumboCyclicVertexSearch.and(s, t);
379 
380         assertTrue(s.get(0));
381         assertTrue(s.get(1));
382         assertFalse(s.get(2));
383 
384         assertFalse(t.get(0));
385         assertTrue(t.get(1));
386         assertTrue(t.get(2));
387 
388         assertFalse(u.get(0));
389         assertTrue(u.get(1));
390         assertFalse(u.get(2));
391 
392     }
393 
394     @Test
testCopy()395     public void testCopy() throws Exception {
396         BitSet set = new BitSet();
397         set.set(5);
398         BitSet cpy = JumboCyclicVertexSearch.copy(set);
399         assertTrue(cpy.get(5));
400         set.set(6);
401         assertFalse(cpy.get(6));
402     }
403 }
404