org.openscience.cdk.graph

Class RelevantCycles

java.lang.Object

org.openscience.cdk.graph.RelevantCycles

public final class RelevantCycles
extends Object

Compute the relevant cycles (C_R) 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:

master

Belongs to CDK module:

core

Keywords:

relevant cycles, relevant rings, R(G), union of all minimum cycles bases, cycle, ring, ring perception

Constructor Summary

Constructors

Constructor and Description
RelevantCycles(int[][] graph) Generate the relevant cycle basis for a graph.

Method Summary

Modifier and Type	Method and Description
int[][]	paths() Reconstruct the paths of all relevant cycles.
int	size() The number of the relevant cycles.

Methods inherited from class java.lang.Object

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

Constructor Detail

RelevantCycles

public RelevantCycles(int[][] graph)

Generate the relevant cycle basis for a graph.

Parameters:

graph - undirected adjacency list

See Also:

RingSearch.fused(), GraphUtil.subgraph(int[][], int[])

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