Package org.openscience.cdk.ringsearch

Class 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:
    Cycle (Graph Theory) - Wikipedia, Scaling Up: Faster Ring Detecting in CDK - Efficient Bits, Blog, SpanningTree, SSSRFinder, AllRingsFinder, CyclicVertexSearch
    Source code:
    main
    Belongs to CDK module:
    core

    • Constructor Detail

      • 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 Detail

      • numRings

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

      • 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:
        SpanningTree.getCyclicFragmentsContainer()

      • 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:
        isolated()

      • 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:
        fused()