** [patches:#634] Ring Perception Pt 2**

**Status:** open

**Labels:** cycles rings relevant

**Created:** Sat May 11, 2013 04:42 PM UTC by John May

**Last Updated:** Sat May 11, 2013 04:42 PM UTC

**Owner:** nobody

Implementation of Vismara's 97 algorithm to find the relevant cycles in a graph. This is the union of all minimum cycle bases and is the smallest unique set of the cycles in a graph. The algorithm is much faster then the existing (SSSRFinder.findRelevantRings) and is intended to fit together with the new RingSearch. I also added a MinimumCycleBasis (SSSRFinder.findSSRR) which is also faster but not as much. Both of these use an intermediate (InitialCycles, describes in Vismara 97) which is quick to compute and can be used by both the RelevantRings and MinimumCycleBasis. Unfortunately one of the slowest steps is still getting from the IAtomContainer to the graph and back.

Code is on this branch (bd2af30083 onwards): https://github.com/johnmay/cdk/tree/ncycles

I wasn't sure which packages to put it. There's lots of package-private class as these are more tools to build other algorithms with then a tool in their own right. It needs the ShortestPaths so I put it in graph and module core, but could go elsewhere.

I've verified the output of RelevantRings against the existing implementation on ~46,000,000 structures from PubChem-Compound and found no mistakes. Unfortunately the output is close to a GB but I've attached the first ~2,000,000, not that it shows anything useful. The MCB is harder to verify as it is not unique and I could only verify the size of the MCB rather then actual paths.

Will also likely add the essential cycles and all cycles (rings) so all the ring code fits well together.

Sent from sourceforge.net because you indicated interest in https://sourceforge.net/p/cdk/patches/634/

To unsubscribe from further messages, please visit https://sourceforge.net/auth/subscriptions/