Package org.openscience.cdk.graph

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
 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 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
        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 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