org.openscience.cdk.ringsearch

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 C_R (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.

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:

master

Belongs to CDK module:

core

Constructor Summary

Constructors

Constructor and Description
RingSearch(IAtomContainer container) Create a new RingSearch for the specified container.
RingSearch(IAtomContainer container, CyclicVertexSearch searcher) Create a new RingSearch for the specified container using the provided search.
RingSearch(IAtomContainer container, int[][] graph) Create a new RingSearch for the specified container and graph.

Method Summary

Modifier and Type	Method and Description
int[]	cyclic() Construct a set of vertices which belong to any cycle (ring).
boolean	cyclic(IAtom atom) Determine whether the provided atom belongs to a ring (is cyclic).
boolean	cyclic(IBond bond) Determine whether the bond is cyclic.
boolean	cyclic(int i) Determine whether the vertex at index i is a cyclic vertex.
boolean	cyclic(int u, int v) Determine whether the edge between the vertices u and v is cyclic.
int[][]	fused() Construct the sets of vertices which belong to fused ring systems.
List<IAtomContainer>	fusedRingFragments() Construct a list of IAtomContainers which only contain fused rings.
int[][]	isolated() Construct the sets of vertices which belong to isolated rings.
List<IAtomContainer>	isolatedRingFragments() Construct a list of IAtomContainers each of which only contains a single isolated ring.
int	numRings() Access the number of rings found (aka.
IAtomContainer	ringFragments() Extract the cyclic atom and bond fragments of the container.

Methods inherited from class java.lang.Object

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

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()