Package org.openscience.cdk.graph
Class RelevantCycles
java.lang.Object
org.openscience.cdk.graph.RelevantCycles
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
-
Constructor Summary
ConstructorsConstructorDescriptionRelevantCycles
(int[][] graph) Generate the relevant cycle basis for a graph. -
Method Summary
-
Constructor Details
-
RelevantCycles
public RelevantCycles(int[][] graph) Generate the relevant cycle basis for a graph.- Parameters:
graph
- undirected adjacency list- See Also:
-
-
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
-