Package org.openscience.cdk.graph
Class AllCycles
 java.lang.Object

 org.openscience.cdk.graph.AllCycles

public final class AllCycles extends Object
Compute all simple cycles (rings) in a graph. Generally speaking one does not need all the cycles and tractable subsets offer good alternatives. EdgeShortCycles  the smallest cycle through each edge
RelevantCycles
 union of all minimum cycle bases  unique but may be exponentialEssentialCycles
 intersection of all minimum cycle basesMinimumCycleBasis
 a minimum cycles basis, may not be unique. Often used interchangeable with the term SSSR.
// convert the molecule to adjacency list  may be redundant in future IAtomContainer m =...; int[][] g = GraphUtil.toAdjList(m); // efficient computation/partitioning of the ring systems RingSearch rs = new RingSearch(m, g); // isolated cycles don't need to be run rs.isolated(); // process fused systems separately for (int[] fused : rs.fused()) { // given the fused subgraph, max cycle size is // the number of vertices AllCycles ac = new AllCycles(subgraph(g, fused), fused.length, maxDegree); // cyclic walks int[][] paths = ac.paths(); }
 Author:
 John May
 See Also:
RegularPathGraph
,JumboPathGraph
,RingSearch
,GraphUtil
, Performance Analysis (Blog Post) Source code:
 main
 Belongs to CDK module:
 core


Constructor Summary
Constructors Constructor Description AllCycles(int[][] graph, int maxCycleSize, int maxDegree)
Compute all simple cycles up to given maxCycleSize in the provided graph.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
completed()
Did the cycle perception complete  if not the molecule was considered impractical and computation was aborted.int[][]
paths()
The paths describing all simple cycles in the given graph.int
size()
Cardinality of the set.



Constructor Detail

AllCycles
public AllCycles(int[][] graph, int maxCycleSize, int maxDegree)
Compute all simple cycles up to given maxCycleSize in the provided graph. In some graphs the topology makes it impracticable to compute all the simple. To avoid running forever on these molecules the maxDegree provides an escape clause. The value doesn't quantify how many cycles we get. The percentage of molecules in PubChem Compound (Dec '12) which would successfully complete for a given degree are listed below.Table 1. Num of structures processable in PubChem Compound (Dec 2012) as a result of setting the max degree Percent Max Degree 99% 9 99.95% 72 99.96% 84 99.97% 126 99.98% 216 99.99% 684  Parameters:
graph
 adjacency list representation of a graphmaxCycleSize
 the maximum cycle size to perceivemaxDegree
 escape clause to stop the algorithm running forever


Method Detail

paths
public int[][] paths()
The paths describing all simple cycles in the given graph. The path stats and ends vertex. Returns:
 2d array of paths

size
public int size()
Cardinality of the set. Returns:
 number of cycles

completed
public boolean completed()
Did the cycle perception complete  if not the molecule was considered impractical and computation was aborted. Returns:
 algorithm completed

