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