Package org.openscience.cdk.graph
Class Cycles
 java.lang.Object

 org.openscience.cdk.graph.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 toIRing
s. 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 nonuniqueness 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 Summary
All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description static CycleFinder
all()
Create a cycle finder which will compute all simple cycles in a molecule.static CycleFinder
all(int length)
All cycles of smaller than or equal to the specified length.static Cycles
all(IAtomContainer container)
Find all simple cycles in a molecule.static Cycles
all(IAtomContainer container, int length)
All cycles of smaller than or equal to the specified length.static CycleFinder
allOrVertexShort()
Deprecated.useor(org.openscience.cdk.graph.CycleFinder, org.openscience.cdk.graph.CycleFinder)
to define a custom fallbackstatic CycleFinder
cdkAromaticSet()
Create a cycle finder which will compute a set of cycles traditionally used by the CDK to test for aromaticity.static CycleFinder
edgeShort()
Create a cycle finder which will compute the shortest cycles of each vertex in a molecule.static Cycles
edgeShort(IAtomContainer container)
Find the edge short cycles of a molecule.static CycleFinder
essential()
Create a cycle finder which will compute the essential cycles of a molecule.static Cycles
essential(IAtomContainer container)
Find the essential cycles of a molecule.static int
markRingAtomsAndBonds(IAtomContainer mol)
Find and mark all cyclic atoms and bonds in the provided molecule.static int
markRingAtomsAndBonds(IAtomContainer mol, int[][] adjList, GraphUtil.EdgeToBondMap bondMap)
Find and mark all cyclic atoms and bonds in the provided molecule.static CycleFinder
mcb()
Create a cycle finder which will compute the minimum cycle basis (MCB) of a molecule.static Cycles
mcb(IAtomContainer container)
Find the minimum cycle basis (MCB) of a molecule.int
numberOfCycles()
How many cycles are stored.static CycleFinder
or(CycleFinder primary, CycleFinder auxiliary)
Use an auxiliary cycle finder if the primary method was intractable.int[][]
paths()
static CycleFinder
relevant()
Create a cycle finder which will compute the relevant cycle basis (RC) of a molecule.static Cycles
relevant(IAtomContainer container)
Find the relevant cycles of a molecule.static int
smallRingSize(IAtom atom)
Determine the smallest ring size an atom belongs to.static int
smallRingSize(IAtom atom, int max)
Determine the smallest ring size an atom belongs to.static int
smallRingSize(IBond bond)
Determine the smallest ring size an bond belongs to.static int
smallRingSize(IBond bond, int max)
Determine the smallest ring size an bond belongs to.static void
smallRingSizes(IAtomContainer mol, int[] rsizes)
Convenience method to determine the smallest ring size of every atom in the molecule.static Cycles
sssr(IAtomContainer container)
Find the smallest set of smallest rings (SSSR)  aka minimum cycle basis (MCB) of a molecule.IRingSet
toRingSet()
static CycleFinder
tripletShort()
Create a cycle finder which will compute the triplet short cycles of a molecule.static Cycles
tripletShort(IAtomContainer container)
Find the triplet short cycles of a molecule.static CycleFinder
unchorded(CycleFinder original)
Derive a new cycle finder that only provides cycles without a chord.static CycleFinder
vertexShort()
Create a cycle finder which will compute the shortest cycles of each vertex in a molecule.static Cycles
vertexShort(IAtomContainer container)
Find the vertex short cycles of a molecule.



Method Detail

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

paths
public int[][] paths()

toRingSet
public IRingSet toRingSet()
 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 standaloneAllCycles
orAllRingsFinder
. All cycles is every possible simple cycle (i.e. nonrepeating 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 toCycleFinder.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 noncanonical (which in this algorithms case means unique). For finer tuning of options please use theTripletShortCycles
.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 andall()
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.useor(org.openscience.cdk.graph.CycleFinder, org.openscience.cdk.graph.CycleFinder)
to define a custom fallbackFind 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 callsmallRingSize(IAtom, int)
. Parameters:
mol
 the moleculersizes
 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 thatmarkRingAtomsAndBonds(IAtomContainer)
has been called first to set theIAtom.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 atommax
 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 thatmarkRingAtomsAndBonds(IAtomContainer)
has been called first to set theIAtom.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 thatmarkRingAtomsAndBonds(IAtomContainer)
has been called first to set theIBond.isInRing()
status of each atom/bond. Parameters:
bond
 the bondmax
 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 thatmarkRingAtomsAndBonds(IAtomContainer)
has been called first to set theIBond.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)
Find and mark all cyclic atoms and bonds in the provided molecule. Parameters:
mol
 molecule Returns:
 Number of rings found (circuit rank)
 See Also:
IBond.isInRing()
,IAtom.isInRing()
, Circuit Rank

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.
It is possible to nest multiple levels.// all cycles or all cycles size <= 6 CycleFinder cf = Cycles.or(Cycles.all(), Cycles.all(6));
// all cycles or relevant or essential CycleFinder cf = Cycles.or(Cycles.all(), Cycles.or(Cycles.relevant(), Cycles.essential()));
 Parameters:
primary
 primary cycle finding methodauxiliary
 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 standaloneAllCycles
orAllRingsFinder
. All cycles is every possible simple cycle (i.e. nonrepeating 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 containerlength
 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

sssr
public static Cycles sssr(IAtomContainer container)
Find the smallest set of smallest rings (SSSR)  aka minimum cycle basis (MCB) of a molecule.for (IAtomContainer m : ms) { Cycles cycles = Cycles.sssr(m); IRingSet rings = cycles.toRingSet(); }
 Returns:
 cycles belonging to the minimum cycle basis
 See Also:
mcb()
,mcb(org.openscience.cdk.interfaces.IAtomContainer)
,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

