1 // $Id$
2 //
3 // Copyright (C) 2003-2010 greg Landrum and Rational Discovery LLC
4 //
5 // @@ All Rights Reserved @@
6 // This file is part of the RDKit.
7 // The contents are covered by the terms of the BSD license
8 // which is included in the file license.txt, found at the root
9 // of the RDKit source tree.
10 //
11 #include <RDGeneral/types.h>
12 #include <cmath>
13 #include <Geometry/point.h>
14 #include <Geometry/Transform2D.h>
15 #include "DepictUtils.h"
16 #include <iostream>
17 #include <RDGeneral/Invariant.h>
18 #include <algorithm>
19
20 namespace RDDepict {
21 double BOND_LEN = 1.5;
22 double COLLISION_THRES = 0.70;
23 double BOND_THRES = 0.50;
24 double ANGLE_OPEN = 0.1222; // that is about 7 deg
25 unsigned int MAX_COLL_ITERS = 15;
26 double HETEROATOM_COLL_SCALE = 1.3;
27 unsigned int NUM_BONDS_FLIPS = 3;
28
embedRing(const RDKit::INT_VECT & ring)29 RDGeom::INT_POINT2D_MAP embedRing(const RDKit::INT_VECT &ring) {
30 // The process here is very straight forward
31 // we take the center of the ring to lies at the origin put the first
32 // point at the origin and then sweep
33 // anticlockwise so by an angle A = 360/n for the next point
34 // the length of the arm (l) we want to sweep is easy to compute given the
35 // bond length (b) we want to use for each bond in the ring (for now
36 // we will assume that this bond length is the same for all bonds in the ring
37 // l = b/sqrt(2*(1 - cos(A))
38 // the above formula derives from the triangle formula, where side 'c' is
39 // given
40 // in terms of sides 'a' and 'b' as
41 // c = a^2 + b^2 - 2.a.b.cos(A)
42 // where A is the angle between a and b
43
44 // compute the sweep angle
45 unsigned int na = ring.size();
46 double ang = 2 * M_PI / na;
47
48 // compute the arm length
49 double al = BOND_LEN / (sqrt(2 * (1 - cos(ang))));
50
51 RDGeom::INT_POINT2D_MAP res;
52
53 unsigned int i, aid;
54 double x, y;
55
56 for (i = 0; i < na; i++) {
57 x = al * cos(i * ang);
58 y = al * sin(i * ang);
59 RDGeom::Point2D loc(x, y);
60 aid = ring[i];
61 res[aid] = loc;
62 }
63 return res;
64 }
65
transformPoints(RDGeom::INT_POINT2D_MAP & nringCor,const RDGeom::Transform2D & trans)66 void transformPoints(RDGeom::INT_POINT2D_MAP &nringCor,
67 const RDGeom::Transform2D &trans) {
68 RDGeom::INT_POINT2D_MAP_I nrci;
69 for (nrci = nringCor.begin(); nrci != nringCor.end(); nrci++) {
70 RDGeom::Point2D loc = nrci->second;
71 trans.TransformPoint(loc);
72 nrci->second = loc;
73 }
74 }
75
computeBisectPoint(const RDGeom::Point2D & rcr,double ang,const RDGeom::Point2D & nb1,const RDGeom::Point2D & nb2)76 RDGeom::Point2D computeBisectPoint(const RDGeom::Point2D &rcr, double ang,
77 const RDGeom::Point2D &nb1,
78 const RDGeom::Point2D &nb2) {
79 RDGeom::Point2D cloc = nb1;
80 cloc += nb2;
81 cloc *= 0.5;
82 if (ang > M_PI) {
83 // invert the cloc
84 cloc -= rcr;
85 cloc *= -1.0;
86 cloc += rcr;
87 }
88 return cloc;
89 }
90
reflectPoint(const RDGeom::Point2D & point,const RDGeom::Point2D & loc1,const RDGeom::Point2D & loc2)91 RDGeom::Point2D reflectPoint(const RDGeom::Point2D &point,
92 const RDGeom::Point2D &loc1,
93 const RDGeom::Point2D &loc2) {
94 RDGeom::Point2D org(0.0, 0.0);
95 RDGeom::Point2D xaxis(1.0, 0.0);
96 RDGeom::Point2D cent = (loc1 + loc2);
97 cent *= 0.5;
98
99 RDGeom::Transform2D trans;
100 trans.SetTransform(org, xaxis, cent, loc1);
101
102 /// reverse transform
103 RDGeom::Transform2D itrans;
104 itrans.SetTransform(cent, loc1, org, xaxis);
105
106 RDGeom::INT_POINT2D_MAP_I nci;
107 RDGeom::Point2D res;
108 res = point;
109 trans.TransformPoint(res);
110 res.y = -res.y;
111 itrans.TransformPoint(res);
112 return res;
113 }
114
reflectPoints(RDGeom::INT_POINT2D_MAP & coordMap,const RDGeom::Point2D & loc1,const RDGeom::Point2D & loc2)115 void reflectPoints(RDGeom::INT_POINT2D_MAP &coordMap,
116 const RDGeom::Point2D &loc1, const RDGeom::Point2D &loc2) {
117 RDGeom::INT_POINT2D_MAP_I nci;
118 for (nci = coordMap.begin(); nci != coordMap.end(); nci++) {
119 nci->second = reflectPoint(nci->second, loc1, loc2);
120 }
121 }
122
setNbrOrder(unsigned int aid,const RDKit::INT_VECT & nbrs,const RDKit::ROMol & mol)123 RDKit::INT_VECT setNbrOrder(unsigned int aid, const RDKit::INT_VECT &nbrs,
124 const RDKit::ROMol &mol) {
125 PRECONDITION(aid < mol.getNumAtoms(), "");
126 PR_QUEUE subsAid;
127 int ref = -1;
128 RDKit::ROMol::ADJ_ITER nbrIdx, endNbrs;
129 boost::tie(nbrIdx, endNbrs) = mol.getAtomNeighbors(mol.getAtomWithIdx(aid));
130 // find the neighbor of aid that is not in nbrs i.e. atom A from the comments
131 // in the header file
132 // and the store the pair <degree, aid> in the order of increasing degree
133 while (nbrIdx != endNbrs) {
134 // We used to use degree here instead we will start using the CIP rank here
135 if (std::find(nbrs.begin(), nbrs.end(), static_cast<int>(*nbrIdx)) ==
136 nbrs.end()) {
137 ref = (*nbrIdx);
138 }
139 nbrIdx++;
140 }
141
142 RDKit::INT_VECT thold = nbrs;
143 if (ref >= 0) {
144 thold.push_back(ref);
145 }
146 // we should be here unless we have more than 3 atoms to worry about
147 CHECK_INVARIANT(thold.size() > 3, "");
148 thold = rankAtomsByRank(mol, thold);
149
150 // swap the position of the 3rd to last and second to last items in sorted
151 // list
152 unsigned int ln = thold.size();
153 int tint = thold[ln - 3];
154 thold[ln - 3] = thold[ln - 2];
155 thold[ln - 2] = tint;
156
157 // go clock wise along the list from this position for the arranged neighbor
158 // list
159 RDKit::INT_VECT res;
160 res.reserve(thold.size());
161 auto pos = std::find(thold.begin(), thold.end(), ref);
162 if (pos != thold.end()) {
163 res.insert(res.end(), pos + 1, thold.end());
164 }
165 if (pos != thold.begin()) {
166 res.insert(res.end(), thold.begin(), pos);
167 }
168
169 POSTCONDITION(res.size() == nbrs.size(), "");
170 return res;
171 }
172
pickFirstRingToEmbed(const RDKit::ROMol & mol,const RDKit::VECT_INT_VECT & fusedRings)173 int pickFirstRingToEmbed(const RDKit::ROMol &mol,
174 const RDKit::VECT_INT_VECT &fusedRings) {
175 // ok this is what we will do here
176 // we will pick the ring with the smallest number of substituents
177 int res = -1;
178 unsigned int maxSize = 0;
179 int subs, minsubs = static_cast<int>(1e8);
180 int cnt = 0;
181 for (const auto &fusedRing : fusedRings) {
182 subs = 0;
183 for (auto rii : fusedRing) {
184 int deg = mol.getAtomWithIdx(rii)->getDegree();
185 if (deg > 2) {
186 subs++;
187 }
188 }
189 if (subs < minsubs) {
190 res = cnt;
191 minsubs = subs;
192 maxSize = fusedRing.size();
193 } else if (subs == minsubs) {
194 if (fusedRing.size() > maxSize) {
195 res = cnt;
196 maxSize = fusedRing.size();
197 }
198 }
199 cnt++;
200 }
201 return res;
202 }
203
findNextRingToEmbed(const RDKit::INT_VECT & doneRings,const RDKit::VECT_INT_VECT & fusedRings,int & nextId)204 RDKit::INT_VECT findNextRingToEmbed(const RDKit::INT_VECT &doneRings,
205 const RDKit::VECT_INT_VECT &fusedRings,
206 int &nextId) {
207 // REVIEW: We are changing this after Issue166
208 // Originally the ring that have maximum number of atoms in common with the
209 // atoms
210 // that have already been embedded will be the ring that will get embedded.
211 // But
212 // if we can find a ring with two atoms in common with the embedded atoms, we
213 // will
214 // choose that first before systems with more than 2 atoms in common. Cases
215 // with two atoms
216 // in common are in general flat systems to start with and can be embedded
217 // cleanly.
218 // when there are more than 2 atoms in common, these are most likely bridged
219 // systems, which are
220 // screwed up anyway, might as well screw them up later
221 // if we do not have a system with two rings in common then we will return the
222 // ring with max,
223 // common atoms
224 PRECONDITION(doneRings.size() > 0, "");
225 PRECONDITION(fusedRings.size() > 1, "");
226
227 RDKit::INT_VECT commonAtoms, res, doneAtoms, notDone;
228 for (int i = 0; i < rdcast<int>(fusedRings.size()); i++) {
229 if (std::find(doneRings.begin(), doneRings.end(), i) == doneRings.end()) {
230 notDone.push_back(i);
231 }
232 }
233
234 RDKit::Union(fusedRings, doneAtoms, ¬Done);
235
236 int maxCommonAtoms = 0;
237
238 int currRingId = 0;
239 for (const auto &fusedRing : fusedRings) {
240 if (std::find(doneRings.begin(), doneRings.end(), currRingId) !=
241 doneRings.end()) {
242 currRingId++;
243 continue;
244 }
245 commonAtoms.clear();
246 int numCommonAtoms = 0;
247 for (auto rii : fusedRing) {
248 if (std::find(doneAtoms.begin(), doneAtoms.end(), (rii)) !=
249 doneAtoms.end()) {
250 commonAtoms.push_back(rii);
251 numCommonAtoms++;
252 }
253 }
254 if (numCommonAtoms == 2) {
255 // if we found a ring with two atoms in common get out
256 nextId = currRingId;
257 return commonAtoms; // FIX: this causes the rendering to be non-canonical
258 }
259 if (numCommonAtoms > maxCommonAtoms) {
260 maxCommonAtoms = numCommonAtoms;
261 nextId = currRingId;
262 res = commonAtoms;
263 }
264 currRingId++;
265 }
266 // here is an additional constrain we will put on the common atoms
267 // it is quite likely that the common atoms form a chain (it is possible we
268 // can
269 // construct some weird cases where this does not hold true - but for now we
270 // will
271 // assume this is true. However the IDs in the res may not be in the order of
272 // going
273 // from one end of the chain to the other - here is an example
274 // C1CCC(CC12)CCC2 - two rings here with three atoms in common
275 // let ring1:(0,1,2,3,4,5) be a ring that is already embedded, then let
276 // ring2:(4,3,6,7,8,5) be the ring
277 // that we found to be the next ring we should embed. The commonAtoms are
278 // (4,3,5) - note that
279 // they will be in this order since the rings are always traversed in order.
280 // Now we would like these
281 // common atoms to be returned in the order (5,4,3) - then we have a
282 // continuous chain, we can
283 // do this by simply looking at the original ring order (4,3,6,7,8,5) and
284 // observing that 5 need to come to
285 // the front
286
287 // find out how many atoms from the end we need to move to the front
288 unsigned int cmnLst = 0;
289 unsigned int nCmn = res.size();
290 for (unsigned int i = 0; i < nCmn; i++) {
291 if (res[i] == fusedRings[nextId][i]) {
292 cmnLst++;
293 } else {
294 break;
295 }
296 }
297 // now do the moving if we have to
298 if ((cmnLst > 0) && (cmnLst < res.size())) {
299 RDKit::INT_VECT tempV = res;
300
301 for (unsigned int i = cmnLst; i < nCmn; i++) {
302 res[i - cmnLst] = tempV[i];
303 }
304 unsigned int nMov = nCmn - cmnLst;
305 for (unsigned int i = 0; i < cmnLst; i++) {
306 res[nMov + i] = tempV[i];
307 }
308 }
309
310 POSTCONDITION(res.size() > 0, "");
311 return res;
312 }
313
getAllRotatableBonds(const RDKit::ROMol & mol)314 RDKit::INT_VECT getAllRotatableBonds(const RDKit::ROMol &mol) {
315 RDKit::INT_VECT res;
316 RDKit::ROMol::ConstBondIterator bondIt;
317 for (bondIt = mol.beginBonds(); bondIt != mol.endBonds(); bondIt++) {
318 int bid = (*bondIt)->getIdx();
319 if (((*bondIt)->getStereo() <= RDKit::Bond::STEREOANY) &&
320 (!(mol.getRingInfo()->numBondRings(bid)))) {
321 res.push_back(bid);
322 }
323 }
324 return res;
325 }
326
getRotatableBonds(const RDKit::ROMol & mol,unsigned int aid1,unsigned int aid2)327 RDKit::INT_VECT getRotatableBonds(const RDKit::ROMol &mol, unsigned int aid1,
328 unsigned int aid2) {
329 PRECONDITION(aid1 < mol.getNumAtoms(), "");
330 PRECONDITION(aid2 < mol.getNumAtoms(), "");
331
332 RDKit::INT_LIST path = RDKit::MolOps::getShortestPath(mol, aid1, aid2);
333 RDKit::INT_VECT res;
334 if (path.size() >= 4) {
335 // remove the first atom (aid1) and last atom (aid2)
336 CHECK_INVARIANT(static_cast<unsigned int>(path.front()) == aid1,
337 "bad first element");
338 path.pop_front();
339 CHECK_INVARIANT(static_cast<unsigned int>(path.back()) == aid2,
340 "bad last element");
341 path.pop_back();
342
343 RDKit::INT_LIST_CI pi = path.begin();
344 int pid = (*pi);
345 ++pi;
346 while (pi != path.end()) {
347 int aid = (*pi);
348 const RDKit::Bond *bond = mol.getBondBetweenAtoms(pid, aid);
349 int bid = bond->getIdx();
350 if ((bond->getStereo() <= RDKit::Bond::STEREOANY) &&
351 (!(mol.getRingInfo()->numBondRings(bid)))) {
352 res.push_back(bid);
353 }
354 pid = aid;
355 ++pi;
356 }
357 }
358 return res;
359 }
360
getNbrAtomAndBondIds(unsigned int aid,const RDKit::ROMol * mol,RDKit::INT_VECT & aids,RDKit::INT_VECT & bids)361 void getNbrAtomAndBondIds(unsigned int aid, const RDKit::ROMol *mol,
362 RDKit::INT_VECT &aids, RDKit::INT_VECT &bids) {
363 CHECK_INVARIANT(mol, "");
364 unsigned int na = mol->getNumAtoms();
365 URANGE_CHECK(aid, na);
366
367 RDKit::ROMol::ADJ_ITER nbrIdx, endNbrs;
368 boost::tie(nbrIdx, endNbrs) = mol->getAtomNeighbors(mol->getAtomWithIdx(aid));
369
370 unsigned int ai, bi;
371 while (nbrIdx != endNbrs) {
372 ai = (*nbrIdx);
373 bi = mol->getBondBetweenAtoms(aid, ai)->getIdx();
374 aids.push_back(ai);
375 bids.push_back(bi);
376 nbrIdx++;
377 }
378 }
379
380 // find pairs of bonds that can be permuted at a non-ring degree 4
381 // node. This function will return only those pairs that cannot be
382 // permuted by flipping a rotatable bond
383 //
384 // D
385 // |
386 // b3
387 // |
388 // A-b1-B-b2-C
389 // |
390 // b4
391 // |
392 // E
393 // For example in the above situation on the pairs (b1, b3) and (b1, b4) will be
394 // returned
395 // All other permutations can be achieved via a rotatable bond flip.
findBondsPairsToPermuteDeg4(const RDGeom::Point2D & center,const RDKit::INT_VECT & nbrBids,const VECT_C_POINT & nbrLocs)396 INT_PAIR_VECT findBondsPairsToPermuteDeg4(const RDGeom::Point2D ¢er,
397 const RDKit::INT_VECT &nbrBids,
398 const VECT_C_POINT &nbrLocs) {
399 INT_PAIR_VECT res;
400
401 // make sure there are four of them
402 CHECK_INVARIANT(nbrBids.size() == 4, "");
403 CHECK_INVARIANT(nbrLocs.size() == 4, "");
404
405 std::vector<RDGeom::Point2D> nbrPts;
406 nbrPts.reserve(nbrLocs.size());
407 for (const auto &nloc : nbrLocs) {
408 RDGeom::Point2D v = (*nloc) - center;
409 nbrPts.push_back(v);
410 }
411
412 // now find the lay out of the bonds and return the bonds that are 90deg to
413 // the
414 // the bond to the first neighbor; i.e. we want to find b3 and b4 in the above
415 // picture
416 double dp1 = nbrPts[0].dotProduct(nbrPts[1]);
417 if (fabs(dp1) < 1.e-3) {
418 // the first two vectors are perpendicular to each other. We now have b1 and
419 // b3 we need to
420 // find b4
421 INT_PAIR p1(nbrBids[0], nbrBids[1]);
422 res.push_back(p1);
423
424 double dp2 = nbrPts[0].dotProduct(nbrPts[2]);
425 if (fabs(dp2) < 1.e-3) {
426 // now we found b4 as well return the results
427 INT_PAIR p2(nbrBids[0], nbrBids[2]);
428 res.push_back(p2);
429 } else {
430 // bids[0] and bids[2] are opposite to each other and we know bids[1] is
431 // perpendicular to bids[0]. So bids[3] is also perpendicular to bids[0]
432 INT_PAIR p2(nbrBids[0], nbrBids[3]);
433 res.push_back(p2);
434 }
435 return res;
436 } else {
437 // bids[0] and bids[1] are opposite to each other, so bids[2] and bids[3]
438 // must
439 // be perpendicular to bids[0]
440 INT_PAIR p1(nbrBids[0], nbrBids[2]);
441 res.push_back(p1);
442 INT_PAIR p2(nbrBids[0], nbrBids[3]);
443 res.push_back(p2);
444 return res;
445 }
446 }
447
448 // compare the first elements of two pairs of integers/
449
_pairCompDescending(const INT_PAIR & arg1,const INT_PAIR & arg2)450 int _pairCompDescending(const INT_PAIR &arg1, const INT_PAIR &arg2) {
451 return (arg1.first != arg2.first ? arg1.first > arg2.first
452 : arg1.second > arg2.second);
453 }
454
_pairCompAscending(const INT_PAIR & arg1,const INT_PAIR & arg2)455 int _pairCompAscending(const INT_PAIR &arg1, const INT_PAIR &arg2) {
456 return (arg1.first != arg2.first ? arg1.first < arg2.first
457 : arg1.second < arg2.second);
458 }
459
460 template <class T>
rankAtomsByRank(const RDKit::ROMol & mol,const T & commAtms,bool ascending)461 T rankAtomsByRank(const RDKit::ROMol &mol, const T &commAtms, bool ascending) {
462 size_t natms = commAtms.size();
463 INT_PAIR_VECT rankAid;
464 rankAid.reserve(natms);
465 T res;
466 typename T::const_iterator ci;
467 for (ci = commAtms.begin(); ci != commAtms.end(); ci++) {
468 unsigned int rank;
469 const RDKit::Atom *at = mol.getAtomWithIdx(*ci);
470 if (at->hasProp(RDKit::common_properties::_CIPRank)) {
471 at->getProp(RDKit::common_properties::_CIPRank, rank);
472 } else {
473 rank = mol.getNumAtoms() * getAtomDepictRank(at) + (*ci);
474 }
475 rankAid.push_back(std::make_pair(rank, (*ci)));
476 }
477 if (ascending) {
478 std::stable_sort(rankAid.begin(), rankAid.end(), _pairCompAscending);
479 } else {
480 std::stable_sort(rankAid.begin(), rankAid.end(), _pairCompDescending);
481 }
482 INT_PAIR_VECT_CI rai;
483 for (rai = rankAid.begin(); rai != rankAid.end(); rai++) {
484 res.push_back(rai->second);
485 }
486
487 return res;
488 }
489
490 template RDKit::INT_VECT rankAtomsByRank(const RDKit::ROMol &mol,
491 const RDKit::INT_VECT &commAtms,
492 bool ascending);
493 template RDKit::INT_DEQUE rankAtomsByRank(const RDKit::ROMol &mol,
494 const RDKit::INT_DEQUE &commAtms,
495 bool ascending);
496 template RDKit::INT_LIST rankAtomsByRank(const RDKit::ROMol &mol,
497 const RDKit::INT_LIST &commAtms,
498 bool ascending);
499 } // namespace RDDepict
500