Class 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
     // 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),
        // cyclic walks
        int[][] paths = ac.paths();
    John May
    See Also:
    RegularPathGraph, JumboPathGraph, RingSearch, GraphUtil, Performance Analysis (Blog Post)
    Source code:
    Belongs to CDK module:
    • 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
        PercentMax Degree
        graph - adjacency list representation of a graph
        maxCycleSize - the maximum cycle size to perceive
        maxDegree - 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.
        2d array of paths
      • size

        public int size()
        Cardinality of the set.
        number of cycles
      • completed

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