← Back to branch summary

~ubuntu-branches/debian/stretch/openbabel/stretch

« back to all changes in this revision

Viewing changes to src/formats/inchi/ichiring.c

  • Committer: Bazaar Package Importer
  • Author(s): Daniel Leidert (dale)
  • Date: 2009-07-17 00:18:06 UTC
  • mfrom: (6.1.1 sid)
  • Revision ID: james.westby@ubuntu.com-20090717001806-sy3mzs3e1d1adbs9
Tags: 2.2.2-2
http://bugs.debian.org/537102
* debian/control (Uploaders): Removed LI Daobing. Thanks for your work!
  (Standards-Version): Bumped to 3.8.2.
  (Vcs-Svn): Fixed vcs-field-uses-not-recommended-uri-format.
* debian/patches/537102_fix_tr1_memory_detection.patch: Added.
  - configure.in, configure, src/config.h.in: Fix detection of tr1/memory to
    prevent building the package with boost (closes: #537102).

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/formats/inchi/ichiring.c
1
 
/*
2
 
 * International Chemical Identifier (InChI)
3
 
 * Version 1
4
 
 * Software version 1.02-beta
5
 
 * August 23, 2007
6
 
 * Developed at NIST
7
 
 *
8
 
 * The InChI library and programs are free software developed under the
9
 
 * auspices of the International Union of Pure and Applied Chemistry (IUPAC);
10
 
 * you can redistribute this software and/or modify it under the terms of 
11
 
 * the GNU Lesser General Public License as published by the Free Software 
12
 
 * Foundation:
13
 
 * http://www.opensource.org/licenses/lgpl-license.php
14
 
 */
15
 
 
16
 
 
17
 
#include <stdio.h>
18
 
#include <stdlib.h>
19
 
#include <string.h>
20
 
 
21
 
#include "mode.h"
22
 
 
23
 
#include "inpdef.h"
24
 
#include "extr_ct.h"
25
 
#include "ichiring.h"
26
 
 
27
 
/* local prototypes */
28
 
int GetMinRingSize( inp_ATOM* atom, QUEUE *q, AT_RANK *nAtomLevel, S_CHAR *cSource, AT_RANK nMaxRingSize );
29
 
 
30
 
 
31
 
 
32
 
 
33
 
/*******************************************************************/
34
 
/*  add to the queue */
35
 
int QueueAdd( QUEUE *q, QINT_TYPE *Val );
36
 
/*  read & remove from the queue */
37
 
int QueueGet( QUEUE *q, QINT_TYPE *Val );
38
 
/*  read from the queue */
39
 
int QueueGetAny( QUEUE *q, QINT_TYPE *, int ord );
40
 
/*  initialize the queue */
41
 
int QueueReinit( QUEUE *q );
42
 
/*  current queue length */
43
 
int QueueLength( QUEUE *q );
44
 
/*  number of used queue internal elements */
45
 
int QueueWrittenLength( QUEUE *q );
46
 
 
47
 
 
48
 
#if( QUEUE_QINT == 1 )  /* { */
49
 
 
50
 
QUEUE *QueueCreate( int nTotLength, int nSize )
51
 
{
52
 
    QUEUE     *q   = NULL;
53
 
    QINT_TYPE *Val = NULL;
54
 
    if ( nTotLength < 1 || nSize != (int)sizeof(QINT_TYPE) ||
55
 
         !(q   = (QUEUE     *) inchi_calloc( 1, sizeof(QUEUE)) ) ||
56
 
         !(Val = (QINT_TYPE *) inchi_calloc( nTotLength, nSize) )) {
57
 
        if ( q ) inchi_free(q);
58
 
        return NULL;
59
 
    }
60
 
    q->Val        = Val;
61
 
    /* q->nSize      = nSize; */
62
 
    q->nTotLength = nTotLength;
63
 
    return q;
64
 
}
65
 
int QueueAdd( QUEUE *q, QINT_TYPE *Val )
66
 
{
67
 
    if ( q && Val && q->nLength < q->nTotLength ) {
68
 
         q->Val[ (q->nFirst + q->nLength) % q->nTotLength ] = *Val;
69
 
         q->nLength ++;
70
 
         return q->nLength;
71
 
    }
72
 
    return -1;
73
 
}
74
 
int QueueGet( QUEUE *q, QINT_TYPE *Val )
75
 
{
76
 
    if ( q && Val && q->nLength > 0 ) {
77
 
        *Val = q->Val[ q->nFirst ];
78
 
        /* new: do not allow to overwrite the retrieved value */
79
 
        q->nFirst = (q->nFirst == q->nTotLength - 1)? 0 : q->nFirst + 1;
80
 
        q->nLength --;
81
 
        /* -- old --
82
 
        if ( -- q->nLength ) {
83
 
            q->nFirst = (q->nFirst == q->nTotLength - 1)? 0 : q->nFirst + 1;
84
 
        }
85
 
        */
86
 
        return q->nLength;
87
 
    }
88
 
    return -1;
89
 
}
90
 
int QueueGetAny( QUEUE *q, QINT_TYPE *Val, int ord )
91
 
{
92
 
    if ( 0 <= ord && ord < q->nTotLength ) {
93
 
        *Val = q->Val[ ord ];
94
 
        return  1; /*  success */
95
 
    } else {
96
 
        return -1; /*  error */
97
 
    }
98
 
}
99
 
 
100
 
#else  /* } QUEUE_QINT == 1 { */
101
 
 
102
 
QUEUE *QueueCreate( int nTotLength, int nSize )
103
 
{
104
 
    QUEUE     *q   = NULL;
105
 
    QINT_TYPE *Val = NULL;
106
 
    if ( nTotLength < 1 || nSize < 1 ||
107
 
         !(q   = (QUEUE     *) inchi_calloc( 1, sizeof(QUEUE)) ) ||
108
 
         !(Val = (QINT_TYPE *) inchi_calloc( nTotLength, nSize) )) {
109
 
        if ( q ) inchi_free(q);
110
 
        return NULL;
111
 
    }
112
 
    q->Val        = Val;
113
 
    q->nSize      = nSize;
114
 
    q->nTotLength = nTotLength;
115
 
    return q;
116
 
}
117
 
int QueueAdd( QUEUE *q, QINT_TYPE *Val )
118
 
{
119
 
    if ( q && Val && q->nLength < q->nTotLength ) {
120
 
         memcpy( (char*)q->Val + ((q->nFirst + q->nLength) % q->nTotLength)*q->nSize, Val, q->nSize);
121
 
         q->nLength ++;
122
 
         return q->nLength;
123
 
    }
124
 
    return -1;
125
 
}
126
 
int QueueGet( QUEUE *q, QINT_TYPE *Val )
127
 
{
128
 
    if ( q && Val && q->nLength > 0 ) {
129
 
        memcpy( Val, (char*)q->Val + q->nFirst * q->nSize, q->nSize);
130
 
        if ( -- q->nLength ) {
131
 
            q->nFirst = (q->nFirst == q->nTotLength - 1)? 0 : q->nFirst + 1;
132
 
        }
133
 
        return q->nLength;
134
 
    }
135
 
    return -1;
136
 
}
137
 
int QueueGetAny( QUEUE *q, QINT_TYPE *Val, int ord )
138
 
{
139
 
    if ( 0 <= ord && ord < q->nTotLength ) {
140
 
        memcpy( Val, (char*)q->Val + ord * q->nSize, q->nSize);
141
 
        return  1; /*  success */
142
 
    } else {
143
 
        return -1; /*  error */
144
 
    }
145
 
}
146
 
 
147
 
#endif /* } QUEUE_QINT == 1 */
148
 
 
149
 
QUEUE *QueueDelete( QUEUE *q )
150
 
{
151
 
    if ( q ) {
152
 
        if ( q->Val ) inchi_free(q->Val);
153
 
        inchi_free( q );
154
 
    }
155
 
    return NULL;
156
 
}
157
 
int QueueReinit( QUEUE *q )
158
 
{
159
 
    if ( q ) {
160
 
        q->nFirst  = 0;
161
 
        q->nLength = 0;
162
 
        /* memset( q->Val, 0, q->nTotLength*sizeof(q->Val[0])); */ /*  for debug only */
163
 
        return q->nTotLength;
164
 
    }
165
 
    return -1;
166
 
}
167
 
int QueueLength( QUEUE *q )
168
 
{
169
 
    if ( q ) {
170
 
        return q->nLength;
171
 
    } else {
172
 
        return 0;
173
 
    }
174
 
}
175
 
int QueueWrittenLength( QUEUE *q )
176
 
{
177
 
    if ( q ) {
178
 
        int len = q->nFirst+q->nLength;
179
 
        return (len > q->nTotLength)? q->nTotLength : len;
180
 
    } else {
181
 
        return 0;
182
 
    }
183
 
}
184
 
 
185
 
/**********************************************************************************/
186
 
/*  BFS: Breadth First Search */
187
 
int GetMinRingSize( inp_ATOM* atom, QUEUE *q, AT_RANK *nAtomLevel, S_CHAR *cSource, AT_RANK nMaxRingSize )
188
 
{
189
 
    int qLen, i, j;
190
 
    AT_RANK nCurLevel, nRingSize, nMinRingSize=MAX_ATOMS+1;
191
 
    qInt at_no, next;
192
 
    int  iat_no, inext;
193
 
    
194
 
    while ( qLen = QueueLength( q ) ) {
195
 
        /*  traverse the next level (next outer ring) */
196
 
        for ( i = 0; i < qLen; i ++ ) {
197
 
            if ( 0 <= QueueGet( q, &at_no ) ) {
198
 
                iat_no = (int)at_no;
199
 
                nCurLevel = nAtomLevel[iat_no] + 1;
200
 
                if ( 2*nCurLevel > nMaxRingSize + 4 ) {
201
 
                    /*  2*nCurLevel = nRingSize + 3 + k, k = 0 or 1  */
202
 
                    if ( nMinRingSize < MAX_ATOMS+1 ) {
203
 
                        return (nMinRingSize >= nMaxRingSize)? 0 : nMinRingSize;
204
 
                    }
205
 
                    return 0; /*  min. ring size > nMaxRingSize */
206
 
                }
207
 
                for ( j = 0; j < atom[iat_no].valence; j ++ ) {
208
 
                    next  = (qInt)atom[iat_no].neighbor[j];
209
 
                    inext = (int)next;
210
 
                    if ( !nAtomLevel[inext] ) {
211
 
                        /*  the at_no neighbor has not been traversed yet. Add it to the queue */
212
 
                        if ( 0 <= QueueAdd( q, &next ) ) {
213
 
                            nAtomLevel[inext] = nCurLevel;
214
 
                            cSource[inext] = cSource[iat_no]; /*  keep the path number */
215
 
                        } else {
216
 
                            return -1; /*  error */
217
 
                        }
218
 
                    } else
219
 
                    if ( nAtomLevel[inext]+1 >= nCurLevel &&
220
 
                         cSource[inext] != cSource[iat_no]
221
 
                         /*  && cSource[(int)next] != -1 */
222
 
                       ) {
223
 
                        /*  found a ring closure */
224
 
                        /*  debug */
225
 
                        if ( cSource[inext] == -1 ) {
226
 
                            return -1;  /*  error */
227
 
                        }
228
 
                        if ( (nRingSize = nAtomLevel[inext] + nCurLevel - 2) < nMinRingSize ) {
229
 
                            nMinRingSize = nRingSize;
230
 
                        }
231
 
                        /* return (nRingSize >= nMaxRingSize)? 0 : nRingSize; */
232
 
                    }
233
 
                }
234
 
            } else {
235
 
                return -1; /*  error */
236
 
            }
237
 
        }
238
 
    }
239
 
 
240
 
    if ( nMinRingSize < MAX_ATOMS+1 ) {
241
 
        return (nMinRingSize >= nMaxRingSize)? 0 : nMinRingSize;
242
 
    }
243
 
 
244
 
    return 0;
245
 
}
246
 
/*******************************************************************/
247
 
/* Return value:
248
 
     0:    nMaxRingSize < 3 or
249
 
           min. ring size >= nMaxRingSize or
250
 
           not a ring bond (the last is currently impossible: bond is known to belong to a ring system.
251
 
     n>0:  min. ring size < nMaxRingSize
252
 
     n<0:  error
253
 
   
254
 
  Input:
255
 
     atom[]
256
 
     at_no      number of the 1st atom adjacent to the bond
257
 
     neigh_ord  ordering number of the bond in question: at[at_no].bond_type[neigh_ord]
258
 
     q          queue structure
259
 
     nAtomLevel work array, DFS distance
260
 
     cSource    work array, origin mark
261
 
*/
262
 
 
263
 
int is_bond_in_Nmax_memb_ring( inp_ATOM* atom, int at_no, int neigh_ord, QUEUE *q, AT_RANK *nAtomLevel, S_CHAR *cSource, AT_RANK nMaxRingSize )
264
 
{
265
 
    int  nMinRingSize = -1, i;
266
 
    qInt n;
267
 
    int  nTotLen;
268
 
 
269
 
    if ( nMaxRingSize < 3 ) {
270
 
        return 0;
271
 
    }
272
 
    
273
 
    QueueReinit( q );
274
 
 
275
 
    /*  mark the starting atom */
276
 
    nAtomLevel[at_no] =  1;
277
 
    cSource[at_no]    = -1;
278
 
    /*  add neighbors */
279
 
    for ( i = 0; i < atom[at_no].valence; i ++ ) {
280
 
        n = (qInt)atom[at_no].neighbor[i];
281
 
        nAtomLevel[(int)n] = 2;
282
 
        cSource[(int)n]    = 1 + (i==neigh_ord);
283
 
        QueueAdd( q, &n );
284
 
    }
285
 
 
286
 
    nMinRingSize =  GetMinRingSize( atom, q, nAtomLevel, cSource, nMaxRingSize );
287
 
    /*  cleanup */
288
 
    nTotLen = QueueWrittenLength( q );
289
 
    for ( i = 0; i < nTotLen; i ++ ) {
290
 
        if ( 0 < QueueGetAny( q, &n, i ) ) {
291
 
            nAtomLevel[(int)n] = 0;
292
 
            cSource[(int)n]    = 0;
293
 
        }
294
 
    }
295
 
    nAtomLevel[at_no] = 0;
296
 
    cSource[at_no]    = 0;
297
 
 
298
 
 
299
 
/*
300
 
    if ( nAtomLevel )
301
 
        inchi_free ( nAtomLevel );
302
 
    if ( cSource )
303
 
        inchi_free ( cSource );
304
 
    QueueDelete( q );
305
 
*/
306
 
    return nMinRingSize;
307
 
}
308
 
/*******************************************************************/
309
 
int is_atom_in_3memb_ring( inp_ATOM* atom, int at_no )
310
 
{
311
 
    AT_NUMB   neigh_neigh;
312
 
    int       i, j, k, val, val_neigh, neigh;
313
 
 
314
 
    if ( atom[at_no].nNumAtInRingSystem < 3 ) {
315
 
        return 0;
316
 
    }
317
 
    
318
 
    for ( i = 0, val = atom[at_no].valence; i < val; i ++ ) {
319
 
        neigh = (int)atom[at_no].neighbor[i];
320
 
        if ( atom[at_no].nRingSystem != atom[neigh].nRingSystem )
321
 
            continue;
322
 
        for ( j = 0, val_neigh = atom[neigh].valence; j < val_neigh; j ++ ) {
323
 
            neigh_neigh = atom[neigh].neighbor[j];
324
 
            if ( (int)neigh_neigh == at_no )
325
 
                continue;
326
 
            for ( k = 0; k < val; k ++ ) {
327
 
                if ( atom[at_no].neighbor[k] == neigh_neigh ) {
328
 
                    return 1;
329
 
                }
330
 
            }
331
 
        }
332
 
    }
333
 
    return 0;
334
 
}