Package org.openscience.cdk.graph
Class MinimumCycleBasis
- java.lang.Object
-
- org.openscience.cdk.graph.MinimumCycleBasis
-
public final class MinimumCycleBasis extends Object
Compute the minimum cycle basis (MCB) of a graph. A cycle basis is a set of cycles that can be combined to generate all the cycles of a graph. The MCB is the basis of minimum weight (length). As an example, there are three cycles in naphthalene. To generate the three cycles (cycle space) we actually only need two of the three cycles. The third cycle can be generated by combining the other two. Each combination of the two cycles is called a cycle basis. There is one basis with the two rings of size six and two bases with either ring of size six and the perimeter ring of size 10. The weights of each basis are 12 (6+6), 16 (6+10), 16 (6+10). The basis of the two six member rings has minimum weight (12) and is thus the MCB of naphthalene. The Smallest Set of Smallest Rings (SSSR) is normally used interchangeably with MCB although traditionally their meaning was different [Berger, F. et. al.. J. Chem. Inf. Comput. Sci.. 2004. 44]. Although the MCB can be used to generate all other cycles of a graph it may not be unique. A compound with a bridged ring system, such as 3-quinuclidinol, has three equally valid minimum cycle bases. From any two six member rings the third ring can be generated by ⊕-sum (xor-ing) their edges. As there may be more than one MCB it should not be used as a unique descriptor. The smallest (but potentially exponential) unique set of short cycles which generates the cycle space is the union of all minimum cycle bases. This set is known as theRelevantCycles
. The intersect of all minimum cycle bases (EssentialCycles
) is also unique. Although the number ofEssentialCycles
is polynomial it can not always be used to generate the cycle space.- Author:
- John May
- See Also:
RelevantCycles
,SSSRFinder.findSSSR()
, Cycle Basis- Source code:
- main
- Belongs to CDK module:
- core
- Keywords:
- sssr, smallest set of smallest rings, mcb, minimum cycle basis, cycle, ring, ring perception
-
-
Constructor Summary
Constructors Constructor Description MinimumCycleBasis(int[][] graph)
Generate the minimum cycle basis for a graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int[][]
paths()
The paths of all cycles in the minimum cycle basis.int
size()
The number of the cycles in the minimum cycle basis.
-
-
-
Constructor Detail
-
MinimumCycleBasis
public MinimumCycleBasis(int[][] graph)
Generate the minimum cycle basis for a graph.- Parameters:
graph
- undirected adjacency list- See Also:
RingSearch.fused()
,GraphUtil.subgraph(int[][], int[])
-
-