Package org.openscience.cdk.graph

Class 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:
    RingSearch, SSSRFinder.findRelevantRings(), GreedyBasis
    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

    • Method Detail

      • 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