Package org.openscience.cdk.graph

Class Cycles

  • public final class Cycles
extends Object
    A utility class for storing and computing the cycles of a chemical graph. Utilities are also provided for converting the cycles to IRings. A brief description of each cycle set is given below - for a more comprehensive review please see - [Berger, F. et. al.. J. Chem. Inf. Comput. Sci.. 2004. 44].
    • all() - all simple cycles in the graph, the number of cycles generated may be very large and may not be feasible for some molecules, such as, fullerene.
    • mcb() (aka. SSSR) - minimum cycle basis (MCB) of a graph, these cycles are linearly independent and can be used to generate all of cycles in the graph. It is important to note the MCB is not unique and a that there may be multiple equally valid MCBs. The smallest set of smallest rings (SSSR) is often used to refer to the MCB but originally SSSR was defined as a strictly fundamental cycle basis [Berger, F. et. al.. J. Chem. Inf. Comput. Sci.. 2004. 44]. Not every graph has a strictly fundamental cycle basis the definition has come to mean the MCB. Due to the non-uniqueness of the MCB/SSSR its use is discouraged.
    • relevant() - relevant cycles of a graph, the smallest set of uniquely defined short cycles. If a graph has a single MCB then the relevant cycles and MCB are the same. If the graph has multiple MCB then the relevant cycles is the union of all MCBs. The number of relevant cycles may be exponential but it is possible to determine how many relevant cycles there are in polynomial time without generating them. For chemical graphs the number of relevant cycles is usually within manageable bounds.
    • essential() - essential cycles of a graph. Similar to the relevant cycles the set is unique for a graph. If a graph has a single MCB then the essential cycles and MCB are the same. If the graph has multiple MCB then the essential cycles is the intersect of all MCBs. That is the cycles which appear in every MCB. This means that is is possible to have no essential cycles in a molecule which clearly has cycles (e.g. bridged system like bicyclo[2.2.2]octane).
    • tripletShort() - the triple short cycles are the shortest cycle through each triple of vertices. This allows one to generate the envelope rings of some molecules (e.g. naphthalene) without generating all cycles. The cycles are primarily useful for the CACTVS Substructure Keys (PubChem fingerprint).
    • vertexShort() - the shortest cycles through each vertex. Unlike the MCB, linear independence is not checked and it may not be possible to generate all other cycles from this set. In practice the vertex/edge short cycles are similar to MCB.
    • edgeShort() - the shortest cycles through each edge. Unlike the MCB, linear independence is not checked and it may not be possible to generate all other cycles from this set. In practice the vertex/edge short cycles are similar to MCB.
    Author:
    John May
    Source code:
    main
    Belongs to CDK module:
    core

    • Method Detail

      • numberOfCycles

        public int numberOfCycles()
        How many cycles are stored.
        Returns:
        number of cycles

      • paths

        public int[][] paths()

      • toRingSet

        public IRingSet toRingSet()
        Convert the cycles to a IRingSet containing the IAtoms and IBonds of the input molecule.
        Returns:
        ringset for the cycles

      • all

        public static CycleFinder all()
        Create a cycle finder which will compute all simple cycles in a molecule. The threshold values can not be tuned and is set at a value which will complete in reasonable time for most molecules. To change the threshold values please use the stand-alone AllCycles or AllRingsFinder. All cycles is every possible simple cycle (i.e. non-repeating vertices) in the chemical graph. As an example - all simple cycles of anthracene includes, 3 cycles of length 6, 2 of length 10 and 1 of length 14. 
         CycleFinder cf = Cycles.all();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // handle error - note it is common that finding all simple
         // cycles in chemical graphs is intractable
     }
 }
        Returns:
        finder for all simple cycles
        See Also:
        all(org.openscience.cdk.interfaces.IAtomContainer), AllCycles, AllRingsFinder

      • all

        public static CycleFinder all​(int length)
        All cycles of smaller than or equal to the specified length. If a length is also provided to CycleFinder.find(IAtomContainer, int) the minimum of the two limits is used.
        Parameters:
        length - maximum size or cycle to find
        Returns:
        cycle finder

      • mcb

        public static CycleFinder mcb()
        Create a cycle finder which will compute the minimum cycle basis (MCB) of a molecule. 
         CycleFinder cf = Cycles.mcb();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - MCB should never be intractable
     }
 }
        Returns:
        finder for all simple cycles
        See Also:
        mcb(org.openscience.cdk.interfaces.IAtomContainer), MinimumCycleBasis

      • relevant

        public static CycleFinder relevant()
        Create a cycle finder which will compute the relevant cycle basis (RC) of a molecule. 
         CycleFinder cf = Cycles.relevant();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - there may be an exponential number of cycles
         // but this is not currently checked
     }
 }
        Returns:
        finder for relevant cycles
        See Also:
        relevant(org.openscience.cdk.interfaces.IAtomContainer), RelevantCycles

      • essential

        public static CycleFinder essential()
        Create a cycle finder which will compute the essential cycles of a molecule. 
         CycleFinder cf = Cycles.essential();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - essential cycles do not check tractability
     }
 }
        Returns:
        finder for essential cycles
        See Also:
        relevant(org.openscience.cdk.interfaces.IAtomContainer), RelevantCycles

      • tripletShort

        public static CycleFinder tripletShort()
        Create a cycle finder which will compute the triplet short cycles of a molecule. These cycles are the shortest through each triplet of vertices are utilised in the generation of CACTVS Substructure Keys (PubChem Fingerprint). Currently the triplet cycles are non-canonical (which in this algorithms case means unique). For finer tuning of options please use the TripletShortCycles. 
         CycleFinder cf = Cycles.tripletShort();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - triple short cycles do not check tractability
     }
 }
        Returns:
        finder for triplet short cycles
        See Also:
        tripletShort(org.openscience.cdk.interfaces.IAtomContainer), TripletShortCycles

      • vertexShort

        public static CycleFinder vertexShort()
        Create a cycle finder which will compute the shortest cycles of each vertex in a molecule. Unlike the SSSR/MCB computation linear independence is not required and provides some performance gain. In practise typical chemical graphs are small and the linear independence check is relatively fast. 
         CycleFinder cf = Cycles.vertexShort();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - vertex short cycles do not check tractability
     }
 }
        Returns:
        finder for vertex short cycles
        See Also:
        vertexShort(org.openscience.cdk.interfaces.IAtomContainer)

      • edgeShort

        public static CycleFinder edgeShort()
        Create a cycle finder which will compute the shortest cycles of each vertex in a molecule. Unlike the SSSR/MCB computation linear independence is not required and provides some performance gain. In practise typical chemical graphs are small and the linear independence check is relatively fast. 
         CycleFinder cf = Cycles.edgeShort();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - edge short cycles do not check tractability
     }
 }
        Returns:
        finder for edge short cycles
        See Also:
        edgeShort(org.openscience.cdk.interfaces.IAtomContainer)

      • cdkAromaticSet

        public static CycleFinder cdkAromaticSet()
        Create a cycle finder which will compute a set of cycles traditionally used by the CDK to test for aromaticity. This set of cycles is the MCB/SSSR and all() cycles for fused systems with 3 or less rings. This allows on to test aromaticity of envelope rings in compounds such as azulene without generating an huge number of cycles for large fused systems (e.g. fullerenes). The use case was that computation of all cycles previously took a long time and ring systems with more than 2 rings were too difficult. However it is now more efficient to simply check all cycles/rings without using the MCB/SSSR. This computation will fail for complex fused systems but the failure is fast and one can easily 'fall back' to a smaller set of cycles after catching the exception. 
         CycleFinder cf = Cycles.cdkAromaticSet();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - edge short cycles do not check tractability
     }
 }
        Returns:
        finder for cdk aromatic cycles
        See Also:
        edgeShort(org.openscience.cdk.interfaces.IAtomContainer)

      • allOrVertexShort

        @Deprecated
