Branch data Line data Source code
1 : : /*
2 : : * SPDX-License-Identifier: MIT
3 : : * Copyright (c) 2024 IUPAC and InChI Trust
4 : : */
5 : :
6 : : #include "mode.h"
7 : : #include "ichiring.h"
8 : :
9 : : #include "bcf_s.h"
10 : :
11 : : /* Local prototypes */
12 : : int GetMinRingSize( inp_ATOM* atom, QUEUE *q, AT_RANK *nAtomLevel, S_CHAR *cSource, AT_RANK nMaxRingSize );
13 : :
14 : : /* add to the queue */
15 : : int QueueAdd( QUEUE *q, QINT_TYPE *Val );
16 : : /* read & remove from the queue */
17 : : int QueueGet( QUEUE *q, QINT_TYPE *Val );
18 : : /* read from the queue */
19 : : int QueueGetAny( QUEUE *q, QINT_TYPE *, int ord );
20 : : /* initialize the queue */
21 : : int QueueReinit( QUEUE *q );
22 : : /* current queue length */
23 : : int QueueLength( QUEUE *q );
24 : : /* number of used queue internal elements */
25 : : int QueueWrittenLength( QUEUE *q );
26 : :
27 : :
28 : : #if ( QUEUE_QINT == 1 ) /* { */
29 : :
30 : :
31 : : /****************************************************************************/
32 : 161 : QUEUE *QueueCreate( int nTotLength, int nSize )
33 : : {
34 : 161 : QUEUE *q = NULL;
35 : 161 : QINT_TYPE *Val = NULL;
36 [ + - + - ]: 161 : if (nTotLength < 1 || nSize != ( int )sizeof( QINT_TYPE ) ||
37 [ + - ]: 161 : !( q = (QUEUE *) inchi_calloc( 1, sizeof( QUEUE ) ) ) ||
38 [ - + ]: 161 : !( Val = (QINT_TYPE *) inchi_calloc( nTotLength, nSize ) ))
39 : : {
40 [ # # # # ]: 0 : if (q) inchi_free( q );
41 : 0 : return NULL;
42 : : }
43 : 161 : q->Val = Val;
44 : : /* q->nSize = nSize; */
45 : 161 : q->nTotLength = nTotLength;
46 : :
47 : 161 : return q;
48 : : }
49 : :
50 : :
51 : : /****************************************************************************/
52 : 580 : int QueueAdd( QUEUE *q, QINT_TYPE *Val )
53 : : {
54 [ + - + - : 580 : if (q && Val && q->nLength < q->nTotLength)
+ - ]
55 : : {
56 : 580 : q->Val[( q->nFirst + q->nLength ) % q->nTotLength] = *Val;
57 : 580 : q->nLength++;
58 : 580 : return q->nLength;
59 : : }
60 : :
61 : 0 : return -1;
62 : : }
63 : :
64 : :
65 : : /****************************************************************************/
66 : 498 : int QueueGet( QUEUE *q, QINT_TYPE *Val )
67 : : {
68 [ + - + - : 498 : if (q && Val && q->nLength > 0)
+ - ]
69 : : {
70 : 498 : *Val = q->Val[q->nFirst];
71 : : /* new: do not allow to overwrite the retrieved value */
72 [ + - ]: 498 : q->nFirst = ( q->nFirst == q->nTotLength - 1 ) ? 0 : q->nFirst + 1;
73 : 498 : q->nLength--;
74 : : /* -- old --
75 : : if ( -- q->nLength ) {
76 : : q->nFirst = (q->nFirst == q->nTotLength - 1)? 0 : q->nFirst + 1;
77 : : }
78 : : */
79 : 498 : return q->nLength;
80 : : }
81 : :
82 : 0 : return -1;
83 : : }
84 : :
85 : :
86 : : /****************************************************************************/
87 : 580 : int QueueGetAny( QUEUE *q, QINT_TYPE *Val, int ord )
88 : : {
89 [ + - + - ]: 580 : if (0 <= ord && ord < q->nTotLength)
90 : : {
91 : 580 : *Val = q->Val[ord];
92 : 580 : return 1; /* success */
93 : : }
94 : : else
95 : : {
96 : 0 : return -1; /* error */
97 : : }
98 : : }
99 : :
100 : : #else /* } QUEUE_QINT == 1 { */
101 : :
102 : :
103 : : /****************************************************************************/
104 : : QUEUE *QueueCreate( int nTotLength, int nSize )
105 : : {
106 : : QUEUE *q = NULL;
107 : : QINT_TYPE *Val = NULL;
108 : : if (nTotLength < 1 || nSize < 1 ||
109 : : !( q = (QUEUE *) inchi_calloc( 1, sizeof( QUEUE ) ) ) ||
110 : : !( Val = (QINT_TYPE *) inchi_calloc( nTotLength, nSize ) ))
111 : : {
112 : : if (q) inchi_free( q );
113 : : return NULL;
114 : : }
115 : : q->Val = Val;
116 : : q->nSize = nSize;
117 : : q->nTotLength = nTotLength;
118 : : return q;
119 : : }
120 : : int QueueAdd( QUEUE *q, QINT_TYPE *Val )
121 : : {
122 : : if (q && Val && q->nLength < q->nTotLength)
123 : : {
124 : : memcpy( (char*) q->Val + ( ( q->nFirst + q->nLength ) % q->nTotLength )*q->nSize, Val, q->nSize );
125 : : q->nLength++;
126 : : return q->nLength;
127 : : }
128 : :
129 : : return -1;
130 : : }
131 : :
132 : :
133 : : /****************************************************************************/
134 : : int QueueGet( QUEUE *q, QINT_TYPE *Val )
135 : : {
136 : : if (q && Val && q->nLength > 0)
137 : : {
138 : : memcpy( Val, (char*) q->Val + q->nFirst * q->nSize, q->nSize );
139 : : if (--q->nLength)
140 : : {
141 : : q->nFirst = ( q->nFirst == q->nTotLength - 1 ) ? 0 : q->nFirst + 1;
142 : : }
143 : : return q->nLength;
144 : : }
145 : :
146 : : return -1;
147 : : }
148 : :
149 : :
150 : : /****************************************************************************/
151 : : int QueueGetAny( QUEUE *q, QINT_TYPE *Val, int ord )
152 : : {
153 : : if (0 <= ord && ord < q->nTotLength)
154 : : {
155 : : memcpy( Val, (char*) q->Val + ord * q->nSize, q->nSize );
156 : : return 1; /* success */
157 : : }
158 : : else
159 : : {
160 : : return -1; /* error */
161 : : }
162 : : }
163 : :
164 : : #endif /* } QUEUE_QINT == 1 */
165 : :
166 : :
167 : : /****************************************************************************/
168 : 161 : QUEUE *QueueDelete( QUEUE *q )
169 : : {
170 [ + - ]: 161 : if (q)
171 : : {
172 [ + - + - ]: 161 : if (q->Val) inchi_free( q->Val );
173 [ + - ]: 161 : inchi_free( q );
174 : : }
175 : :
176 : 161 : return NULL;
177 : : }
178 : :
179 : :
180 : : /****************************************************************************/
181 : 42 : int QueueReinit( QUEUE *q )
182 : : {
183 [ + - ]: 42 : if (q)
184 : : {
185 : 42 : q->nFirst = 0;
186 : 42 : q->nLength = 0;
187 : : /* memset( q->Val, 0, q->nTotLength*sizeof(q->Val[0])); */ /* for debug only */
188 : 42 : return q->nTotLength;
189 : : }
190 : :
191 : 0 : return -1;
192 : : }
193 : :
194 : :
195 : : /****************************************************************************/
196 : 202 : int QueueLength( QUEUE *q )
197 : : {
198 [ + - ]: 202 : if (q)
199 : : {
200 : 202 : return q->nLength;
201 : : }
202 : : else
203 : : {
204 : 0 : return 0;
205 : : }
206 : : }
207 : :
208 : :
209 : : /****************************************************************************/
210 : 42 : int QueueWrittenLength( QUEUE *q )
211 : : {
212 [ + - ]: 42 : if (q)
213 : : {
214 : 42 : int len = q->nFirst + q->nLength;
215 : 42 : return ( len > q->nTotLength ) ? q->nTotLength : len;
216 : : }
217 : : else
218 : : {
219 : 0 : return 0;
220 : : }
221 : : }
222 : :
223 : :
224 : : /****************************************************************************
225 : : BFS: Breadth First Search
226 : : ****************************************************************************/
227 : 42 : int GetMinRingSize( inp_ATOM* atom,
228 : : QUEUE *q,
229 : : AT_RANK *nAtomLevel,
230 : : S_CHAR *cSource,
231 : : AT_RANK nMaxRingSize )
232 : : {
233 : : int qLen, i, j;
234 : 42 : AT_RANK nCurLevel, nRingSize, nMinRingSize = MAX_ATOMS + 1;
235 : : qInt at_no, next;
236 : : int iat_no, inext;
237 : :
238 [ + + ]: 202 : while ((qLen = QueueLength( q ))) /* djb-rwth: addressing LLVM warning */
239 : : {
240 : : /* traverse the next level (next outer ring) */
241 [ + + ]: 658 : for (i = 0; i < qLen; i++)
242 : : {
243 [ + - ]: 498 : if (0 <= QueueGet( q, &at_no ))
244 : : {
245 : 498 : iat_no = (int) at_no;
246 : 498 : nCurLevel = nAtomLevel[iat_no] + 1;
247 [ + + ]: 498 : if (2 * nCurLevel > nMaxRingSize + 4)
248 : : {
249 : : /* 2*nCurLevel = nRingSize + 3 + k, k = 0 or 1 */
250 [ + - ]: 36 : if (nMinRingSize < MAX_ATOMS + 1)
251 : : {
252 [ + - ]: 36 : return ( nMinRingSize >= nMaxRingSize ) ? 0 : nMinRingSize;
253 : : }
254 : 0 : return 0; /* min. ring size > nMaxRingSize */
255 : : }
256 [ + + ]: 1530 : for (j = 0; j < atom[iat_no].valence; j++)
257 : : {
258 : 1068 : next = (qInt) atom[iat_no].neighbor[j];
259 : 1068 : inext = (int) next;
260 [ + + ]: 1068 : if (!nAtomLevel[inext])
261 : : {
262 : : /* the at_no neighbor has not been traversed yet. Add it to the queue */
263 [ + - ]: 476 : if (0 <= QueueAdd( q, &next ))
264 : : {
265 : 476 : nAtomLevel[inext] = nCurLevel;
266 : 476 : cSource[inext] = cSource[iat_no]; /* keep the path number */
267 : : }
268 : : else
269 : : {
270 : 0 : return -1; /* error */
271 : : }
272 : : }
273 : : else
274 : : {
275 [ + + ]: 592 : if (nAtomLevel[inext] + 1 >= nCurLevel &&
276 [ + + ]: 82 : cSource[inext] != cSource[iat_no]
277 : : /* && cSource[(int)next] != -1 */
278 : : )
279 : : {
280 : : /* found a ring closure */
281 : : /* debug */
282 [ - + ]: 52 : if (cSource[inext] == -1)
283 : : {
284 : 0 : return -1; /* error */
285 : : }
286 [ + + ]: 52 : if (( nRingSize = nAtomLevel[inext] + nCurLevel - 2 ) < nMinRingSize)
287 : : {
288 : 42 : nMinRingSize = nRingSize;
289 : : }
290 : : /* return (nRingSize >= nMaxRingSize)? 0 : nRingSize; */
291 : : }
292 : : }
293 : : }
294 : : }
295 : : else
296 : : {
297 : 0 : return -1; /* error */
298 : : }
299 : : }
300 : : }
301 : :
302 [ + - ]: 6 : if (nMinRingSize < MAX_ATOMS + 1)
303 : : {
304 [ + - ]: 6 : return ( nMinRingSize >= nMaxRingSize ) ? 0 : nMinRingSize;
305 : : }
306 : :
307 : 0 : return 0;
308 : : }
309 : :
310 : :
311 : : /****************************************************************************
312 : : Return value:
313 : : 0: nMaxRingSize < 3 or
314 : : min. ring size >= nMaxRingSize or
315 : : not a ring bond (the last is currently impossible: bond is known to belong to a ring system.
316 : : n>0: min. ring size < nMaxRingSize
317 : : n<0: error
318 : :
319 : : Input:
320 : : atom[]
321 : : at_no number of the 1st atom adjacent to the bond
322 : : neigh_ord ordering number of the bond in question: at[at_no].bond_type[neigh_ord]
323 : : q queue structure
324 : : nAtomLevel work array, DFS distance
325 : : cSource work array, origin mark
326 : : ****************************************************************************/
327 : 42 : int is_bond_in_Nmax_memb_ring( inp_ATOM* atom,
328 : : int at_no,
329 : : int neigh_ord,
330 : : QUEUE *q,
331 : : AT_RANK *nAtomLevel,
332 : : S_CHAR *cSource,
333 : : AT_RANK nMaxRingSize )
334 : : {
335 : 42 : int nMinRingSize = -1, i;
336 : : qInt n;
337 : : int nTotLen;
338 : :
339 [ - + ]: 42 : if (nMaxRingSize < 3)
340 : : {
341 : 0 : return 0;
342 : : }
343 : :
344 : 42 : QueueReinit( q );
345 : :
346 : : /* mark the starting atom */
347 : 42 : nAtomLevel[at_no] = 1;
348 : 42 : cSource[at_no] = -1;
349 : : /* add neighbors */
350 [ + + ]: 146 : for (i = 0; i < atom[at_no].valence; i++)
351 : : {
352 : 104 : n = (qInt) atom[at_no].neighbor[i];
353 : 104 : nAtomLevel[(int) n] = 2;
354 [ + + ]: 104 : cSource[(int) n] = 1 + ( i == neigh_ord );
355 : 104 : QueueAdd( q, &n );
356 : : }
357 : :
358 : 42 : nMinRingSize = GetMinRingSize( atom, q, nAtomLevel, cSource, nMaxRingSize );
359 : : /* cleanup */
360 : 42 : nTotLen = QueueWrittenLength( q );
361 [ + + ]: 622 : for (i = 0; i < nTotLen; i++)
362 : : {
363 [ + - ]: 580 : if (0 < QueueGetAny( q, &n, i ))
364 : : {
365 : 580 : nAtomLevel[(int) n] = 0;
366 : 580 : cSource[(int) n] = 0;
367 : : }
368 : : }
369 : 42 : nAtomLevel[at_no] = 0;
370 : 42 : cSource[at_no] = 0;
371 : :
372 : : /*
373 : : if ( nAtomLevel )
374 : : inchi_free ( nAtomLevel );
375 : : if ( cSource )
376 : : inchi_free ( cSource );
377 : : QueueDelete( q );
378 : : */
379 : :
380 : 42 : return nMinRingSize;
381 : : }
382 : :
383 : :
384 : : /****************************************************************************/
385 : 36 : int is_atom_in_3memb_ring( inp_ATOM* atom, int at_no )
386 : : {
387 : : AT_NUMB neigh_neigh;
388 : : int i, j, k, val, val_neigh, neigh;
389 : :
390 [ + - ]: 36 : if (atom[at_no].nNumAtInRingSystem < 3)
391 : : {
392 : 36 : return 0;
393 : : }
394 : :
395 [ # # ]: 0 : for (i = 0, val = atom[at_no].valence; i < val; i++)
396 : : {
397 : 0 : neigh = (int) atom[at_no].neighbor[i];
398 [ # # ]: 0 : if (atom[at_no].nRingSystem != atom[neigh].nRingSystem)
399 : : {
400 : 0 : continue;
401 : : }
402 [ # # ]: 0 : for (j = 0, val_neigh = atom[neigh].valence; j < val_neigh; j++)
403 : : {
404 : 0 : neigh_neigh = atom[neigh].neighbor[j];
405 [ # # ]: 0 : if ((int) neigh_neigh == at_no)
406 : : {
407 : 0 : continue;
408 : : }
409 [ # # ]: 0 : for (k = 0; k < val; k++)
410 : : {
411 [ # # ]: 0 : if (atom[at_no].neighbor[k] == neigh_neigh)
412 : : {
413 : 0 : return 1;
414 : : }
415 : : }
416 : : }
417 : : }
418 : :
419 : 0 : return 0;
420 : : }
|
