Chemical Data Processing Library C++ API - Version 1.1.1
Atom2DCoordinatesCalculator.hpp
Go to the documentation of this file.
1 /*
2  * Atom2DCoordinatesCalculator.hpp
3  *
4  * This file is part of the Chemical Data Processing Toolkit
5  *
6  * Copyright (C) 2003 Thomas Seidel <thomas.seidel@univie.ac.at>
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public License
19  * along with this library; see the file COPYING. If not, write to
20  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
21  * Boston, MA 02111-1307, USA.
22  */
23 
29 #ifndef CDPL_CHEM_ATOM2DCOORDINATESCALCULATOR_HPP
30 #define CDPL_CHEM_ATOM2DCOORDINATESCALCULATOR_HPP
31 
32 #include <cstddef>
33 #include <vector>
34 #include <list>
35 #include <deque>
36 #include <map>
37 #include <utility>
38 
39 #include <boost/unordered_set.hpp>
40 
41 #include "CDPL/Chem/APIPrefix.hpp"
43 #include "CDPL/Math/Matrix.hpp"
44 #include "CDPL/Util/BitSet.hpp"
47 
48 
49 namespace CDPL
50 {
51 
52  namespace Chem
53  {
54 
55  class Atom;
56  class Bond;
57  class MolecularGraph;
58  class Fragment;
59 
64  {
65 
66  public:
71 
82 
91  void calculate(const MolecularGraph& molgraph, Math::Vector2DArray& coords);
92 
93  private:
94  class RingInfo
95  {
96 
97  public:
98  void init(const MolecularGraph*, const Fragment&, std::size_t, std::size_t);
99 
100  const Fragment& getFragment() const;
101 
102  const Util::BitSet& getAtomMask() const;
103  const Util::BitSet& getBondMask() const;
104 
105  double getPriority() const;
106  void setPriority(double);
107 
108  std::size_t getSize() const;
109 
110  private:
111  const Fragment* fragment;
112  Util::BitSet atomMask;
113  Util::BitSet bondMask;
114  double priority;
115  };
116 
117  class LGNode;
118 
119  class LGEdge
120  {
121 
122  public:
123  enum Type
124  {
125 
126  BOND_EDGE,
127  SPIRO_EDGE
128  };
129 
130  void init(const MolecularGraph*, const Atom*, LGNode*, LGNode*);
131  void init(const MolecularGraph*, const Bond*, LGNode*, LGNode*);
132 
133  const Atom* getSpiroCenter() const;
134  const Bond* getBond() const;
135 
136  LGNode* otherNode(const LGNode*) const;
137 
138  Type getType() const;
139 
140  bool hasConfigConstraint() const;
141  bool configConstraintFulfilled(const Math::Vector2DArray&) const;
142 
143  private:
144  bool initConfigInfo();
145 
146  const MolecularGraph* molGraph;
147  const Atom* spiroCenter;
148  const Bond* bond;
149  LGNode* node1;
150  LGNode* node2;
151  Type type;
152  bool hasConfig;
153  unsigned int configuration;
154  const Atom* configRefAtoms[2];
155  };
156 
157  typedef std::vector<std::size_t> AtomIndexList;
158  typedef std::vector<const Bond*> BondList;
159  typedef std::vector<LGNode*> NodeList;
160 
161  class LGNode
162  {
163 
164  public:
165  enum Type
166  {
167 
168  RING_SYS = 0x1,
169  CHAIN_ATOM = 0x2,
170  END_ATOM = 0x3
171  };
172 
173  enum Direction
174  {
175 
176  UP,
177  DOWN
178  };
179 
180  virtual ~LGNode() {}
181 
182  void init(const MolecularGraph* molgraph);
183 
184  virtual void addEdge(const Atom*, const LGEdge*) = 0;
185 
186  virtual void getChildNodes(NodeList&) const = 0;
187 
188  virtual void init() = 0;
189 
190  virtual void createChildLayouts() = 0;
191 
192  virtual double getPriority() const = 0;
193 
194  virtual std::size_t getChainID() const = 0;
195 
196  virtual void layout() = 0;
197  virtual bool layout(double, const Math::Vector2D&, std::size_t&, std::size_t, bool) = 0;
198 
199  virtual bool layoutChildNodes(std::size_t&, std::size_t, bool) = 0;
200 
201  virtual Type getType() const = 0;
202 
203  virtual double getAngularDemand(const Atom*) const;
204 
205  virtual bool setParentEdge(const LGEdge*, Direction) = 0;
206 
207  protected:
208  std::size_t countAtomCollisions(const AtomIndexList&, const AtomIndexList&, const Math::Vector2DArray&);
209  std::size_t countAtomCollisionsForAtom(std::size_t, const AtomIndexList&, const Math::Vector2DArray&);
210 
211  std::size_t countBondCollisions(const BondList&, const BondList&, const Math::Vector2DArray&);
212  std::size_t countBondCollisionsForBond(const Bond*, const BondList&, const Math::Vector2DArray&);
213 
214  std::size_t countAtomBondCollisions(const AtomIndexList&, const BondList&, const Math::Vector2DArray&);
215  std::size_t countBondCollisionsForAtom(std::size_t, const BondList&, const Math::Vector2DArray&);
216 
217  std::size_t countBondAtomCollisions(const BondList&, const AtomIndexList&, const Math::Vector2DArray&);
218  std::size_t countAtomCollisionsForBond(const Bond*, const AtomIndexList&, const Math::Vector2DArray&);
219 
220  bool testAtomBondCollision(std::size_t, const Bond*, const Math::Vector2DArray&);
221 
223  {
224 
225  NodeLayoutInfo(const LGEdge* edge, double angle):
226  edge(edge), angle(angle) {}
227 
228  const LGEdge* edge;
229  double angle;
230  };
231 
232  typedef std::vector<NodeLayoutInfo> NodeLayoutInfoList;
233  typedef std::pair<double, double> AngleRange;
234 
235  class EdgePriorityGreaterCmpFunc;
236 
237  class LinkedNodePriorityLessCmpFunc;
238  class LinkedNodePriorityEqualCmpFunc;
239 
240  class NodeLayoutInfoListEqualCmpFunc;
241 
242  const MolecularGraph* molGraph;
243  };
244 
245  typedef std::list<RingInfo*> RingInfoList;
246  typedef std::vector<const LGEdge*> EdgeList;
247 
248  class RingSysNode : public LGNode
249  {
250 
251  public:
252  RingSysNode();
253 
254  void init(const MolecularGraph*, const RingInfo*, Math::Vector2DArray&,
255  AtomIndexList&, BondList&);
256 
257  const Util::BitSet& getAtomMask() const;
258  const Util::BitSet& getBondMask() const;
259 
260  bool containsAtom(std::size_t) const;
261 
262  bool addRing(const RingInfo*);
263 
264  void addEdge(const Atom*, const LGEdge*);
265 
266  void getChildNodes(NodeList&) const;
267 
268  void init();
269 
270  double getPriority() const;
271 
272  std::size_t getChainID() const;
273 
274  void layout();
275  bool layout(double, const Math::Vector2D&, std::size_t&, std::size_t, bool);
276 
277  bool layoutChildNodes(std::size_t&, std::size_t, bool);
278 
279  Type getType() const;
280 
281  double getAngularDemand(const Atom*) const;
282 
283  bool setParentEdge(const LGEdge*, Direction);
284 
285  private:
286  bool layoutChildNodes(double, double, bool, double, std::size_t&, std::size_t, bool);
287  bool layoutChildNodes(std::size_t, std::size_t&, std::size_t, bool);
288 
289  void createChildLayouts();
290  void createChildLayouts(const Atom*, EdgeList&);
291 
292  bool layout(std::size_t, const Math::Vector2D&, double, bool, double, std::size_t&, std::size_t);
293 
294  void transformCoords(std::size_t, const Math::Vector2D&, double, bool, double);
295 
296  double transformEdgeAngle(double) const;
297 
298  void copyCoords();
299 
300  void commitAtomAndBondList() const;
301 
302  void calcCoords();
303 
304  void calcCoordsForRing(const RingInfo*);
305  void calcCoordsForRingSegment(const RingInfo*);
306 
307  void refineLayout();
308 
309  void initSpringLayoutParams();
310  void performSpringLayout();
311 
312  void performDistGeomLayout();
313  bool needDistGeomLayout() const;
314  bool addBondStereoDGConstraints(const RingInfo* ring_info);
315  void addBondAngleDGConstraints(const RingInfo* ring_info);
316  void addDefaultDGConstraints();
317 
318  const Chem::Atom* getExoBondAtom(const RingInfo* ring_info, const Atom& atom, std::size_t rings_nbrs[2]) const;
319 
320  Math::Vector2D computePartialDerivatives(std::size_t) const;
321  Math::Vector2D computePartialDerivative(std::size_t, std::size_t) const;
322 
323  bool layoutFinished(bool, double, double&, double&) const;
324 
325  void distributeWeightFactors(std::size_t, double, const Math::ULMatrix&);
326 
327  void calcFreeSweeps();
328 
329  bool getNextRingSegment(const RingInfo*);
330 
331  double calcCongestionFactor(const Math::Vector2D&) const;
332  double calcCongestionFactor(const Math::Vector2D&, const Util::BitSet&) const;
333 
334  typedef Util::DGCoordinatesGenerator<2, double> DGCoordsGenerator;
335  typedef std::pair<std::size_t, std::size_t> DistConstraintKey;
336  typedef boost::unordered_set<DistConstraintKey> DistConstraintKeySet;
337  typedef std::vector<const RingInfo*> RingInfoList;
338  typedef std::list<const RingInfo*> RingLayoutQueue;
339  typedef std::map<const Atom*, EdgeList> EdgeListMap;
340  typedef std::map<const Atom*, AngleRange> AngleRangeMap;
341  typedef std::deque<std::size_t> RingSegment;
342  typedef std::vector<std::vector<NodeLayoutInfoList> > NodeLayoutInfoListTable;
343  typedef std::vector<std::size_t> LayoutIndexTable;
344  typedef std::vector<const Atom*> AtomTable;
345  typedef std::vector<Math::Vector2D> EnergyDerivativeTable;
346  typedef std::vector<double> WeightFactorTable;
347 
348  Util::BitSet atomMask;
349  Util::BitSet bondMask;
350  Util::BitSet procAtomMask;
351  Util::BitSet tmpBitMask;
352  double priority;
353  RingInfoList ringList;
354  RingLayoutQueue ringLayoutQueue;
355  RingSegment ringSegment;
356  EdgeListMap edgeListMap;
357  AngleRangeMap freeSweepMap;
358  AtomIndexList atomList;
359  BondList bondList;
360  AtomIndexList* procAtomList;
361  BondList* procBondList;
362  Math::Vector2DArray localCoords;
363  Math::Vector2DArray* outputCoords;
364  const LGEdge* parentEdge;
365  const Atom* parentEdgeAtom;
366  EdgeList parentEdgeAtomEdges;
367  NodeLayoutInfoListTable childLayouts;
368  LayoutIndexTable childLayoutIndexTable;
369  AtomTable edgeAtomTable;
370  Math::Vector2D parentPos;
371  std::size_t rsysLayoutIndex;
372  double parentEdgeAngle;
373  double rsysRotAngle;
374  double rsysAxisAngle;
375  bool flipped;
376  WeightFactorTable layoutWeightFactors;
377  EnergyDerivativeTable layoutEnergyDerivatives;
378  Math::DMatrix layoutAtomDistances;
379  Math::DMatrix layoutSpringStrengths;
380  DGCoordsGenerator dgCoordsGenerator;
381  DistConstraintKeySet setDistConstraints;
382  };
383 
384  class AtomNode : public LGNode
385  {
386 
387  public:
388  void init(const MolecularGraph*, const Atom*, double, Math::Vector2DArray&, AtomIndexList&, BondList&);
389 
390  void addEdge(const Atom*, const LGEdge*);
391 
392  const Atom* getAtom() const;
393  std::size_t getAtomIndex() const;
394 
395  void getChildNodes(NodeList&) const;
396 
397  void init();
398 
399  double getPriority() const;
400 
401  std::size_t getChainID() const;
402 
403  void setChainID(std::size_t);
404 
405  void layout();
406  bool layout(double, const Math::Vector2D&, std::size_t&, std::size_t, bool);
407 
408  bool layoutChildNodes(std::size_t&, std::size_t, bool);
409 
410  Type getType() const;
411 
412  bool setParentEdge(const LGEdge*, Direction);
413 
414  private:
415  struct LayoutParameters
416  {
417 
418  LayoutParameters(std::size_t num_colls):
419  numCollisions(num_colls) {}
420 
421  std::size_t numCollisions;
422  double bondLength;
423  double edgeAngle;
424  };
425 
426  void layout(double, double, const Math::Vector2D&, std::size_t, std::size_t, LayoutParameters&);
427 
428  std::size_t getChildNodeTypePattern() const;
429 
430  void createChildLayouts();
431 
432  void createChildLayoutsD1();
433  void createChildLayoutsD2();
434  void createChildLayoutsD3();
435  void createChildLayoutsD4();
436  void createChildLayoutsDN();
437 
438  void removeChildLayoutSymmetryDuplicates();
439 
440  void removeParentEdge();
441 
442  void sortChildEdges();
443 
444  typedef std::vector<NodeLayoutInfoList> NodeLayoutInfoListTable;
445 
446  const Atom* atom;
447  std::size_t atomIndex;
448  bool isHydrogen;
449  Type type;
450  double priority;
451  std::size_t chainID;
452  AtomIndexList* procAtomList;
453  BondList* procBondList;
454  Math::Vector2DArray* outputCoords;
455  Direction chainDirection;
456  double parentEdgeAngle;
457  EdgeList edges;
458  const LGEdge* parentEdge;
459  NodeLayoutInfoListTable childLayouts;
460  std::size_t childLayoutIndex;
461  Direction childChainDirections[4];
462  };
463 
464  typedef std::pair<Math::Vector2D, Math::Vector2D> BoundingBox;
465 
466  Atom2DCoordinatesCalculator(const Atom2DCoordinatesCalculator&);
467 
468  Atom2DCoordinatesCalculator& operator=(const Atom2DCoordinatesCalculator&);
469 
470  void init(const MolecularGraph&, Math::Vector2DArray&);
471 
472  void extractRingInformation();
473 
474  void calcAtomPriorities();
475  void calcRingPriorities();
476 
477  void layoutComponents(Math::Vector2DArray&);
478  void layoutComponent(const Fragment&, Math::Vector2DArray&);
479 
480  void alignComponents(Math::Vector2DArray&);
481 
482  void moveComponent(const BoundingBox&, double, double, const Fragment&, Math::Vector2DArray&);
483  void addPoint(BoundingBox&, const Math::Vector2D&) const;
484  void calcBounds(BoundingBox&, const Fragment&, Math::Vector2DArray&) const;
485 
486  void createLayoutTree(const Fragment&, Math::Vector2DArray&);
487  void createRingSysNodes(const Fragment&, Math::Vector2DArray&);
488  void createAtomNodes(const Fragment&, Math::Vector2DArray&);
489  void createBondEdges(const Fragment&);
490  void createSpiroEdges(const Fragment&);
491 
492  void setAtomNodeChainIDs();
493 
494  void findLongestNodePath(AtomNode*, const AtomNode*);
495 
496  void createBFSNodeList();
497  void initNodes() const;
498 
499  void layoutNodes();
500  bool layoutChildNodes(std::size_t);
501 
502  LGEdge* allocEdge(const Atom*, LGNode*, LGNode*);
503  LGEdge* allocEdge(const Bond*, LGNode*, LGNode*);
504 
505  RingInfo* allocRingInfo(const Fragment&);
506  RingSysNode* allocRingSysNode(const RingInfo*, Math::Vector2DArray&);
507 
508  AtomNode* allocAtomNode(const Atom*, Math::Vector2DArray&);
509 
510  void freeAllocEdges();
511  void freeAllocRingInfos();
512  void freeAllocRingSysNodes();
513  void freeAllocAtomNodes();
514 
515  typedef std::vector<AtomNode*> AtomNodeList;
516  typedef std::vector<std::size_t> AtomPriorityTable;
517  typedef Util::ObjectStack<RingInfo> RingInfoCache;
518  typedef Util::ObjectStack<RingSysNode> RingSysNodeCache;
519  typedef Util::ObjectStack<AtomNode> AtomNodeCache;
520  typedef Util::ObjectStack<LGEdge> EdgeCache;
521  typedef std::vector<RingSysNode*> RingSysNodeList;
522 
523  const MolecularGraph* molGraph;
524  RingInfoCache ringInfoCache;
525  RingSysNodeCache ringSysNodeCache;
526  AtomNodeCache atomNodeCache;
527  EdgeCache edgeCache;
528  EdgeList edgeList;
529  RingInfoList ringList;
530  RingSysNodeList ringSysNodeList;
531  AtomNodeList atomNodeList;
532  RingInfoList tmpRingList;
533  NodeList bfsNodeList;
534  AtomNodeList atomNodeTable;
535  AtomNodeList longestAtomNodePath;
536  AtomNodeList currAtomNodePath;
537  AtomIndexList procAtomList;
538  BondList procBondList;
539  Util::BitSet atomMask;
540  Util::BitSet ringAtomMask;
541  Util::BitSet tmpBitMask;
542  AtomPriorityTable atomPriorityTable;
543  std::size_t numAtoms;
544  std::size_t numBonds;
545  bool strictLayoutGeometry;
546  std::size_t numLayoutCollisions;
547  std::size_t maxNumLayoutCollisions;
548  std::size_t backtrackingCount;
549  };
550  } // namespace Chem
551 } // namespace CDPL
552 
553 #endif // CDPL_CHEM_ATOM2DCOORDINATESCALCULATOR_HPP
ObjectStack.hpp
Definition of the class CDPL::Util::ObjectStack.
APIPrefix.hpp
Definition of the preprocessor macro CDPL_CHEM_API.
VectorArray.hpp
Definition of the class CDPL::Math::VectorArray.
CDPL_CHEM_API
#define CDPL_CHEM_API
Tells the compiler/linker which classes, functions and variables are part of the library API.
CDPL::Chem::Atom2DCoordinatesCalculator::calculate
void calculate(const MolecularGraph &molgraph, Math::Vector2DArray &coords)
Calculates 2D-coordinates for the atoms of the molecular graph molgraph.
CDPL::Util::BitSet
boost::dynamic_bitset BitSet
A dynamic bitset class.
Definition: BitSet.hpp:46
CDPL::Chem::Atom2DCoordinatesCalculator::Atom2DCoordinatesCalculator
Atom2DCoordinatesCalculator()
Constructs the Atom2DCoordinatesCalculator instance.
CDPL::Chem::Atom
Atom.
Definition: Atom.hpp:52
CDPL::Chem::Fragment
Fragment.
Definition: Fragment.hpp:52
CDPL::Util::DGCoordinatesGenerator< 2, double >
CDPL::Chem::MolecularGraph
MolecularGraph.
Definition: MolecularGraph.hpp:52
BitSet.hpp
Definition of the type CDPL::Util::BitSet.
CDPL::Chem::Atom2DCoordinatesCalculator
Atom2DCoordinatesCalculator.
Definition: Atom2DCoordinatesCalculator.hpp:64
CDPL::Chem::Atom2DCoordinatesCalculator::LGNode::NodeLayoutInfo::angle
double angle
Definition: Atom2DCoordinatesCalculator.hpp:229
CDPL::Chem::Atom2DCoordinatesCalculator::Atom2DCoordinatesCalculator
Atom2DCoordinatesCalculator(const MolecularGraph &molgraph, Math::Vector2DArray &coords)
Constructs the Atom2DCoordinatesCalculator instance and calculates 2D-coordinates for the atoms of th...
CDPL::Biomol::getChainID
CDPL_BIOMOL_API const std::string & getChainID(const Chem::Atom &atom)
CDPL::Chem::getType
CDPL_CHEM_API unsigned int getType(const Atom &atom)
CDPL::Chem::Atom2DCoordinatesCalculator::LGNode::NodeLayoutInfo::NodeLayoutInfo
NodeLayoutInfo(const LGEdge *edge, double angle)
Definition: Atom2DCoordinatesCalculator.hpp:225
CDPL::Math::Matrix
Definition: Matrix.hpp:280
CDPL
The namespace of the Chemical Data Processing Library.
CDPL::Chem::BondDirection::UP
const unsigned int UP
Specifies that the bond is directed upwards.
Definition: BondDirection.hpp:60
CDPL::Math::Vector2D
CVector< double, 2 > Vector2D
A bounded 2 element vector holding floating point values of type double.
Definition: Vector.hpp:1632
CDPL::Chem::BondDirection::DOWN
const unsigned int DOWN
Specifies that the bond is directed downwards.
Definition: BondDirection.hpp:67
DGCoordinatesGenerator.hpp
Implementation of a distance geometry based coordinates generator.
Matrix.hpp
Definition of matrix data types.
CDPL::Math::Vector2DArray
VectorArray< Vector2D > Vector2DArray
An array of Math::Vector2D objects.
Definition: VectorArray.hpp:79
CDPL::Chem::Atom2DCoordinatesCalculator::LGNode::NodeLayoutInfo::edge
const LGEdge * edge
Definition: Atom2DCoordinatesCalculator.hpp:228
CDPL::Biomol::setChainID
CDPL_BIOMOL_API void setChainID(Chem::Atom &atom, const std::string &id)
CDPL::Chem::Atom2DCoordinatesCalculator::LGNode::NodeLayoutInfo
Definition: Atom2DCoordinatesCalculator.hpp:223