Class RingSearch

java.lang.Object
org.openscience.cdk.ringsearch.RingSearch

public final class RingSearch extends Object
Efficiently search for atoms that are members of a ring. A depth first search (DFS) determines which vertices belong to cycles (rings). As cycles are discovered they are separated into two sets of cycle systems, fused and isolated. A ring is in a fused cycle systems if it shares at least one edge (bond) with another cycle. The isolated cycles consist of cycles which at most share only one vertex (atom) with another cyclic system. A molecule may contain more then one isolated and/or fused cycle system (see. Examples). Additional computations such as CR (relevant cycles), Minimum Cycle Basis (MCB) (aka. Smallest Set of Smallest Rings (SSSR)) or the Set of All Rings can be completely bypassed for members of the isolated rings. Since every isolated cycle (ring) does not share any edges (bonds) with any other elementary cycle it cannot be made by composing any other cycles (rings). Therefore, all isolated cycles (rings) are relevant and are members of all minimum cycle bases (SSSRs). Important the cycle sets returned are not ordered in the path of the cycle.
Further Explanation The diagram below illustrates the isolated and fused sets of cyclic atoms. The colored circles indicate the atoms and bonds that are returned for each molecules.

isolated and
 fused cycle systems
  1. Two separate isolated cycles
  2. Two separate fused cycle systems. The bridged systems are fused but separate from each other
  3. Fused rings - a single fused cycle system
  4. Spiro rings - three separate isolated systems, no bonds are shared
  5. Cyclophane - a single fused system, the perimeter rings share bonds with the smaller rings
  6. One isolated system and one fused system

Example Usage

 // construct the search for a given molecule, if an adjacency list
 // representation (int[][]) is available this can be passed to the
 // constructor for improved performance
 IAtomContainer container  = ...;
 RingSearch     ringSearch = new RingSearch(container);

 // indices of cyclic vertices
 int[] cyclic = ringSearch.cyclic();

 // iterate over fused systems (atom indices)
 for(int[] fused : ringSearch.fused()){
     ...
 }

 // iterate over isolated rings (atom indices)
 for(int[] isolated : ringSearch.isolated()){
     ...
 }

 // convenience methods for getting the fragments
 IAtomContainer cyclic = ringSearch.ringFragments();

 for(IAtomContainer fragment : ringSearch.fusedRingFragments()){
     ....
 }
 for(IAtomContainer fragment : ringSearch.isolatedRingFragments()){
     ....
 }
 
Author:
John May
See Also:
Source code:
main
Belongs to CDK module:
core
  • Constructor Details

    • RingSearch

      public RingSearch(IAtomContainer container)
      Create a new RingSearch for the specified container.
      Parameters:
      container - non-null input structure
      Throws:
      NullPointerException - if the container was null
      IllegalArgumentException - if the container contains a bond which references an atom which could not be found
    • RingSearch

      public RingSearch(IAtomContainer container, int[][] graph)
      Create a new RingSearch for the specified container and graph. The adjacency list allows much faster graph traversal but is not free to create. If the adjacency list representation of the input container has already been created you can bypass the creation with this constructor.
      Parameters:
      container - non-null input structure
      graph - non-null adjacency list representation of the container
      Throws:
      NullPointerException - if the container or graph was null
    • RingSearch

      public RingSearch(IAtomContainer container, CyclicVertexSearch searcher)
      Create a new RingSearch for the specified container using the provided search.
      Parameters:
      container - non-null input structure
      searcher - non-null adjacency list representation of the container
      Throws:
      NullPointerException - if the container or searcher was null
  • Method Details

    • numRings

      public int numRings()
      Access the number of rings found (aka. circuit rank, SSSR size).
      Returns:
      number of rings
      See Also:
    • cyclic

      public boolean cyclic(int u, int v)
      Determine whether the edge between the vertices u and v is cyclic.
      Parameters:
      u - an end point of the edge
      v - another end point of the edge
      Returns:
      whether the edge formed by the given end points is in a cycle
    • cyclic

      public boolean cyclic(IAtom atom)
      Determine whether the provided atom belongs to a ring (is cyclic).
      
       IAtomContainer mol        = ...;
       RingSearch     ringSearch = new RingSearch(mol);
      
       for(IAtom atom : mol.atoms()){
           if(ringSearch.cyclic(atom)){
               ...
           }
       }
       
      Parameters:
      atom - an atom
      Returns:
      whether the atom is in a ring
      Throws:
      NoSuchAtomException - the atom was not found
    • cyclic

      public boolean cyclic(IBond bond)
      Determine whether the bond is cyclic. Note this currently requires a linear search to look-up the indices of each atoms.
      Parameters:
      bond - a bond of the container
      Returns:
      whether the vertex at the given index is in a cycle
    • cyclic

      public boolean cyclic(int i)
      Determine whether the vertex at index i is a cyclic vertex.
      
       IAtomContainer  mol    = ...;
       RingSearch      tester = new RingSearch(mol);
      
       int n = mol.getAtomCount();
       for(int i = 0; i < n; i++){
           if(tester.cyclic(i)){
               ...
           }
       }
       
      Parameters:
      i - atom index
      Returns:
      whether the vertex at the given index is in a cycle
    • cyclic

      public int[] cyclic()
      Construct a set of vertices which belong to any cycle (ring).
      Returns:
      cyclic vertices
    • isolated

      public int[][] isolated()
      Construct the sets of vertices which belong to isolated rings.
      
       IAtomContainer  biphenyl   = ...;
       RingSearch      ringSearch = new RingSearch(biphenyl);
      
       int[][] isolated = ringSearch.isolated();
       isolated.length; // 2 isolated rings in biphenyl
      
       isolated[0].length; // 6 vertices in one benzene
       isolated[1].length; // 6 vertices in the other benzene
      
       
      Returns:
      array of isolated fragments, defined by the vertices in the fragment
    • fused

      public int[][] fused()
      Construct the sets of vertices which belong to fused ring systems.
      
       IAtomContainer  mol        = ...;
       RingSearch      ringSearch = new RingSearch(mol);
      
       int[][] fused = ringSearch.fused();
       fused.length; // e.g. 3 separate fused ring systems
      
       fused[0].length; // e.g. 6 vertices in the first system
       fused[1].length; // e.g. 10 vertices in the second system
       fused[2].length; // e.g. 4 vertices in the third system
      
       
      Returns:
      array of fused fragments, defined by the vertices in the fragment
    • ringFragments

      public IAtomContainer ringFragments()
      Extract the cyclic atom and bond fragments of the container. Bonds which join two different isolated/fused cycles (e.g. biphenyl) are not be included.
      Returns:
      a new container with only the cyclic atoms and bonds
      See Also:
    • isolatedRingFragments

      public List<IAtomContainer> isolatedRingFragments()
      Construct a list of IAtomContainers each of which only contains a single isolated ring. A ring is consider isolated if it does not share any bonds with another ring. By this definition each ring of a spiro ring system is considered isolated. The atoms are not arranged sequential.
      Returns:
      list of isolated ring fragments
      See Also:
    • fusedRingFragments

      public List<IAtomContainer> fusedRingFragments()
      Construct a list of IAtomContainers which only contain fused rings. A ring is consider fused if it shares any bonds with another ring. By this definition bridged ring systems are also included. The atoms are not arranged sequential.
      Returns:
      list of fused ring fragments
      See Also: