Branch data Line data Source code
1 : : /*
2 : : * International Chemical Identifier (InChI)
3 : : * Version 1
4 : : * Software version 1.07
5 : : * April 30, 2024
6 : : *
7 : : * MIT License
8 : : *
9 : : * Copyright (c) 2024 IUPAC and InChI Trust
10 : : *
11 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
12 : : * of this software and associated documentation files (the "Software"), to deal
13 : : * in the Software without restriction, including without limitation the rights
14 : : * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 : : * copies of the Software, and to permit persons to whom the Software is
16 : : * furnished to do so, subject to the following conditions:
17 : : *
18 : : * The above copyright notice and this permission notice shall be included in all
19 : : * copies or substantial portions of the Software.
20 : : *
21 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 : : * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
27 : : * SOFTWARE.
28 : : *
29 : : * The InChI library and programs are free software developed under the
30 : : * auspices of the International Union of Pure and Applied Chemistry (IUPAC).
31 : : * Originally developed at NIST.
32 : : * Modifications and additions by IUPAC and the InChI Trust.
33 : : * Some portions of code were developed/changed by external contributors
34 : : * (either contractor or volunteer) which are listed in the file
35 : : * 'External-contributors' included in this distribution.
36 : : *
37 : : * info@inchi-trust.org
38 : : *
39 : : */
40 : :
41 : : #include "mode.h"
42 : : #include "ichiring.h"
43 : :
44 : : #include "bcf_s.h"
45 : :
46 : : /* Local prototypes */
47 : : int GetMinRingSize( inp_ATOM* atom, QUEUE *q, AT_RANK *nAtomLevel, S_CHAR *cSource, AT_RANK nMaxRingSize );
48 : :
49 : : /* add to the queue */
50 : : int QueueAdd( QUEUE *q, QINT_TYPE *Val );
51 : : /* read & remove from the queue */
52 : : int QueueGet( QUEUE *q, QINT_TYPE *Val );
53 : : /* read from the queue */
54 : : int QueueGetAny( QUEUE *q, QINT_TYPE *, int ord );
55 : : /* initialize the queue */
56 : : int QueueReinit( QUEUE *q );
57 : : /* current queue length */
58 : : int QueueLength( QUEUE *q );
59 : : /* number of used queue internal elements */
60 : : int QueueWrittenLength( QUEUE *q );
61 : :
62 : :
63 : : #if ( QUEUE_QINT == 1 ) /* { */
64 : :
65 : :
66 : : /****************************************************************************/
67 : 69 : QUEUE *QueueCreate( int nTotLength, int nSize )
68 : : {
69 : 69 : QUEUE *q = NULL;
70 : 69 : QINT_TYPE *Val = NULL;
71 [ + - + - ]: 69 : if (nTotLength < 1 || nSize != ( int )sizeof( QINT_TYPE ) ||
72 [ + - ]: 69 : !( q = (QUEUE *) inchi_calloc( 1, sizeof( QUEUE ) ) ) ||
73 [ - + ]: 69 : !( Val = (QINT_TYPE *) inchi_calloc( nTotLength, nSize ) ))
74 : : {
75 [ # # # # ]: 0 : if (q) inchi_free( q );
76 : 0 : return NULL;
77 : : }
78 : 69 : q->Val = Val;
79 : : /* q->nSize = nSize; */
80 : 69 : q->nTotLength = nTotLength;
81 : :
82 : 69 : return q;
83 : : }
84 : :
85 : :
86 : : /****************************************************************************/
87 : 176 : int QueueAdd( QUEUE *q, QINT_TYPE *Val )
88 : : {
89 [ + - + - : 176 : if (q && Val && q->nLength < q->nTotLength)
+ - ]
90 : : {
91 : 176 : q->Val[( q->nFirst + q->nLength ) % q->nTotLength] = *Val;
92 : 176 : q->nLength++;
93 : 176 : return q->nLength;
94 : : }
95 : :
96 : 0 : return -1;
97 : : }
98 : :
99 : :
100 : : /****************************************************************************/
101 : 158 : int QueueGet( QUEUE *q, QINT_TYPE *Val )
102 : : {
103 [ + - + - : 158 : if (q && Val && q->nLength > 0)
+ - ]
104 : : {
105 : 158 : *Val = q->Val[q->nFirst];
106 : : /* new: do not allow to overwrite the retrieved value */
107 [ + - ]: 158 : q->nFirst = ( q->nFirst == q->nTotLength - 1 ) ? 0 : q->nFirst + 1;
108 : 158 : q->nLength--;
109 : : /* -- old --
110 : : if ( -- q->nLength ) {
111 : : q->nFirst = (q->nFirst == q->nTotLength - 1)? 0 : q->nFirst + 1;
112 : : }
113 : : */
114 : 158 : return q->nLength;
115 : : }
116 : :
117 : 0 : return -1;
118 : : }
119 : :
120 : :
121 : : /****************************************************************************/
122 : 176 : int QueueGetAny( QUEUE *q, QINT_TYPE *Val, int ord )
123 : : {
124 [ + - + - ]: 176 : if (0 <= ord && ord < q->nTotLength)
125 : : {
126 : 176 : *Val = q->Val[ord];
127 : 176 : return 1; /* success */
128 : : }
129 : : else
130 : : {
131 : 0 : return -1; /* error */
132 : : }
133 : : }
134 : :
135 : : #else /* } QUEUE_QINT == 1 { */
136 : :
137 : :
138 : : /****************************************************************************/
139 : : QUEUE *QueueCreate( int nTotLength, int nSize )
140 : : {
141 : : QUEUE *q = NULL;
142 : : QINT_TYPE *Val = NULL;
143 : : if (nTotLength < 1 || nSize < 1 ||
144 : : !( q = (QUEUE *) inchi_calloc( 1, sizeof( QUEUE ) ) ) ||
145 : : !( Val = (QINT_TYPE *) inchi_calloc( nTotLength, nSize ) ))
146 : : {
147 : : if (q) inchi_free( q );
148 : : return NULL;
149 : : }
150 : : q->Val = Val;
151 : : q->nSize = nSize;
152 : : q->nTotLength = nTotLength;
153 : : return q;
154 : : }
155 : : int QueueAdd( QUEUE *q, QINT_TYPE *Val )
156 : : {
157 : : if (q && Val && q->nLength < q->nTotLength)
158 : : {
159 : : memcpy( (char*) q->Val + ( ( q->nFirst + q->nLength ) % q->nTotLength )*q->nSize, Val, q->nSize );
160 : : q->nLength++;
161 : : return q->nLength;
162 : : }
163 : :
164 : : return -1;
165 : : }
166 : :
167 : :
168 : : /****************************************************************************/
169 : : int QueueGet( QUEUE *q, QINT_TYPE *Val )
170 : : {
171 : : if (q && Val && q->nLength > 0)
172 : : {
173 : : memcpy( Val, (char*) q->Val + q->nFirst * q->nSize, q->nSize );
174 : : if (--q->nLength)
175 : : {
176 : : q->nFirst = ( q->nFirst == q->nTotLength - 1 ) ? 0 : q->nFirst + 1;
177 : : }
178 : : return q->nLength;
179 : : }
180 : :
181 : : return -1;
182 : : }
183 : :
184 : :
185 : : /****************************************************************************/
186 : : int QueueGetAny( QUEUE *q, QINT_TYPE *Val, int ord )
187 : : {
188 : : if (0 <= ord && ord < q->nTotLength)
189 : : {
190 : : memcpy( Val, (char*) q->Val + ord * q->nSize, q->nSize );
191 : : return 1; /* success */
192 : : }
193 : : else
194 : : {
195 : : return -1; /* error */
196 : : }
197 : : }
198 : :
199 : : #endif /* } QUEUE_QINT == 1 */
200 : :
201 : :
202 : : /****************************************************************************/
203 : 69 : QUEUE *QueueDelete( QUEUE *q )
204 : : {
205 [ + - ]: 69 : if (q)
206 : : {
207 [ + - + - ]: 69 : if (q->Val) inchi_free( q->Val );
208 [ + - ]: 69 : inchi_free( q );
209 : : }
210 : :
211 : 69 : return NULL;
212 : : }
213 : :
214 : :
215 : : /****************************************************************************/
216 : 16 : int QueueReinit( QUEUE *q )
217 : : {
218 [ + - ]: 16 : if (q)
219 : : {
220 : 16 : q->nFirst = 0;
221 : 16 : q->nLength = 0;
222 : : /* memset( q->Val, 0, q->nTotLength*sizeof(q->Val[0])); */ /* for debug only */
223 : 16 : return q->nTotLength;
224 : : }
225 : :
226 : 0 : return -1;
227 : : }
228 : :
229 : :
230 : : /****************************************************************************/
231 : 72 : int QueueLength( QUEUE *q )
232 : : {
233 [ + - ]: 72 : if (q)
234 : : {
235 : 72 : return q->nLength;
236 : : }
237 : : else
238 : : {
239 : 0 : return 0;
240 : : }
241 : : }
242 : :
243 : :
244 : : /****************************************************************************/
245 : 16 : int QueueWrittenLength( QUEUE *q )
246 : : {
247 [ + - ]: 16 : if (q)
248 : : {
249 : 16 : int len = q->nFirst + q->nLength;
250 : 16 : return ( len > q->nTotLength ) ? q->nTotLength : len;
251 : : }
252 : : else
253 : : {
254 : 0 : return 0;
255 : : }
256 : : }
257 : :
258 : :
259 : : /****************************************************************************
260 : : BFS: Breadth First Search
261 : : ****************************************************************************/
262 : 16 : int GetMinRingSize( inp_ATOM* atom,
263 : : QUEUE *q,
264 : : AT_RANK *nAtomLevel,
265 : : S_CHAR *cSource,
266 : : AT_RANK nMaxRingSize )
267 : : {
268 : : int qLen, i, j;
269 : 16 : AT_RANK nCurLevel, nRingSize, nMinRingSize = MAX_ATOMS + 1;
270 : : qInt at_no, next;
271 : : int iat_no, inext;
272 : :
273 [ + + ]: 72 : while ((qLen = QueueLength( q ))) /* djb-rwth: addressing LLVM warning */
274 : : {
275 : : /* traverse the next level (next outer ring) */
276 [ + + ]: 214 : for (i = 0; i < qLen; i++)
277 : : {
278 [ + - ]: 158 : if (0 <= QueueGet( q, &at_no ))
279 : : {
280 : 158 : iat_no = (int) at_no;
281 : 158 : nCurLevel = nAtomLevel[iat_no] + 1;
282 [ + + ]: 158 : if (2 * nCurLevel > nMaxRingSize + 4)
283 : : {
284 : : /* 2*nCurLevel = nRingSize + 3 + k, k = 0 or 1 */
285 [ + - ]: 10 : if (nMinRingSize < MAX_ATOMS + 1)
286 : : {
287 [ + - ]: 10 : return ( nMinRingSize >= nMaxRingSize ) ? 0 : nMinRingSize;
288 : : }
289 : 0 : return 0; /* min. ring size > nMaxRingSize */
290 : : }
291 [ + + ]: 474 : for (j = 0; j < atom[iat_no].valence; j++)
292 : : {
293 : 326 : next = (qInt) atom[iat_no].neighbor[j];
294 : 326 : inext = (int) next;
295 [ + + ]: 326 : if (!nAtomLevel[inext])
296 : : {
297 : : /* the at_no neighbor has not been traversed yet. Add it to the queue */
298 [ + - ]: 140 : if (0 <= QueueAdd( q, &next ))
299 : : {
300 : 140 : nAtomLevel[inext] = nCurLevel;
301 : 140 : cSource[inext] = cSource[iat_no]; /* keep the path number */
302 : : }
303 : : else
304 : : {
305 : 0 : return -1; /* error */
306 : : }
307 : : }
308 : : else
309 : : {
310 [ + + ]: 186 : if (nAtomLevel[inext] + 1 >= nCurLevel &&
311 [ + + ]: 24 : cSource[inext] != cSource[iat_no]
312 : : /* && cSource[(int)next] != -1 */
313 : : )
314 : : {
315 : : /* found a ring closure */
316 : : /* debug */
317 [ - + ]: 20 : if (cSource[inext] == -1)
318 : : {
319 : 0 : return -1; /* error */
320 : : }
321 [ + + ]: 20 : if (( nRingSize = nAtomLevel[inext] + nCurLevel - 2 ) < nMinRingSize)
322 : : {
323 : 16 : nMinRingSize = nRingSize;
324 : : }
325 : : /* return (nRingSize >= nMaxRingSize)? 0 : nRingSize; */
326 : : }
327 : : }
328 : : }
329 : : }
330 : : else
331 : : {
332 : 0 : return -1; /* error */
333 : : }
334 : : }
335 : : }
336 : :
337 [ + - ]: 6 : if (nMinRingSize < MAX_ATOMS + 1)
338 : : {
339 [ + - ]: 6 : return ( nMinRingSize >= nMaxRingSize ) ? 0 : nMinRingSize;
340 : : }
341 : :
342 : 0 : return 0;
343 : : }
344 : :
345 : :
346 : : /****************************************************************************
347 : : Return value:
348 : : 0: nMaxRingSize < 3 or
349 : : min. ring size >= nMaxRingSize or
350 : : not a ring bond (the last is currently impossible: bond is known to belong to a ring system.
351 : : n>0: min. ring size < nMaxRingSize
352 : : n<0: error
353 : :
354 : : Input:
355 : : atom[]
356 : : at_no number of the 1st atom adjacent to the bond
357 : : neigh_ord ordering number of the bond in question: at[at_no].bond_type[neigh_ord]
358 : : q queue structure
359 : : nAtomLevel work array, DFS distance
360 : : cSource work array, origin mark
361 : : ****************************************************************************/
362 : 16 : int is_bond_in_Nmax_memb_ring( inp_ATOM* atom,
363 : : int at_no,
364 : : int neigh_ord,
365 : : QUEUE *q,
366 : : AT_RANK *nAtomLevel,
367 : : S_CHAR *cSource,
368 : : AT_RANK nMaxRingSize )
369 : : {
370 : 16 : int nMinRingSize = -1, i;
371 : : qInt n;
372 : : int nTotLen;
373 : :
374 [ - + ]: 16 : if (nMaxRingSize < 3)
375 : : {
376 : 0 : return 0;
377 : : }
378 : :
379 : 16 : QueueReinit( q );
380 : :
381 : : /* mark the starting atom */
382 : 16 : nAtomLevel[at_no] = 1;
383 : 16 : cSource[at_no] = -1;
384 : : /* add neighbors */
385 [ + + ]: 52 : for (i = 0; i < atom[at_no].valence; i++)
386 : : {
387 : 36 : n = (qInt) atom[at_no].neighbor[i];
388 : 36 : nAtomLevel[(int) n] = 2;
389 [ + + ]: 36 : cSource[(int) n] = 1 + ( i == neigh_ord );
390 : 36 : QueueAdd( q, &n );
391 : : }
392 : :
393 : 16 : nMinRingSize = GetMinRingSize( atom, q, nAtomLevel, cSource, nMaxRingSize );
394 : : /* cleanup */
395 : 16 : nTotLen = QueueWrittenLength( q );
396 [ + + ]: 192 : for (i = 0; i < nTotLen; i++)
397 : : {
398 [ + - ]: 176 : if (0 < QueueGetAny( q, &n, i ))
399 : : {
400 : 176 : nAtomLevel[(int) n] = 0;
401 : 176 : cSource[(int) n] = 0;
402 : : }
403 : : }
404 : 16 : nAtomLevel[at_no] = 0;
405 : 16 : cSource[at_no] = 0;
406 : :
407 : : /*
408 : : if ( nAtomLevel )
409 : : inchi_free ( nAtomLevel );
410 : : if ( cSource )
411 : : inchi_free ( cSource );
412 : : QueueDelete( q );
413 : : */
414 : :
415 : 16 : return nMinRingSize;
416 : : }
417 : :
418 : :
419 : : /****************************************************************************/
420 : 34 : int is_atom_in_3memb_ring( inp_ATOM* atom, int at_no )
421 : : {
422 : : AT_NUMB neigh_neigh;
423 : : int i, j, k, val, val_neigh, neigh;
424 : :
425 [ + - ]: 34 : if (atom[at_no].nNumAtInRingSystem < 3)
426 : : {
427 : 34 : return 0;
428 : : }
429 : :
430 [ # # ]: 0 : for (i = 0, val = atom[at_no].valence; i < val; i++)
431 : : {
432 : 0 : neigh = (int) atom[at_no].neighbor[i];
433 [ # # ]: 0 : if (atom[at_no].nRingSystem != atom[neigh].nRingSystem)
434 : : {
435 : 0 : continue;
436 : : }
437 [ # # ]: 0 : for (j = 0, val_neigh = atom[neigh].valence; j < val_neigh; j++)
438 : : {
439 : 0 : neigh_neigh = atom[neigh].neighbor[j];
440 [ # # ]: 0 : if ((int) neigh_neigh == at_no)
441 : : {
442 : 0 : continue;
443 : : }
444 [ # # ]: 0 : for (k = 0; k < val; k++)
445 : : {
446 [ # # ]: 0 : if (atom[at_no].neighbor[k] == neigh_neigh)
447 : : {
448 : 0 : return 1;
449 : : }
450 : : }
451 : : }
452 : : }
453 : :
454 : 0 : return 0;
455 : : }
|
