public final class AllCycles extends Object
RelevantCycles
- union of all minimum cycle bases - unique but
may be exponentialEssentialCycles
- intersection of all
minimum cycle bases MinimumCycleBasis
- a minimum cycles
basis, may not be unique. Often used interchangeable with the term SSSR.// 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(); }
RegularPathGraph
,
JumboPathGraph
,
RingSearch
,
GraphUtil
,
Performance
Analysis (Blog Post)Constructor and Description |
---|
AllCycles(int[][] graph,
int maxCycleSize,
int maxDegree)
Compute all simple cycles up to given maxCycleSize in the provided
graph.
|
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.
|
public AllCycles(int[][] graph, int maxCycleSize, int maxDegree)
Percent | Max Degree |
---|---|
99% | 9 |
99.95% | 72 |
99.96% | 84 |
99.97% | 126 |
99.98% | 216 |
99.99% | 684 |
graph
- adjacency list representation of a graphmaxCycleSize
- the maximum cycle size to perceivemaxDegree
- escape clause to stop the algorithm running foreverpublic int[][] paths()
public int size()
public boolean completed()
Copyright © 2021. All rights reserved.