Package org.openscience.cdk.graph

Class RelevantCycles

java.lang.Object
org.openscience.cdk.graph.RelevantCycles
public final class RelevantCycles extends Object
Compute the relevant cycles (CR) of a graph. A cycle is relevant if it cannot be represented as the ⊕-sum (xor) of strictly shorter cycles [Berger, F. et. al.. J. Chem. Inf. Comput. Sci.. 2004. 44]. This is the smallest set of short cycles which is uniquely defined for a graph. The set can also be thought of as the union of all minimum cycle bases. The set of cycles may be exponential in number but can be checked (see size()) before construction [Vismara, Philippe. Combinatorics. 1997. 4]. 

 // import static org.openscience.cdk.graph.GraphUtil.*;
 IAtomContainer m = ...;

 // compute on the whole graph
 RelevantCycles relevant = new RelevantCycles(toAdjList(m));

 // it is much faster to compute on the separate ring systems of the molecule
 int[][]    graph      = toAdjList(m);
 RingSearch ringSearch = new RingSearch(m, graph);

 // all isolated cycles are relevant
 for (int[] isolated : ringSearch.isolated()){
     int[] path = cycle(graph, isolated);
 }

 // compute the relevant cycles for each system
 for (int[] fused : ringSearch.fused()){

     int[][] subgraph = subgraph(graph, fused);
     RelevantCycles relevant = new RelevantCycles(subgraph);

     for(int[] path : relevant.paths()){
         // convert the sub graph vertices back to the super graph indices
         for(int i = 0; i < path.length; i++) {
             path[i] = fused[path[i];
         }
     }
 }
Author:
John May
See Also:
Source code:
main
Belongs to CDK module:
core
Keywords:
relevant cycles, relevant rings, R(G), union of all minimum cycles bases, cycle, ring, ring perception

  • Constructor Details

  • Method Details

    • paths

      public int[][] paths()
      Reconstruct the paths of all relevant cycles. 
      
 RelevantCycles relevant = ...

 // ensure the number is manageable
 if(relevant.size() < 100){
   for(int[] path : relevant.paths()){
     // process the path
   }
 }
      Returns:
      array of vertex paths

    • size

      public int size()
      The number of the relevant cycles.
      Returns:
      size of relevant cycle set