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 to IRings. A brief description of each cycle set is given below - for a more comprehensive review please see - [Berger, F. and Flamm, C and Gleiss, P and Leydold, J and Stadler, P, Counterexamples in Chemical Ring Perception, J. Chem. Inf. Comput. Sci., 2004, 44:323-331].

• 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. and Flamm, C and Gleiss, P and Leydold, J and Stadler, P, Counterexamples in Chemical Ring Perception, J. Chem. Inf. Comput. Sci., 2004, 44:323-331]. 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:

master

Belongs to CDK module:

core

Method Summary

Methods

Modifier and Type	Method and Description
static CycleFinder	all() Create a cycle finder which will compute all simple cycles in a molecule.
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	all(int length) All cycles of smaller than or equal to the specified length.
static CycleFinder	allOrVertexShort() Deprecated. use or(org.openscience.cdk.graph.CycleFinder, org.openscience.cdk.graph.CycleFinder) to define a custom fall-back
static 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 Cycles	sssr(IAtomContainer container) Find the smallest set of smallest rings (SSSR) - aka minimum cycle basis (MCB) of a molecule.
IRingSet	toRingSet() Convert the cycles to a IRingSet containing the IAtoms and IBonds of the input molecule.
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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

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.

// 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

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