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.openscience.cdk.exception.NoSuchAtomException; 26 import org.openscience.cdk.graph.GraphUtil; 27 import org.openscience.cdk.interfaces.IAtom; 28 import org.openscience.cdk.interfaces.IAtomContainer; 29 import org.openscience.cdk.interfaces.IBond; 30 import org.openscience.cdk.interfaces.IChemObjectBuilder; 31 32 import java.util.ArrayList; 33 import java.util.HashSet; 34 import java.util.List; 35 import java.util.NoSuchElementException; 36 import java.util.Set; 37 38 /** 39 * Efficiently search for atoms that are members of a ring. A depth first search 40 * (DFS) determines which vertices belong to cycles (rings). As cycles are 41 * discovered they are separated into two sets of cycle systems, fused and 42 * isolated. A ring is in a fused cycle systems if it shares at least one edge 43 * (bond) with another cycle. The isolated cycles consist of cycles which at 44 * most share only one vertex (atom) with another cyclic system. A molecule may 45 * contain more then one isolated and/or fused cycle system (see. Examples). 46 * Additional computations such as C<sub>R</sub> (relevant cycles), Minimum 47 * Cycle Basis (MCB) (aka. Smallest Set of Smallest Rings (SSSR)) or the Set of 48 * All Rings can be completely bypassed for members of the isolated rings. Since 49 * every isolated cycle (ring) does not share any edges (bonds) with any other 50 * elementary cycle it cannot be made by composing any other cycles (rings). 51 * Therefore, all isolated cycles (rings) are relevant and are members of all 52 * minimum cycle bases (SSSRs). <b>Important</b> the cycle sets returned are not 53 * ordered in the path of the cycle. 54 * 55 * <br> <b>Further Explanation</b> The diagram below illustrates the isolated 56 * and fused sets of cyclic atoms. The colored circles indicate the atoms and 57 * bonds that are returned for each molecules. <br><br> <img alt="isolated and 58 * fused cycle systems" src="http://cdk.github.io/cdk/img/isolated-and-fused-cycles-01_zpse0311377.PNG"> 59 * <br> <ol type="a"> <li>Two separate isolated cycles</li> <li>Two 60 * separate fused cycle systems. The bridged systems are fused but separate from 61 * each other</li> <li>Fused rings - a single fused cycle system</li> <li>Spiro 62 * rings - three separate isolated systems, no bonds are shared</li> 63 * <li>Cyclophane - a single fused system, the perimeter rings share bonds with 64 * the smaller rings </li> <li>One isolated system and one fused system</li> 65 * </ol> 66 * 67 * <br> 68 * <b>Example Usage</b> 69 * <blockquote><pre>{@code 70 * // construct the search for a given molecule, if an adjacency list 71 * // representation (int[][]) is available this can be passed to the 72 * // constructor for improved performance 73 * IAtomContainer container = ...; 74 * RingSearch ringSearch = new RingSearch(container); 75 * 76 * // indices of cyclic vertices 77 * int[] cyclic = ringSearch.cyclic(); 78 * 79 * // iterate over fused systems (atom indices) 80 * for(int[] fused : ringSearch.fused()){ 81 * ... 82 * } 83 * 84 * // iterate over isolated rings (atom indices) 85 * for(int[] isolated : ringSearch.isolated()){ 86 * ... 87 * } 88 * 89 * // convenience methods for getting the fragments 90 * IAtomContainer cyclic = ringSearch.ringFragments(); 91 * 92 * for(IAtomContainer fragment : ringSearch.fusedRingFragments()){ 93 * .... 94 * } 95 * for(IAtomContainer fragment : ringSearch.isolatedRingFragments()){ 96 * .... 97 * } 98 * }</pre></blockquote> 99 * 100 * @author John May 101 * @cdk.module core 102 * @cdk.githash 103 * @see <a href="http://en.wikipedia.org/wiki/Cycle_(graph_theory)">Cycle (Graph 104 * Theory) - Wikipedia</a> 105 * @see <a href="http://efficientbits.blogspot.co.uk/2012/12/scaling-up-faster-ring-detection-in-cdk.html">Scaling 106 * Up: Faster Ring Detecting in CDK - Efficient Bits, Blog</a> 107 * @see org.openscience.cdk.graph.SpanningTree 108 * @see SSSRFinder 109 * @see AllRingsFinder 110 * @see CyclicVertexSearch 111 */ 112 public final class RingSearch { 113 114 /* depending on molecule size, delegate the search to one of two sub-classes */ 115 private final CyclicVertexSearch searcher; 116 117 /* input atom container */ 118 private final IAtomContainer container; 119 120 /** 121 * Create a new RingSearch for the specified container. 122 * 123 * @param container non-null input structure 124 * @throws NullPointerException if the container was null 125 * @throws IllegalArgumentException if the container contains a bond which 126 * references an atom which could not be 127 * found 128 */ RingSearch(IAtomContainer container)129 public RingSearch(IAtomContainer container) { 130 this(container, GraphUtil.toAdjList(container)); 131 } 132 133 /** 134 * Create a new RingSearch for the specified container and graph. The 135 * adjacency list allows much faster graph traversal but is not free to 136 * create. If the adjacency list representation of the input container has 137 * already been created you can bypass the creation with this constructor. 138 * 139 * @param container non-null input structure 140 * @param graph non-null adjacency list representation of the container 141 * @throws NullPointerException if the container or graph was null 142 */ RingSearch(IAtomContainer container, int[][] graph)143 public RingSearch(IAtomContainer container, int[][] graph) { 144 this(container, makeSearcher(graph)); 145 } 146 147 /** 148 * Create a new RingSearch for the specified container using the provided 149 * search. 150 * 151 * @param container non-null input structure 152 * @param searcher non-null adjacency list representation of the container 153 * @throws NullPointerException if the container or searcher was null 154 */ RingSearch(IAtomContainer container, CyclicVertexSearch searcher)155 public RingSearch(IAtomContainer container, CyclicVertexSearch searcher) { 156 if (container == null) throw new NullPointerException("container must not be null"); 157 if (searcher == null) throw new NullPointerException("searcher was null"); 158 this.searcher = searcher; 159 this.container = container; 160 } 161 162 /** 163 * Utility method making a new {@link CyclicVertexSearch} during 164 * construction. 165 * 166 * @param graph non-null graph 167 * @return a new cyclic vertex search for the given graph 168 * @throws NullPointerException if the graph was null 169 */ makeSearcher(int[][] graph)170 private static CyclicVertexSearch makeSearcher(int[][] graph) { 171 172 if (graph == null) throw new NullPointerException("graph[][] must not be null"); 173 174 // if the molecule has 64 or less atoms we can use single 64 bit long 175 // values to represent our sets of vertices 176 if (graph.length <= 64) { 177 return new RegularCyclicVertexSearch(graph); 178 } else { 179 return new JumboCyclicVertexSearch(graph); 180 } 181 } 182 183 /** 184 * Access the number of rings found (aka. circuit rank, SSSR size). 185 * 186 * @return number of rings 187 * @see <a href="https://en.wikipedia.org/wiki/Circuit_rank">Circuit Rank</a> 188 */ numRings()189 public int numRings() { 190 return searcher.numCycles(); 191 } 192 193 /** 194 * Determine whether the edge between the vertices <i>u</i> and <i>v</i> is 195 * cyclic. 196 * 197 * @param u an end point of the edge 198 * @param v another end point of the edge 199 * @return whether the edge formed by the given end points is in a cycle 200 */ cyclic(int u, int v)201 public boolean cyclic(int u, int v) { 202 return searcher.cyclic(u, v); 203 } 204 205 /** 206 * Determine whether the provided atom belongs to a ring (is cyclic). 207 * 208 * <blockquote><pre>{@code 209 * IAtomContainer mol = ...; 210 * RingSearch ringSearch = new RingSearch(mol); 211 * 212 * for(IAtom atom : mol.atoms()){ 213 * if(ringSearch.cyclic(atom)){ 214 * ... 215 * } 216 * } 217 * }</pre></blockquote> 218 * 219 * @param atom an atom 220 * @return whether the atom is in a ring 221 * @throws NoSuchAtomException the atom was not found 222 */ cyclic(IAtom atom)223 public boolean cyclic(IAtom atom) { 224 int i = container.indexOf(atom); 225 if (i < 0) throw new NoSuchAtomException("no such atom"); 226 return cyclic(i); 227 } 228 229 /** 230 * Determine whether the bond is cyclic. Note this currently requires a 231 * linear search to look-up the indices of each atoms. 232 * 233 * @param bond a bond of the container 234 * @return whether the vertex at the given index is in a cycle 235 */ cyclic(IBond bond)236 public boolean cyclic(IBond bond) { 237 // XXX: linear search - but okay for now 238 int u = container.indexOf(bond.getBegin()); 239 int v = container.indexOf(bond.getEnd()); 240 if (u < 0 || v < 0) throw new NoSuchElementException("atoms of the bond are not found in the container"); 241 return searcher.cyclic(u, v); 242 } 243 244 /** 245 * Determine whether the vertex at index <i>i</i> is a cyclic vertex. 246 * 247 * <blockquote><pre>{@code 248 * IAtomContainer mol = ...; 249 * RingSearch tester = new RingSearch(mol); 250 * 251 * int n = mol.getAtomCount(); 252 * for(int i = 0; i < n; i++){ 253 * if(tester.cyclic(i)){ 254 * ... 255 * } 256 * } 257 * }</pre></blockquote> 258 * 259 * @param i atom index 260 * @return whether the vertex at the given index is in a cycle 261 */ cyclic(int i)262 public boolean cyclic(int i) { 263 return searcher.cyclic(i); 264 } 265 266 /** 267 * Construct a set of vertices which belong to any cycle (ring). 268 * 269 * @return cyclic vertices 270 */ cyclic()271 public int[] cyclic() { 272 return searcher.cyclic(); 273 } 274 275 /** 276 * Construct the sets of vertices which belong to isolated rings. 277 * 278 * <blockquote><pre>{@code 279 * IAtomContainer biphenyl = ...; 280 * RingSearch ringSearch = new RingSearch(biphenyl); 281 * 282 * int[][] isolated = ringSearch.isolated(); 283 * isolated.length; // 2 isolated rings in biphenyl 284 * 285 * isolated[0].length; // 6 vertices in one benzene 286 * isolated[1].length; // 6 vertices in the other benzene 287 * 288 * }</pre></blockquote> 289 * 290 * @return array of isolated fragments, defined by the vertices in the 291 * fragment 292 */ isolated()293 public int[][] isolated() { 294 return searcher.isolated(); 295 } 296 297 /** 298 * Construct the sets of vertices which belong to fused ring systems. 299 * 300 * <blockquote><pre>{@code 301 * IAtomContainer mol = ...; 302 * RingSearch ringSearch = new RingSearch(mol); 303 * 304 * int[][] fused = ringSearch.fused(); 305 * fused.length; // e.g. 3 separate fused ring systems 306 * 307 * fused[0].length; // e.g. 6 vertices in the first system 308 * fused[1].length; // e.g. 10 vertices in the second system 309 * fused[2].length; // e.g. 4 vertices in the third system 310 * 311 * }</pre></blockquote> 312 * 313 * @return array of fused fragments, defined by the vertices in the 314 * fragment 315 */ fused()316 public int[][] fused() { 317 return searcher.fused(); 318 } 319 320 /** 321 * Extract the cyclic atom and bond fragments of the container. Bonds which 322 * join two different isolated/fused cycles (e.g. biphenyl) are not be 323 * included. 324 * 325 * @return a new container with only the cyclic atoms and bonds 326 * @see org.openscience.cdk.graph.SpanningTree#getCyclicFragmentsContainer() 327 */ ringFragments()328 public IAtomContainer ringFragments() { 329 330 int[] vertices = cyclic(); 331 332 int n = vertices.length; 333 334 IAtom[] atoms = new IAtom[n]; 335 List<IBond> bonds = new ArrayList<IBond>(); 336 337 for (int i = 0; i < vertices.length; i++) { 338 atoms[i] = container.getAtom(vertices[i]); 339 } 340 341 for (IBond bond : container.bonds()) { 342 343 IAtom either = bond.getBegin(); 344 IAtom other = bond.getEnd(); 345 346 int u = container.indexOf(either); 347 int v = container.indexOf(other); 348 349 // add the bond if the vertex colors match 350 if (searcher.cyclic(u, v)) bonds.add(bond); 351 } 352 353 IChemObjectBuilder builder = container.getBuilder(); 354 IAtomContainer fragment = builder.newInstance(IAtomContainer.class, 0, 0, 0, 0); 355 356 fragment.setAtoms(atoms); 357 fragment.setBonds(bonds.toArray(new IBond[bonds.size()])); 358 359 return fragment; 360 361 } 362 363 /** 364 * Determines whether the two vertex colors match. This method provides the 365 * conditional as to whether to include a bond in the construction of the 366 * {@link #ringFragments()}. 367 * 368 * @param eitherColor either vertex color 369 * @param otherColor other vertex color 370 * @return whether the two vertex colours match 371 */ match(int eitherColor, int otherColor)372 static boolean match(int eitherColor, int otherColor) { 373 return (eitherColor != -1 && otherColor != -1) 374 && (eitherColor == otherColor || (eitherColor == 0 || otherColor == 0)); 375 } 376 377 /** 378 * Construct a list of {@link IAtomContainer}s each of which only contains a 379 * single isolated ring. A ring is consider isolated if it does not share 380 * any bonds with another ring. By this definition each ring of a spiro ring 381 * system is considered isolated. The atoms are <b>not</b> arranged 382 * sequential. 383 * 384 * @return list of isolated ring fragments 385 * @see #isolated() 386 */ isolatedRingFragments()387 public List<IAtomContainer> isolatedRingFragments() { 388 return toFragments(isolated()); 389 } 390 391 /** 392 * Construct a list of {@link IAtomContainer}s which only contain fused 393 * rings. A ring is consider fused if it shares any bonds with another ring. 394 * By this definition bridged ring systems are also included. The atoms are 395 * <b>not</b> arranged sequential. 396 * 397 * @return list of fused ring fragments 398 * @see #fused() 399 */ fusedRingFragments()400 public List<IAtomContainer> fusedRingFragments() { 401 return toFragments(fused()); 402 } 403 404 /** 405 * Utility method for creating the fragments for the fused/isolated sets 406 * 407 * @param verticesList 2D array of vertices (rows=n fragments) 408 * @return the vertices converted to an atom container 409 * @see #toFragment(int[]) 410 * @see #fusedRingFragments() 411 * @see #isolatedRingFragments() 412 */ toFragments(int[][] verticesList)413 private List<IAtomContainer> toFragments(int[][] verticesList) { 414 List<IAtomContainer> fragments = new ArrayList<IAtomContainer>(); 415 for (int[] vertices : verticesList) { 416 fragments.add(toFragment(vertices)); 417 } 418 return fragments; 419 } 420 421 /** 422 * Utility method for creating a fragment from an array of vertices 423 * 424 * @param vertices array of vertices length=cycle weight, values 0 ... 425 * nAtoms 426 * @return atom container only containing the specified atoms (and bonds) 427 */ toFragment(int[] vertices)428 private IAtomContainer toFragment(int[] vertices) { 429 430 int n = vertices.length; 431 432 Set<IAtom> atoms = new HashSet<IAtom>(n > 3 ? n + 1 + n / 3 : n); 433 List<IBond> bonds = new ArrayList<IBond>(); 434 435 // fill the atom set 436 for (int v : vertices) { 437 atoms.add(container.getAtom(v)); 438 } 439 440 // include bonds that have both atoms in the atoms set 441 for (IBond bond : container.bonds()) { 442 IAtom either = bond.getBegin(); 443 IAtom other = bond.getEnd(); 444 if (atoms.contains(either) && atoms.contains(other)) { 445 bonds.add(bond); 446 } 447 } 448 449 IAtomContainer fragment = container.getBuilder().newInstance(IAtomContainer.class, 0, 0, 0, 0); 450 451 fragment.setAtoms(atoms.toArray(new IAtom[n])); 452 fragment.setBonds(bonds.toArray(new IBond[bonds.size()])); 453 454 return fragment; 455 } 456 } 457
