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];
    John May
    See Also:
    RingSearch, SSSRFinder.findRelevantRings(), GreedyBasis
    Source code:
    Belongs to CDK module:
    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
        array of vertex paths
      • size

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