1
/* $Revision: 8163 $ $Author: rajarshi $ $Date: 2007-04-04 23:46:28 +0200 (Wed, 04 Apr 2007) $
3
* Copyright (C) 2001-2007 Nina Jeliazkova
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.graph;
27
import org.openscience.cdk.CDKConstants;
28
import org.openscience.cdk.exception.NoSuchAtomException;
29
import org.openscience.cdk.interfaces.*;
31
import java.util.Iterator;
34
* Spanning tree of a molecule.
35
* Used to discover the number of cyclic bonds in order to prevent the
36
* inefficient AllRingsFinder to run for too long.
38
* @author Nina Jeliazkova
39
* @cdk.module standard
40
* @cdk.dictref blue-obelisk:graphSpanningTree
41
* @cdk.keyword spanning tree
42
* @cdk.keyword ring finding
44
public class SpanningTree {
46
private final static String ATOM_NUMBER = "ST_ATOMNO";
48
private int[] parent = null;
49
private int[][] cb = null; // what is cb??? cyclic bonds?
51
protected boolean[] bondsInTree;
53
private int sptSize = 0;
54
private int edrSize = 0;
56
private int bondsAcyclicCount = 0,bondsCyclicCount = 0;
58
private IAtomContainer molecule = null;
59
private int totalEdgeCount=0, totalVertexCount=0;
60
private boolean disconnected;
61
private boolean identifiedBonds;
63
public boolean isDisconnected() {
67
public SpanningTree(IAtomContainer atomContainer) {
68
identifiedBonds = false;
69
buildSpanningTree(atomContainer);
78
bondsAcyclicCount = 0;
86
private boolean fastfind(int v1,int v2, boolean union) {
87
int i = v1; while (parent[i] > 0) i = parent[i];
88
int j = v2; while (parent[j] > 0) j = parent[j];
90
while (parent[v1] > 0) {
91
t = v1; v1 = parent[v1]; parent[t] = i;
93
while (parent[v2] > 0) {
94
t = v2; v2 = parent[v2]; parent[t] = j;
96
if (union && (i!=j)) {
97
if (parent[j] < parent[i]) {
98
parent[j] = parent[j] + parent[i]-1;
101
parent[i] = parent[i] + parent[j]-1;
108
private void fastFindInit(int V) {
109
parent = new int[V+1];
110
for (int i = 1; i <= V; i++) {
117
* @param atomContainer
119
private void buildSpanningTree(IAtomContainer atomContainer){
120
disconnected = false;
121
molecule = atomContainer;
123
totalVertexCount = atomContainer.getAtomCount();
124
totalEdgeCount = atomContainer.getBondCount();
126
sptSize = 0;edrSize = 0;
127
fastFindInit(totalVertexCount);
128
for (int i = 0; i < totalVertexCount; i++) {
129
(atomContainer.getAtom(i)).setProperty(ATOM_NUMBER, Integer.toString(i+1));
133
bondsInTree = new boolean[totalEdgeCount];
135
for (int b=0; b < totalEdgeCount; b++ ) {
136
bondsInTree[b] = false;
137
bond = atomContainer.getBond(b);
138
v1 = Integer.parseInt((bond.getAtom(0)).getProperty(ATOM_NUMBER).toString());
139
v2 = Integer.parseInt((bond.getAtom(1)).getProperty(ATOM_NUMBER).toString());
140
//this below is a little bit slower
141
//v1 = atomContainer.getAtomNumber(bond.getAtomAt(0))+1;
142
//v2 = atomContainer.getAtomNumber(bond.getAtomAt(1))+1;
143
if (fastfind(v1,v2,true)) {
144
bondsInTree[b] = true;
146
//logger.debug("ST : includes bond between atoms "+v1+","+v2);
148
if (sptSize>=(totalVertexCount-1)) break;
151
// if atomcontainer is connected then the number of bonds in the spanning tree = (No atoms-1)
152
//i.e. edgesRings = new Bond[E-V+1];
153
//but to hold all bonds if atomContainer was disconnected then edgesRings = new Bond[E-sptSize];
154
if (sptSize != (totalVertexCount-1)) disconnected = true;
155
for (int b=0; b < totalEdgeCount; b++ ) if (!bondsInTree[b]){
156
// edgesRings[edrSize] = atomContainer.getBondAt(b);
159
cb = new int[edrSize][totalEdgeCount];
160
for (int i = 0; i < edrSize; i++)
161
for (int a = 0; a < totalEdgeCount; a++)
164
// remove ATOM_NUMBER props again
165
Iterator atoms = atomContainer.atoms();
166
while (atoms.hasNext()) ((IAtom)atoms.next()).removeProperty(ATOM_NUMBER);
169
public IAtomContainer getSpanningTree() {
170
IAtomContainer ac = molecule.getBuilder().newAtomContainer();
171
for (int a=0 ; a < totalVertexCount; a++) ac.addAtom(molecule.getAtom(a));
172
for (int b=0; b < totalEdgeCount; b++ ) if (bondsInTree[b])
173
ac.addBond(molecule.getBond(b));
177
public static void resetFlags(IAtomContainer ac) {
178
for (int f = 0; f < ac.getAtomCount(); f++) {
179
ac.getAtom(f).setFlag(CDKConstants.VISITED, false);
181
for (int f = 0; f < ac.getElectronContainerCount(); f++) {
182
ac.getElectronContainer(f).setFlag(CDKConstants.VISITED, false);
186
public IAtomContainer getPath(IAtomContainer spt,IAtom a1, IAtom a2) throws NoSuchAtomException {
187
IAtomContainer path = spt.getBuilder().newAtomContainer();
188
PathTools.resetFlags(spt);
190
PathTools.depthFirstTargetSearch(spt,a1,a2,path);
194
private IRing getRing(IAtomContainer spt, IBond bond) throws NoSuchAtomException {
195
IRing ring = spt.getBuilder().newRing();
196
PathTools.resetFlags(spt);
197
ring.addAtom(bond.getAtom(0));
198
PathTools.depthFirstTargetSearch(spt,bond.getAtom(0),bond.getAtom(1),ring);
203
private void getBondsInRing(IAtomContainer mol, IRing ring, int[] bonds) {
204
for (int i=0; i < ring.getBondCount(); i++ ) {
205
int m = mol.getBondNumber(ring.getBond(i));
210
public IRingSet getBasicRings() throws NoSuchAtomException {
211
IRingSet ringset = molecule.getBuilder().newRingSet();
212
IAtomContainer spt = getSpanningTree();
213
for (int i = 0; i < totalEdgeCount; i++) if (!bondsInTree[i])
214
ringset.addAtomContainer(getRing(spt,molecule.getBond(i)));
220
* Returns an IAtomContainer which contains all the atoms and bonds which
221
* are involved in ring systems.
223
* @throws NoSuchAtomException
226
* @see getBasicRings()
228
public IAtomContainer getCyclicFragmentsContainer() throws NoSuchAtomException {
229
IAtomContainer fragContainer = this.molecule.getBuilder().newAtomContainer();
230
IAtomContainer spt = getSpanningTree();
232
for (int i = 0; i < totalEdgeCount; i++)
233
if (!bondsInTree[i]) {
234
IRing ring = getRing(spt, molecule.getBond(i));
235
for (int b = 0; b < ring.getBondCount(); b++) {
236
IBond ringBond = ring.getBond(b);
237
if (!fragContainer.contains(ringBond)) {
238
fragContainer.addBond(ringBond);
239
for (int atomCount = 0; atomCount < ringBond.getAtomCount(); atomCount++) {
240
IAtom atom = ringBond.getAtom(atomCount);
241
if (!fragContainer.contains(atom)) {
242
atom.setFlag(CDKConstants.ISINRING, true);
243
fragContainer.addAtom(atom);
249
return fragContainer;
253
* Identifies wether bonds are cyclic or not. It is used by several other methods.
255
* @throws NoSuchAtomException
257
private void identifyBonds() throws NoSuchAtomException {
258
IAtomContainer spt = getSpanningTree();
261
for (int i = 0; i < totalEdgeCount; i++) {
262
if (!bondsInTree[i]) {
263
ring = getRing(spt,molecule.getBond(i));
264
for (int b=0; b < ring.getBondCount(); b++ ) {
265
int m = molecule.getBondNumber(ring.getBond(b));
266
cb[nBasicRings][m] = 1;
271
spt = null; ring = null;
272
bondsAcyclicCount = 0; bondsCyclicCount = 0;
273
for (int i = 0; i < totalEdgeCount; i++) {
275
for (int j = 0; j < nBasicRings; j++) {
279
case(0): { bondsAcyclicCount++; break; }
280
case(1): { bondsCyclicCount ++; break; }
281
default: { bondsCyclicCount ++; }
284
identifiedBonds = true;
288
public IRingSet getAllRings() throws NoSuchAtomException {
289
IRingSet ringset = getBasicRings();
290
IRing newring = null;
291
//logger.debug("Rings "+ringset.size());
293
int nBasicRings = ringset.getAtomContainerCount();
294
for (int i = 0; i < nBasicRings; i++)
295
getBondsInRing(molecule,(IRing) ringset.getAtomContainer(i), cb[i]);
297
for (int i= 0; i < nBasicRings; i++) {
298
for (int j= i+1; j < nBasicRings; j++) {
299
//logger.debug("combining rings "+(i+1)+","+(j+1));
300
newring = combineRings(ringset, i, j);
301
//newring = combineRings((Ring)ringset.get(i),(Ring)ringset.get(j));
302
if (newring != null) ringset.addAtomContainer(newring);
309
public int getSpanningTreeSize() {
313
private IRing combineRings(IRingSet ringset, int i, int j) {
315
for (int b= 0; b < cb[i].length; b++) {
316
c = cb[i][b] + cb[j][b];
317
if (c > 1) break; //at least one common bond
319
if (c < 2) return null;
320
IRing ring = molecule.getBuilder().newRing();
321
IRing ring1 = (IRing) ringset.getAtomContainer(i);
322
IRing ring2 = (IRing) ringset.getAtomContainer(j);
323
for (int b= 0; b < cb[i].length; b++) {
324
c = cb[i][b] + cb[j][b];
325
if ((c == 1) && (cb[i][b] == 1)) ring.addBond(molecule.getBond(b));
327
if ((c == 1) && (cb[j][b] == 1)) ring.addBond(molecule.getBond(b));
329
for (int a = 0; a < ring1.getAtomCount(); a++)
330
ring.addAtom(ring1.getAtom(a));
331
for (int a = 0; a < ring2.getAtomCount(); a++)
332
ring.addAtom(ring2.getAtom(a));
338
* @return Returns the bondsAcyclicCount.
340
public int getBondsAcyclicCount() throws NoSuchAtomException {
341
if (!identifiedBonds) identifyBonds();
342
return bondsAcyclicCount;
346
* @return Returns the bondsCyclicCount.
348
public int getBondsCyclicCount() throws NoSuchAtomException {
349
if (!identifiedBonds) identifyBonds();
350
return bondsCyclicCount;
added
removed
src/org/openscience/cdk/graph/SpanningTree.java
