2
* International Union of Pure and Applied Chemistry (IUPAC)
3
* International Chemical Identifier (InChI)
5
* Software version 1.01
10
#ifndef __INCHI_BNS_H___
11
#define __INCHI_BNS_H___
13
#define BN_MAX_ALTP 16
14
/*#define MAX_VERTEX 1024*/ /* including s; if vert[] has num_vert then MAX_VERTEX has (2*num_vert+2+FIRST_INDX) elements */
16
/* forward declarations */
18
struct BalancedNetworkStructure;
19
struct BalancedNetworkData;
20
struct tagTautomerGroupsInfo;
21
struct tagChargeGroupsInfo;
22
struct BN_AtomsAtTautGroup;
23
struct tagSaltChargeCandidate;
25
/* define BNS types */
27
typedef S_SHORT Vertex;
28
typedef S_SHORT EdgeIndex;
29
typedef S_SHORT Edge[2]; /* Edge[0] = vertex1, Edge[1] = iedge or -(1+vertex1) if vertex2 = s or t */
30
typedef S_SHORT BNS_IEDGE;
31
typedef S_SHORT EdgeFlow;
32
typedef S_SHORT VertexFlow;
35
#define BNS_EDGE_FORBIDDEN_MASK 1
36
#define BNS_EDGE_FORBIDDEN_TEMP 2
37
#define BNS_EDGE_FORBIDDEN_TEST 4
39
/* BNS vertex types */
41
#define BNS_VERT_TYPE_ATOM 0x0001
42
#define BNS_VERT_TYPE_ENDPOINT 0x0002 /* attribute */
43
#define BNS_VERT_TYPE_TGROUP 0x0004
44
#define BNS_VERT_TYPE_C_POINT 0x0008
45
#define BNS_VERT_TYPE_C_GROUP 0x0010
46
#define BNS_VERT_TYPE_SUPER_TGROUP 0x0020
47
#define BNS_VERT_TYPE_TEMP 0x0040
49
#define BNS_VERT_TYPE__AUX 0x0080 /* vertex added to build charge substructures */
50
#define BNS_VERT_TYPE_C_NEGATIVE 0x0100 /* negative charge group; attribute, should be used with BNS_VERT_TYPE_C_GROUP */
51
#define BNS_VERT_TYPE_ACID 0x0200 /* only for this type are allowed paths: t_group-atom-c_group_neg (path_TACN) */
52
#define BNS_VERT_TYPE_CARBON_GR 0x0400 /* charge of carbon atom; should be used with BNS_VT_C_POS, BNS_VT_C_NEG */
53
#define BNS_VERT_TYPE_METAL_GR 0x0800 /* metal atom group; may be used alone or with BNS_VT_M_POS, BNS_VT_M_NEG */
55
#define BNS_VERT_TYPE_ANY_GROUP (BNS_VERT_TYPE_TGROUP | BNS_VERT_TYPE_C_GROUP | BNS_VERT_TYPE_SUPER_TGROUP)
57
/* InChI->Structure */
59
#define BNS_VT_C_POS BNS_VERT_TYPE_C_GROUP /* positive charge group, heteroat */
60
#define BNS_VT_C_NEG (BNS_VERT_TYPE_C_GROUP | BNS_VERT_TYPE_C_NEGATIVE) /* negative charge group, heteroat */
61
#define BNS_VT_C_POS_C (BNS_VT_C_POS | BNS_VERT_TYPE_CARBON_GR) /* positive charge group, C, Si, Ge, Sn */
62
#define BNS_VT_C_NEG_C (BNS_VT_C_NEG | BNS_VERT_TYPE_CARBON_GR) /* negative charge group, C, Si, Ge, Sn */
63
#define BNS_VT_C_POS_M (BNS_VT_C_POS | BNS_VERT_TYPE_METAL_GR) /* positive charge group, metal */
64
#define BNS_VT_C_NEG_M (BNS_VT_C_NEG | BNS_VERT_TYPE_METAL_GR) /* negative charge group, metal */
65
#define BNS_VT_M_GROUP BNS_VERT_TYPE_METAL_GR /* metal-group, flower vertex */
67
#define BNS_VT_C_POS_ALL (BNS_VERT_TYPE_SUPER_TGROUP | BNS_VERT_TYPE_C_GROUP) /* supergroup (+) */
68
#define BNS_VT_C_NEG_ALL (BNS_VT_C_POS_ALL | BNS_VERT_TYPE_C_NEGATIVE) /* supergroup (-) */
70
#define BNS_VT_CHRG_STRUCT (BNS_VERT_TYPE__AUX | BNS_VERT_TYPE_TEMP) /* ChargeStruct vertex */
71
#define BNS_VT_YVCONNECTOR BNS_VERT_TYPE__AUX /* group connection */
73
#define IS_BNS_VT_C_OR_CSUPER_GR(X) ((X) & BNS_VT_C_POS)
74
#define IS_BNS_VT_C_GR(X) (((X) & BNS_VT_C_POS_ALL) == BNS_VERT_TYPE_C_GROUP)
75
#define IS_BNS_VT_CM_GR(X) (((X) & BNS_VT_C_POS_M) == BNS_VT_C_POS_M) /* metal charge group */
76
#define IS_BNS_VT_M_GR(X) ((X) == BNS_VERT_TYPE_METAL_GR ) /* metal flower base or vertices */
77
#define IS_BNS_VT_YVCONNECTOR(X) (((X) & BNS_VERT_TYPE__AUX) && !((X) & BNS_VERT_TYPE_TEMP))
78
#define IS_BNS_VT_CHRG_STRUCT(X) (((X) & BNS_VERT_TYPE__AUX) && ((X) & BNS_VERT_TYPE_TEMP))
79
#define IS_BNS_VT_ATOM(X) ((X) & BNS_VERT_TYPE_ATOM)
81
#define BNS_ADD_SUPER_TGROUP 1 /* reserve one more edge for a t-group to connect to a single super-t-group */
82
#define NUM_KINDS_OF_GROUPS 2 /* 1 accounts for t-group kind, one more 1 accounts for c-group kind */
84
#define BNS_ADD_ATOMS 2 /* max. number of fictitious atoms to add (except t-gtoups) */
85
#define BNS_ADD_EDGES 1 /* max. number of edges to add to each atom (except edges to a t-group or c-group) */
87
typedef enum tagAltPathConst {
88
iALTP_MAX_LEN, /* 0 */
90
iALTP_PATH_LEN, /* 2 */
91
iALTP_START_ATOM, /* 3 */
92
iALTP_END_ATOM, /* 4 */
93
iALTP_NEIGHBOR, /* 5 */
94
iALTP_HDR_LEN = iALTP_NEIGHBOR
97
#define ALTP_PATH_LEN(altp) (altp)[iALTP_PATH_LEN].number /* number of bonds = number of atoms-1*/
98
#define ALTP_END_ATOM(altp) (altp)[iALTP_END_ATOM].number
99
#define ALTP_START_ATOM(altp) (altp)[iALTP_START_ATOM].number
100
#define ALTP_THIS_ATOM_NEIGHBOR(altp,X) (altp)[iALTP_NEIGHBOR+(X)].ineigh[0] /* 0 <= X < path_len */
101
#define ALTP_NEXT_ATOM_NEIGHBOR(altp,X) (altp)[iALTP_NEIGHBOR+(X)].ineigh[1]
102
#define ALTP_CUR_THIS_ATOM_NEIGHBOR(altp) (altp)[iALTP_NEIGHBOR+ALTP_PATH_LEN(altp)].ineigh[0] /* 0 <= X < path_len */
103
#define ALTP_CUR_NEXT_ATOM_NEIGHBOR(altp) (altp)[iALTP_NEIGHBOR+ALTP_PATH_LEN(altp)].ineigh[1]
104
#define ALTP_NEXT(altp) (++ALTP_PATH_LEN(altp))
105
#define ALTP_PREV(altp) (--ALTP_PATH_LEN(altp))
106
#define ALTP_MAY_ADD(altp) (iALTP_NEIGHBOR + (altp)[iALTP_PATH_LEN].number < (altp)[iALTP_MAX_LEN].number)
107
#define ALTP_ALLOCATED_LEN(altp) (altp)[iALTP_MAX_LEN].number
108
#define ALTP_DELTA(altp) (altp)[iALTP_FLOW].flow[0]
109
#define ALTP_OVERFLOW(altp) (altp)[iALTP_FLOW].flow[1]
115
#define BLOSSOM_BASE -1
117
#define ADD_CAPACITY_RADICAL 1 /* add capacity to radical */
119
#define MAX_BOND_EDGE_CAP 2 /* triple bond */
120
#define AROM_BOND_EDGE_CAP 1
121
#define MAX_TGROUP_EDGE_CAP 2 /* -NH2 provides max. capacity */
124
#define EDGE_FLOW_ST_MASK 0x3fff /* mask for flow */
125
#define EDGE_FLOW_ST_PATH 0x4000 /* mark: the edge belongs to the augmenting path */
127
/* edges between other vertices */
128
/* EdgeFlow defined as S_SHORT; change from S_CHAR made 9-23-2005 */
129
#define EDGE_FLOW_MASK 0x3fff /* mask for flow */
130
#define EDGE_FLOW_PATH 0x4000 /* mark: the edge belongs to the augmenting path */
132
/*********************************************************************************/
133
#if( ADD_CAPACITY_RADICAL == 1 ) /* { */
134
/* -- do not treat triplets as moving dots -- 2004-02-18 --
135
#define MAX_AT_FLOW(X) (((X).chem_bonds_valence - (X).valence)+\
136
((is_centerpoint_elem((X).el_number)||get_endpoint_valence((X).el_number))?\
137
(((X).radical==RADICAL_DOUBLET)+2*((X).radical==RADICAL_TRIPLET)):0))
139
#define MAX_AT_FLOW(X) (((X).chem_bonds_valence - (X).valence)+\
140
((is_centerpoint_elem((X).el_number)||get_endpoint_valence((X).el_number))?\
141
(((X).radical==RADICAL_DOUBLET)/*+2*((X).radical==RADICAL_TRIPLET)*/):0))
144
#else /* } ADD_CAPACITY_RADICAL { */
146
#define MAX_AT_FLOW(X) (((X).chem_bonds_valence - (X).valence)
148
#endif /* } ADD_CAPACITY_RADICAL */
150
/**************************** BNS_EDGE ************************************/
151
typedef struct BnsEdge {
152
AT_NUMB neighbor1; /* the smaller neighbor */
153
AT_NUMB neighbor12; /* neighbor1 ^ neighbor2 */
154
AT_NUMB neigh_ord[2]; /* ordering number of the neighbor: [0]: at<neighbor, [1]: at>neighbor */
155
EdgeFlow cap; /* Edge capacity */
156
EdgeFlow cap0; /* Initial edge capacity */
157
EdgeFlow flow; /* Edge flow */
158
EdgeFlow flow0; /* Initial flow */
160
S_CHAR pass; /* number of times changed in AugmentEdge() */
164
/**************************** BNS_ST_EDGE ************************************/
165
typedef struct BnsStEdge {
166
VertexFlow cap; /* Edge capacity */
167
VertexFlow cap0; /* Initial edge capacity */
168
VertexFlow flow; /* Edge flow */
169
VertexFlow flow0; /* Initial edge flow */
170
S_CHAR pass; /* number of times changed in AugmentEdge() */
174
/**************************** BNS_VERTEX ************************************/
175
typedef struct BnsVertex {
177
BNS_ST_EDGE st_edge; /* 0,1 capacity and flow of the edge to s or t */
178
AT_NUMB type; /* 2, atom, t-group, or added atom: BNS_VERT_TYPE_TGROUP, etc. */
179
AT_NUMB num_adj_edges; /* 3, actual number of neighbors incl. t-groups, excl. s or t */
180
AT_NUMB max_adj_edges; /* 4, including reserved */
181
/*S_CHAR path_neigh[2];*/ /* 5 found path information */
182
/* indexes of Edges */
183
BNS_IEDGE *iedge; /* 6 a pointer to the array of edge indexes adjacent to this vertex */
186
/**************************** BNS_ALT_PATH ************************************/
187
typedef union BnsAltPath {
193
/**************************** BN_STRUCT ************************************/
194
typedef struct BalancedNetworkStructure {
196
int num_atoms; /* number of real atoms */
197
/*int len_atoms; */ /* size of filled with real atoms portion of the BNS_VERTEX data */
198
int num_added_atoms; /* number of added fictitious atoms */
199
int nMaxAddAtoms; /* max. number of atoms to add (not including t-groups) */
200
int num_c_groups; /* number of added c-groups */
201
int num_t_groups; /* number of added t-groups */
202
int num_vertices; /* total number currently in effect; includes t-groups and added atoms */
203
/*int len_vertices; */ /* allocation size for BNS_VERTEX data */
204
int num_bonds; /* number of real bonds/2 = number of edges between real atoms */
205
int num_edges; /* number of currently in effect */
206
int num_iedges; /* added 9-16-2005; used only in InChI Reversing */
207
int num_added_edges; /* number of added edges (not including edges to t-groups) */
208
int nMaxAddEdges; /* max. number edges of add to each atom (not including edges to t-groups) */
210
int max_vertices; /* allocation size for BNS_VERTEX structures */
211
int max_edges; /* allocation size for edge[]; iedge has length 2*max_edges */
212
int max_iedges; /* allocation size for iedge */
214
int tot_st_cap; /* not used, only calculated */
215
int tot_st_flow; /* not used, only calculated */
217
int len_alt_path; /* length of alt_path[] */
219
int bNotASimplePath; /* alternating path traversed same bond 2 times in opposite directions */
220
int bChangeFlow; /* actually change flow */
222
BNS_VERTEX *vert; /* vertices */
223
BNS_EDGE *edge; /* edges */
225
BNS_ALT_PATH *alt_path; /* current altp[] element */
226
BNS_ALT_PATH *altp[BN_MAX_ALTP]; /* keep alt. paths */
231
INCHI_MODE *pbTautFlags; /* carry it through all functions; never NULL */
232
INCHI_MODE *pbTautFlagsDone; /* carry it through all functions; never NULL */
233
AT_NUMB type_TACN; /* BNS_VERT_TYPE_ACID: if non-zero than only for it path type_T-type_TACN-type_CN allowed */
234
AT_NUMB type_T; /* BNS_VERT_TYPE_TGROUP */
235
AT_NUMB type_CN; /* BNS_VERT_TYPE_C_GROUP | BNS_VERT_TYPE_C_NEGATIVE */
236
S_CHAR edge_forbidden_mask;
240
/********************* BN_DATA *******************************************/
241
typedef enum tagBnsRadSrchMode {
242
RAD_SRCH_NORM = 0, /* normal search for normalization */
243
RAD_SRCH_FROM_FICT = 1 /* search from fict. vertices to atoms */
245
typedef struct BalancedNetworkData {
246
Vertex *BasePtr; /*[MAX_VERTEX]; pointer toward the base of C(v) */
247
Edge *SwitchEdge; /*[MAX_VERTEX]; a pair of vertices and an edge, implemented here as [*][2] array */
248
S_CHAR *Tree; /*[MAX_VERTEX]; indicates presence in ScanQ, T, T', s-reachability */
249
Vertex *ScanQ; /*[MAX_VERTEX]; contains the set S of s-reachable vertices */
250
int QSize; /* index of the last element added to ScanQ */
251
Vertex *Pu; /*[MAX_VERTEX/2+1] */
252
Vertex *Pv; /*[MAX_VERTEX/2+1] */
253
int max_num_vertices; /* allocation size of all except Pu, Pv */
254
int max_len_Pu_Pv; /* allocation size of Pu and Pv */
255
#if( BNS_RAD_SEARCH == 1 )
256
Vertex *RadEndpoints; /*[MAX_VERTEX*/
257
int nNumRadEndpoints;
261
BRS_MODE bRadSrchMode; /* 1 => connect fict. vertices-radicals to the accessible atoms */
265
/* internal array size */
266
#define MAX_ALT_AATG_ARRAY_LEN 127
267
/* detected endpoint markings */
268
#define AATG_MARK_IN_PATH 1 /* atom in path detected by the BNS */
269
#define AATG_MARK_WAS_IN_PATH 2 /* found to be in path before next level */
271
#define AATG_MARK_MAIN_TYPE 4 /* atom O-"salt" */
272
#define AATG_MARK_OTHER_TYPE 8 /* other atom to be tested */
274
struct tagTautomerGroupsInfo; /* forward declaration */
276
/******************** atoms in alt path through taut group ****************/
277
typedef struct BN_AtomsAtTautGroup {
280
int nNumMainAdj2Tgroup;
281
int nNumOthersAdj2Tgroup;
282
AT_NUMB *nEndPoint; /* original t-group number */
283
S_CHAR *nMarkedAtom; /* atom mark, see AATG_MARK_* */
285
struct tagTautomerGroupsInfo *t_group_info;
289
/************ store changes in flow and capacity to test a bond ****************/
291
typedef struct tagBNS_FLOW_CHANGES {
304
#define ALT_PATH_MODE_TAUTOM 1
305
#define ALT_PATH_MODE_CHARGE 2
306
#define ALT_PATH_MODE_4_SALT 3 /* mark alt bonds along the path */
307
#define ALT_PATH_MODE_4_SALT2 4 /* mark alt bonds along the path, path to taut. group fict. vertex if exists */
308
#define ALT_PATH_MODE_REM2H_CHG 5 /* remove 2 H along alt. path AH-=-BH => A=-=B and change bonds to alternating */
309
#define ALT_PATH_MODE_ADD2H_CHG 6 /* add 2 H along alt. path A=-=B => AH-=-BH and change bonds to alternating */
310
#define ALT_PATH_MODE_REM2H_TST 7 /* test-remove 2 H along alt. path AH-=-BH => A=-=B; restore changed bonds */
311
#define ALT_PATH_MODE_ADD2H_TST 8 /* test-add 2 H along alt. path A=-=B => AH-=-BH; restore changed bonds */
312
#define ALT_PATH_MODE_REM_PROTON 9 /* remove proton, adjust bonds, charges, H-counts 2004-03-05 */
314
#ifndef INCHI_ALL_CPP
321
/*********************************************************************************
323
1 => change flow inside the BNS search
324
3 => change flow inside the BNS search and undo the flow change in the BNS structure here
325
4 => change bonds in the structure according to the flow
326
8 => make altern. bonds in the structure
328
Note: (bChangeFlow & 1) == 1 is needed for multiple runs
329
**********************************************************************************/
331
/* "EF" = "Edge Flow" */
332
#define BNS_EF_CHNG_FLOW 1 /* change Balanced Network (BN) flow inside the BNS search */
333
#define BNS_EF_RSTR_FLOW 2 /* undo BN flow changes after BNS */
334
#define BNS_EF_CHNG_RSTR (BNS_EF_CHNG_FLOW | BNS_EF_RSTR_FLOW)
335
#define BNS_EF_CHNG_BONDS 4 /* change bonds in the structure according to the BN flow */
336
#define BNS_EF_ALTR_BONDS 8 /* make altern. bonds in the structure if the flow has changed */
337
#define BNS_EF_UPD_RAD_ORI 16 /* update BN flow0 & Atom radical values:
338
flow0 := flow, radical:=st_cap - st_flow */
339
#define BNS_EF_SET_NOSTEREO 32 /* in combination with BNS_EF_ALTR_BONDS only:
340
ALT12 bond cannot be stereogenic */
341
#define BNS_EF_UPD_H_CHARGE 64 /* update charges and H-counts according to change flow to c- and t-group vertices */
343
#define BNS_EF_SAVE_ALL (BNS_EF_CHNG_FLOW | BNS_EF_CHNG_BONDS | BNS_EF_UPD_RAD_ORI)
344
#define BNS_EF_ALTR_NS (BNS_EF_ALTR_BONDS | BNS_EF_SET_NOSTEREO)
346
#define BNS_EF_RAD_SRCH 128 /* search for rafical paths closures */
350
int nExists2AtMoveAltPath( struct BalancedNetworkStructure *pBNS, struct BalancedNetworkData *pBD,
351
struct BN_AtomsAtTautGroup *pAATG, inp_ATOM *at, int num_atoms,
352
int jj2, int jj1, struct tagSaltChargeCandidate *s_candidate, int nNumCandidates,
353
AT_NUMB *nForbiddenAtom, int nNumForbiddenAtoms);
354
int bExistsAltPath( struct BalancedNetworkStructure *pBNS, struct BalancedNetworkData *pBD,
355
struct BN_AtomsAtTautGroup *pAATG, inp_ATOM *at, int num_atoms, int nVertDoubleBond, int nVertSingleBond, int path_type );
356
int bExistsAnyAltPath( struct BalancedNetworkStructure *pBNS, struct BalancedNetworkData *pBD,
357
inp_ATOM *at, int num_atoms, int nVertDoubleBond, int nVertSingleBond, int path_type );
358
int AddTGroups2BnStruct( struct BalancedNetworkStructure *pBNS, inp_ATOM *at, int num_atoms,
359
struct tagTautomerGroupsInfo *tgi );
360
int AddSuperTGroup2BnStruct( struct BalancedNetworkStructure *pBNS, inp_ATOM *at, int num_atoms,
361
struct tagTautomerGroupsInfo *tgi );
362
int AddCGroups2BnStruct( struct BalancedNetworkStructure *pBNS, inp_ATOM *at, int num_atoms,
363
struct tagChargeGroupsInfo *cgi );
365
int ReInitBnStruct( struct BalancedNetworkStructure *pBNS, inp_ATOM *at, int num_at, int bRemoveGroupsFromAtoms );
366
int ReInitBnStructAddGroups( struct BalancedNetworkStructure *pBNS, inp_ATOM *at, int num_atoms,
367
struct tagTautomerGroupsInfo *tgi, struct tagChargeGroupsInfo *cgi );
370
int DisconnectTestAtomFromTGroup( struct BalancedNetworkStructure *pBNS, int v1, int *pv2, BNS_FLOW_CHANGES *fcd );
371
int DisconnectTGroupFromSuperTGroup( struct BalancedNetworkStructure *pBNS, int v1, int *pv1, int *pv2,
372
BNS_FLOW_CHANGES *fcd );
373
int ReconnectTestAtomToTGroup( struct BalancedNetworkStructure *pBNS, int v1, int v2, int ie, BNS_FLOW_CHANGES *fcd );
375
int bIsHardRemHCandidate( inp_ATOM *at, int i, int *cSubType );
377
/* moved from ichi_bns.c 2005-08-23 */
378
int RunBalancedNetworkSearch( BN_STRUCT *pBNS, BN_DATA *pBD, int bChangeFlow );
379
BN_STRUCT* AllocateAndInitBnStruct( inp_ATOM *at, int num_atoms, int nMaxAddAtoms, int nMaxAddEdges, int max_altp, int *num_changed_bonds );
380
BN_STRUCT* DeAllocateBnStruct( BN_STRUCT *pBNS );
381
int ReInitBnStructAltPaths( BN_STRUCT *pBNS );
382
int ReInitBnStructForMoveableAltBondTest( BN_STRUCT *pBNS, inp_ATOM *at, int num_atoms );
383
void ClearAllBnDataVertices( Vertex *v, Vertex value, int size );
384
void ClearAllBnDataEdges( Edge *e, Vertex value, int size );
385
BN_DATA *DeAllocateBnData( BN_DATA *pBD );
386
BN_DATA *AllocateAndInitBnData( int max_num_vertices );
387
int ReInitBnData( BN_DATA *pBD );
388
int SetForbiddenEdges( BN_STRUCT *pBNS, inp_ATOM *at, int num_atoms, int edge_forbidden_mask );
389
/* main function: find augmenting path */
390
int BalancedNetworkSearch ( BN_STRUCT* pBNS, BN_DATA *pBD, int bChangeFlow );
392
int SetRadEndpoints( BN_STRUCT *pBNS, BN_DATA *pBD, BRS_MODE bRadSrchMode );
393
int RemoveRadEndpoints( BN_STRUCT *pBNS, BN_DATA *pBD, inp_ATOM *at );
395
int AddRemoveProtonsRestr( inp_ATOM *at, int num_atoms, int *num_protons_to_add,
396
int nNumProtAddedByRestr, INCHI_MODE bNormalizationFlags,
397
int num_tg, int nChargeRevrs, int nChargeInChI );
398
int AddRemoveIsoProtonsRestr( inp_ATOM *at, int num_atoms, NUM_H num_protons_to_add[], int num_tg );
401
#ifndef INCHI_ALL_CPP
408
#endif /* __INCHI_BNS_H___ */
added
removed
src/formats/inchi/ichi_bns.h
