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 exponential
  • EssentialCycles - intersection of all minimum cycle bases
  • MinimumCycleBasis - a minimum cycles basis, may not be unique. Often used interchangeable with the term SSSR.
For maximum performance the algorithm should be run only on ring systems (a biconnected component with at least one tri-connected vertex). An example of this is shown below:
 // 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:
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

    Modifier and Type
    Method
    Description
    boolean
    Did the cycle perception complete - if not the molecule was considered impractical and computation was aborted.
    int[][]
    The paths describing all simple cycles in the given graph.
    int
    Cardinality of the set.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • 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
      PercentMax 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 graph
      maxCycleSize - the maximum cycle size to perceive
      maxDegree - escape clause to stop the algorithm running forever
  • Method Details

    • 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