public static CycleFinder allOrVertexShort()
        Deprecated.
        use or(org.openscience.cdk.graph.CycleFinder, org.openscience.cdk.graph.CycleFinder) to define a custom fall-back
        Find all cycles in a fused system or if there were too many cycles fallback and use the shortest cycles through each vertex. Typically the types of molecules which the vertex short cycles are provided for are fullerenes. This cycle finder is well suited to aromaticity. 
         CycleFinder cf = Cycles.allOrVertexShort();
 for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = cf.find(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // ignore error - edge short cycles do not check tractability
     }
 }
        Returns:
        a cycle finder which computes all cycles if possible or provides the vertex short cycles

      • smallRingSizes

        public static void smallRingSizes​(IAtomContainer mol,
                                  int[] rsizes)
        Convenience method to determine the smallest ring size of every atom in the molecule. For each atom index the smallest ring size is set in the array, if 0 the atom is acyclic. If you just need to check a single atom is more efficient to call smallRingSize(IAtom, int).
        Parameters:
        mol - the molecule
        rsizes - the array to be filled
        See Also:
        smallRingSize(IAtom, int)

      • smallRingSize

        public static int smallRingSize​(IAtom atom,
                                int max)
        Determine the smallest ring size an atom belongs to. This method requires that markRingAtomsAndBonds(IAtomContainer) has been called first to set the IAtom.isInRing() status of each atom/bond. If you need to check every atom in a molecule use {@link @see #smallRingSizes(IAtomContainer, int[])}.
        Parameters:
        atom - the atom
        max - the max ring size
        Returns:
        the ring size, or 0 if the atom is not in a ring or is in a ring larger than 'max'
        See Also:
        smallRingSizes(IAtomContainer, int[])

      • smallRingSize

        public static int smallRingSize​(IAtom atom)
        Determine the smallest ring size an atom belongs to. This method requires that markRingAtomsAndBonds(IAtomContainer) has been called first to set the IAtom.isInRing() status of each atom/bond. If you need to check every atom in a molecule use {@link @see #smallRingSizes(IAtomContainer, int[])}.
        Parameters:
        atom - the atom
        Returns:
        the ring size, or 0 if the atom is not in a ring
        See Also:
        smallRingSizes(IAtomContainer, int[])

      • smallRingSize

        public static int smallRingSize​(IBond bond,
                                int max)
        Determine the smallest ring size an bond belongs to. This method requires that markRingAtomsAndBonds(IAtomContainer) has been called first to set the IBond.isInRing() status of each atom/bond.
        Parameters:
        bond - the bond
        max - the max ring size
        Returns:
        the ring size, or 0 if the bond is not in a ring or is in a ring larger than 'max'

      • smallRingSize

        public static int smallRingSize​(IBond bond)
        Determine the smallest ring size an bond belongs to. This method requires that markRingAtomsAndBonds(IAtomContainer) has been called first to set the IBond.isInRing() status of each atom/bond.
        Parameters:
        bond - the bond
        Returns:
        the ring size, or 0 if the bond is not in a ring or is in a ring larger than 'max'

      • markRingAtomsAndBonds

        public static int markRingAtomsAndBonds​(IAtomContainer mol,
                                        int[][] adjList,
                                        GraphUtil.EdgeToBondMap bondMap)
        Find and mark all cyclic atoms and bonds in the provided molecule. This optimised version allows the caller to optionally provided indexed fast access structure which would otherwise be created.
        Parameters:
        mol - molecule
        Returns:
        Number of rings found (circuit rank)
        See Also:
        IBond.isInRing(), IAtom.isInRing(), Circuit Rank

      • or

        public static CycleFinder or​(CycleFinder primary,
                             CycleFinder auxiliary)
        Use an auxiliary cycle finder if the primary method was intractable. 
        
 // all cycles or all cycles size <= 6
 CycleFinder cf = Cycles.or(Cycles.all(), Cycles.all(6));
        It is possible to nest multiple levels. 
         // all cycles or relevant or essential
 CycleFinder cf = Cycles.or(Cycles.all(),
                            Cycles.or(Cycles.relevant(),
                                      Cycles.essential()));
        Parameters:
        primary - primary cycle finding method
        auxiliary - auxiliary cycle finding method if the primary failed
        Returns:
        a new cycle finder

      • all

        public static Cycles all​(IAtomContainer container)
                  throws Intractable
        Find all simple cycles in a molecule. The threshold values can not be tuned and is set at a value which will complete in reasonable time for most molecules. To change the threshold values please use the stand-alone AllCycles or AllRingsFinder. All cycles is every possible simple cycle (i.e. non-repeating vertices) in the chemical graph. As an example - all simple cycles of anthracene includes, 3 cycles of length 6, 2 of length 10 and 1 of length 14. 
         for (IAtomContainer m : ms) {
     try {
         Cycles   cycles = Cycles.all(m);
         IRingSet rings  = cycles.toRingSet();
     } catch (Intractable e) {
         // handle error - note it is common that finding all simple
         // cycles in chemical graphs is intractable
     }
 }
        Returns:
        all simple cycles
        Throws:
        Intractable - the algorithm reached a limit which caused it to abort in reasonable time
        See Also:
        all(), AllCycles, AllRingsFinder

      • all

        public static Cycles all​(IAtomContainer container,
                         int length)
                  throws Intractable
        All cycles of smaller than or equal to the specified length.
        Parameters:
        container - input container
        length - maximum size or cycle to find
        Returns:
        all cycles
        Throws:
        Intractable - computation was not feasible

      • mcb

        public static Cycles mcb​(IAtomContainer container)
        Find the minimum cycle basis (MCB) of a molecule. 
         for (IAtomContainer m : ms) {
     Cycles   cycles = Cycles.mcb(m);
     IRingSet rings  = cycles.toRingSet();
 }
        Returns:
        cycles belonging to the minimum cycle basis
        See Also:
        mcb(), MinimumCycleBasis

      • relevant

        public static Cycles relevant​(IAtomContainer container)
        Find the relevant cycles of a molecule. 
         for (IAtomContainer m : ms) {
     Cycles   cycles = Cycles.relevant(m);
     IRingSet rings  = cycles.toRingSet();
 }
        Returns:
        relevant cycles
        See Also:
        relevant(), RelevantCycles

      • essential

        public static Cycles essential​(IAtomContainer container)
        Find the essential cycles of a molecule. 
         for (IAtomContainer m : ms) {
     Cycles   cycles = Cycles.essential(m);
     IRingSet rings  = cycles.toRingSet();
 }
        Returns:
        essential cycles
        See Also:
        relevant(), RelevantCycles

      • tripletShort

        public static Cycles tripletShort​(IAtomContainer container)
        Find the triplet short cycles of a molecule. 
         for (IAtomContainer m : ms) {
     Cycles   cycles = Cycles.tripletShort(m);
     IRingSet rings  = cycles.toRingSet();
 }
        Returns:
        triplet short cycles
        See Also:
        tripletShort(), TripletShortCycles

      • vertexShort

        public static Cycles vertexShort​(IAtomContainer container)
        Find the vertex short cycles of a molecule. 
         for (IAtomContainer m : ms) {
     Cycles   cycles = Cycles.vertexShort(m);
     IRingSet rings  = cycles.toRingSet();
 }
        Returns:
        triplet short cycles
        See Also:
        vertexShort(), VertexShortCycles

      • edgeShort

        public static Cycles edgeShort​(IAtomContainer container)
        Find the edge short cycles of a molecule. 
         for (IAtomContainer m : ms) {
     Cycles   cycles = Cycles.edgeShort(m);
     IRingSet rings  = cycles.toRingSet();
 }
        Returns:
        edge short cycles
        See Also:
        edgeShort(), EdgeShortCycles

      • unchorded

        public static CycleFinder unchorded​(CycleFinder original)
        Derive a new cycle finder that only provides cycles without a chord.
        Parameters:
        original - find the initial cycles before filtering
        Returns:
        cycles or the original without chords