Package 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.
 Two separate isolated cycles
 Two separate fused cycle systems. The bridged systems are fused but separate from each other
 Fused rings  a single fused cycle system
 Spiro rings  three separate isolated systems, no bonds are shared
 Cyclophane  a single fused system, the perimeter rings share bonds with the smaller rings
 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 Summary
Constructors Constructor Description RingSearch(IAtomContainer container)
Create a new RingSearch for the specified container.RingSearch(IAtomContainer container, int[][] graph)
Create a new RingSearch for the specified container and graph.RingSearch(IAtomContainer container, CyclicVertexSearch searcher)
Create a new RingSearch for the specified container using the provided search.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int[]
cyclic()
Construct a set of vertices which belong to any cycle (ring).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.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.int[][]
fused()
Construct the sets of vertices which belong to fused ring systems.List<IAtomContainer>
fusedRingFragments()
Construct a list ofIAtomContainer
s which only contain fused rings.int[][]
isolated()
Construct the sets of vertices which belong to isolated rings.List<IAtomContainer>
isolatedRingFragments()
Construct a list ofIAtomContainer
s 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.



Constructor Detail

RingSearch
public RingSearch(IAtomContainer container)
Create a new RingSearch for the specified container. Parameters:
container
 nonnull input structure Throws:
NullPointerException
 if the container was nullIllegalArgumentException
 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
 nonnull input structuregraph
 nonnull 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
 nonnull input structuresearcher
 nonnull 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 edgev
 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 lookup 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 ofIAtomContainer
s 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 ofIAtomContainer
s 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()

