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

master

Belongs to CDK module:

core

Constructor Summary

Constructors

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

Method Summary

Methods

Modifier and Type	Method and 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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