1
/* $Revision: 8201 $ $Author: egonw $ $Date: 2007-04-16 10:40:19 +0200 (Mon, 16 Apr 2007) $
3
* Copyright (C) 2002-2007 Christoph Steinbeck <steinbeck@users.sf.net>
5
* Contact: cdk-devel@lists.sourceforge.net
7
* This program is free software; you can redistribute it and/or
8
* modify it under the terms of the GNU Lesser General Public License
9
* as published by the Free Software Foundation; either version 2.1
10
* of the License, or (at your option) any later version.
11
* All we ask is that proper credit is given for our work, which includes
12
* - but is not limited to - adding the above copyright notice to the beginning
13
* of your source code files, and to any copyright notice that you may distribute
14
* with programs based on this work.
16
* This program is distributed in the hope that it will be useful,
17
* but WITHOUT ANY WARRANTY; without even the implied warranty of
18
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19
* GNU Lesser General Public License for more details.
21
* You should have received a copy of the GNU Lesser General Public License
22
* along with this program; if not, write to the Free Software
23
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
25
package org.openscience.cdk.ringsearch;
27
import org.openscience.cdk.exception.CDKException;
28
import org.openscience.cdk.graph.ConnectivityChecker;
29
import org.openscience.cdk.graph.SpanningTree;
30
import org.openscience.cdk.interfaces.*;
31
import org.openscience.cdk.tools.LoggingTool;
33
import java.util.ArrayList;
34
import java.util.Iterator;
35
import java.util.List;
38
* Finds the Set of all Rings. This is an implementation of the algorithm
39
* published in {@cdk.cite HAN96}. Some of the comments refer to pseudo code
40
* fragments listed in this article. The concept is that a regular molecular
41
* graph is converted into a path graph first, i.e. a graph where the edges are
42
* actually paths, i.e. can list several nodes that are implicitly connecting
43
* the two nodes between the path is formed. The paths that join one endnode
44
* are step by step fused and the joined nodes deleted from the pathgraph. What
45
* remains is a graph of paths that have the same start and endpoint and are
48
* <p><b>WARNING</b>: This class has now a timeout of 5 seconds, after which it aborts
49
* its ringsearch. The timeout value can be customized by the setTimeout()
50
* method of this class.
53
* @cdk.created 2002-06-23
54
* @cdk.module standard
56
public class AllRingsFinder
58
private final LoggingTool logger = new LoggingTool(AllRingsFinder.class);
60
public boolean debug = false;
61
private long timeout = 5000;
62
private long startTime;
65
* used for storing the original atomContainer for
66
* reference purposes (printing)
68
IAtomContainer originalAc = null;
69
List newPaths = new ArrayList();
70
List potentialRings = new ArrayList();
71
List removePaths = new ArrayList();
75
* Returns a ringset containing all rings in the given AtomContainer
77
*@param atomContainer The AtomContainer to be searched for rings
78
*@return A RingSet with all rings in the AtomContainer
79
*@exception CDKException An exception thrown if something goes wrong or if the timeout limit is reached
81
public IRingSet findAllRings(IAtomContainer atomContainer) throws CDKException
83
startTime = System.currentTimeMillis();
84
SpanningTree spanningTree = new SpanningTree(atomContainer);
85
IAtomContainer ringSystems = spanningTree.getCyclicFragmentsContainer();
86
Iterator separateRingSystem = ConnectivityChecker.partitionIntoMolecules(ringSystems).molecules();
87
IRingSet resultSet = atomContainer.getBuilder().newRingSet();
88
while (separateRingSystem.hasNext()) {
89
resultSet.add(findAllRingsInIsolatedRingSystem((IMolecule)separateRingSystem.next()));
96
* Fings the set of all rings in a molecule
98
*@param atomContainer the molecule to be searched for rings
99
*@return a RingSet containing the rings in molecule
100
*@exception CDKException An exception thrown if something goes wrong or if the timeout limit is reached
102
public IRingSet findAllRingsInIsolatedRingSystem(IAtomContainer atomContainer) throws CDKException
104
if (startTime == 0) {
105
startTime = System.currentTimeMillis();
107
List paths = new ArrayList();
108
IRingSet ringSet = atomContainer.getBuilder().newRingSet();
109
IAtomContainer ac = atomContainer.getBuilder().newAtomContainer();
110
originalAc = atomContainer;
111
ac.add(atomContainer);
112
doSearch(ac, paths, ringSet);
118
*@param ac The AtomContainer to be searched
119
*@param paths A vectoring storing all the paths
120
*@param ringSet A ringset to be extended while we search
121
*@exception CDKException An exception thrown if something goes wrong or if the timeout limit is reached
123
private void doSearch(IAtomContainer ac, List paths, IRingSet ringSet) throws CDKException
127
* First we convert the molecular graph into a a path graph by
128
* creating a set of two membered paths from all the bonds in the molecule
130
initPathGraph(ac, paths);
131
logger.debug("BondCount: ", ac.getBondCount());
132
logger.debug("PathCount: ", paths.size());
135
atom = selectAtom(ac);
138
remove(atom, ac, paths, ringSet);
140
} while (paths.size() > 0 && atom != null);
141
logger.debug("paths.size(): ", paths.size());
142
logger.debug("ringSet.size(): ", ringSet.getAtomContainerCount());
147
* Removes all external aliphatic chains by chopping them off from the
150
*@param ac The AtomContainer to work with
151
*@exception CDKException An exception thrown if something goes wrong or if the timeout limit is reached
153
private void removeAliphatic(IAtomContainer ac) throws CDKException
155
boolean removedSomething;
159
removedSomething = false;
160
for (Iterator e = ac.atoms(); e.hasNext(); )
162
atom = (IAtom) e.next();
163
if (ac.getConnectedBondsCount(atom) == 1)
165
ac.removeAtomAndConnectedElectronContainers(atom);
166
removedSomething = true;
169
} while (removedSomething);
174
* Removes an atom from the AtomContainer under certain conditions.
175
* See {@cdk.cite HAN96} for details
178
*@param atom The atom to be removed
179
*@param ac The AtomContainer to work on
180
*@param paths The paths to manipulate
181
*@param rings The ringset to be extended
182
*@exception CDKException Thrown if something goes wrong or if the timeout is exceeded
184
private void remove(IAtom atom, IAtomContainer ac, List paths, IRingSet rings) throws CDKException
189
int intersectionSize;
192
potentialRings.clear();
193
logger.debug("*** Removing atom " + originalAc.getAtomNumber(atom) + " ***");
195
for (int i = 0; i < paths.size(); i++)
197
path1 = (Path) paths.get(i);
198
if (path1.firstElement() == atom || path1.lastElement() == atom)
200
for (int j = i + 1; j < paths.size(); j++)
203
path2 = (Path) paths.get(j);
204
if (path2.firstElement() == atom || path2.lastElement() == atom)
206
intersectionSize = path1.getIntersectionSize(path2);
207
if (intersectionSize < 3)
209
logger.debug("Joining " + path1.toString(originalAc) + " and " + path2.toString(originalAc));
210
union = Path.join(path1, path2, atom);
211
if (intersectionSize == 1)
216
potentialRings.add(union);
218
//logger.debug("Intersection Size: " + intersectionSize);
219
logger.debug("Union: ", union.toString(originalAc));
221
* Now we know that path1 and
222
* path2 share the Atom atom.
224
removePaths.add(path1);
225
removePaths.add(path2);
228
if (timeout > 0) checkTimeout();
232
for (int f = 0; f < removePaths.size(); f++)
234
paths.remove(removePaths.get(f));
236
for (int f = 0; f < newPaths.size(); f++)
238
paths.add(newPaths.get(f));
240
detectRings(potentialRings, rings, originalAc);
241
ac.removeAtomAndConnectedElectronContainers(atom);
242
logger.debug("\n" + paths.size() + " paths and " + ac.getAtomCount() + " atoms left.");
247
* Checks the paths if a ring has been found
249
*@param paths The paths to check for rings
250
*@param ringSet The ringset to add the detected rings to
251
*@param ac The AtomContainer with the original structure
253
private void detectRings(List paths, IRingSet ringSet, IAtomContainer ac)
259
for (int f = 0; f < paths.size(); f++)
261
path = (Path) paths.get(f);
262
if (path.size() > 3 && path.lastElement() == path.firstElement())
264
logger.debug("Removing path " + path.toString(originalAc) + " which is a ring.");
265
path.removeElementAt(0);
266
ring = ac.getBuilder().newRing();
267
for (int g = 0; g < path.size() - 1; g++)
269
a1 = (IAtom) path.elementAt(g);
270
a2 = (IAtom) path.elementAt(g + 1);
272
bondNum = ac.getBondNumber(a1, a2);
273
//logger.debug("bondNum " + bondNum);
274
ring.addBond(ac.getBond(bondNum));
277
a1 = (IAtom) path.elementAt(0);
278
a2 = (IAtom) path.elementAt(path.size()-1);
280
bondNum = ac.getBondNumber(a1, a2);
281
//logger.debug("bondNum " + bondNum);
282
ring.addBond(ac.getBond(bondNum));
285
* The following code had a problem when two atom in the ring
286
* found are connected the in orignal graph but do not belong
287
* to this particular ring.
288
IBond[] bonds = ac.getBonds();
289
for (int g = 0; g < bonds.length; g++)
292
if (ring.contains(bond.getAtom(0)) && ring.contains(bond.getAtom(1)))
297
ringSet.addAtomContainer(ring);
304
* Initialized the path graph
305
* See {@cdk.cite HAN96} for details
307
*@param ac The AtomContainer with the original structure
308
*@param paths The paths to initialize
310
private void initPathGraph(IAtomContainer ac, List paths)
314
Iterator bonds = ac.bonds();
315
while (bonds.hasNext()) {
316
IBond bond = (IBond) bonds.next();
317
path = new Path(bond.getAtom(0), bond.getAtom(1));
319
logger.debug("initPathGraph: " + path.toString(originalAc));
325
* Selects an optimal atom for removal
326
* See {@cdk.cite HAN96} for details
328
*@param ac The AtomContainer to search
329
*@return The selected Atom
331
private IAtom selectAtom(IAtomContainer ac)
336
IAtom minAtom = null;
338
for (int f = 0; f < ac.getAtomCount(); f++)
340
atom = ac.getAtom(f);
341
degree = ac.getConnectedBondsCount(atom);
343
if (degree < minDegree)
355
* Checks if the timeout has been reached and throws an
356
* exception if so. This is used to prevent this AllRingsFinder
357
* to run for ages in certain rare cases with ring systems of
358
* large size or special topology.
360
*@exception CDKException The exception thrown in case of hitting the timeout
362
public void checkTimeout() throws CDKException
364
if (startTime == 0) return;
365
long time = System.currentTimeMillis();
366
if (time - startTime > timeout)
368
throw new CDKException("Timeout for AllringsFinder exceeded");
374
* Sets the timeout value in milliseconds of the AllRingsFinder object
375
* This is used to prevent this AllRingsFinder
376
* to run for ages in certain rare cases with ring systems of
377
* large size or special topology
379
*@param timeout The new timeout value
380
* @return a reference to the instance this method was called for
382
public AllRingsFinder setTimeout(long timeout)
384
this.timeout = timeout;
390
* Gets the timeout values in milliseconds of the AllRingsFinder object
392
*@return The timeout value
394
public long getTimeout()
added
removed
src/org/openscience/cdk/ringsearch/AllRingsFinder.java
