Chemical Data Processing Library C++ API - Version 1.1.0
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 "CDPL/Chem/APIPrefix.hpp"
40 #include "CDPL/Math/VectorArray.hpp"
41 #include "CDPL/Math/Matrix.hpp"
42 #include "CDPL/Util/BitSet.hpp"
43 #include "CDPL/Util/ObjectStack.hpp"
44 
45 
46 namespace CDPL
47 {
48 
49  namespace Chem
50  {
51 
52  class Atom;
53  class Bond;
54  class MolecularGraph;
55  class Fragment;
56 
60  class CDPL_CHEM_API Atom2DCoordinatesCalculator
61  {
62 
63  public:
67  Atom2DCoordinatesCalculator();
68 
78  Atom2DCoordinatesCalculator(const MolecularGraph& molgraph, Math::Vector2DArray& coords);
79 
88  void calculate(const MolecularGraph& molgraph, Math::Vector2DArray& coords);
89 
90  private:
91  class RingInfo
92  {
93 
94  public:
95  void init(const MolecularGraph*, const Fragment&, std::size_t, std::size_t);
96 
97  const Fragment& getFragment() const;
98 
99  const Util::BitSet& getAtomMask() const;
100  const Util::BitSet& getBondMask() const;
101 
102  double getPriority() const;
103  void setPriority(double);
104 
105  std::size_t getSize() const;
106 
107  private:
108  const Fragment* fragment;
109  Util::BitSet atomMask;
110  Util::BitSet bondMask;
111  double priority;
112  };
113 
114  class LGNode;
115 
116  class LGEdge
117  {
118 
119  public:
120  enum Type
121  {
122 
123  BOND_EDGE,
124  SPIRO_EDGE
125  };
126 
127  void init(const MolecularGraph*, const Atom*, LGNode*, LGNode*);
128  void init(const MolecularGraph*, const Bond*, LGNode*, LGNode*);
129 
130  const Atom* getSpiroCenter() const;
131  const Bond* getBond() const;
132 
133  LGNode* otherNode(const LGNode*) const;
134 
135  Type getType() const;
136 
137  bool hasConfigConstraint() const;
138  bool configConstraintFulfilled(const Math::Vector2DArray&) const;
139 
140  private:
141  bool initConfigInfo();
142 
143  const MolecularGraph* molGraph;
144  const Atom* spiroCenter;
145  const Bond* bond;
146  LGNode* node1;
147  LGNode* node2;
148  Type type;
149  bool hasConfig;
150  unsigned int configuration;
151  const Atom* configRefAtoms[2];
152  };
153 
154  typedef std::vector<std::size_t> AtomIndexList;
155  typedef std::vector<const Bond*> BondList;
156  typedef std::vector<LGNode*> NodeList;
157 
158  class LGNode
159  {
160 
161  public:
162  enum Type
163  {
164 
165  RING_SYS = 0x1,
166  CHAIN_ATOM = 0x2,
167  END_ATOM = 0x3
168  };
169 
170  enum Direction
171  {
172 
173  UP,
174  DOWN
175  };
176 
177  virtual ~LGNode() {}
178 
179  void init(const MolecularGraph* molgraph);
180 
181  virtual void addEdge(const Atom*, const LGEdge*) = 0;
182 
183  virtual void getChildNodes(NodeList&) const = 0;
184 
185  virtual void init() = 0;
186 
187  virtual void createChildLayouts() = 0;
188 
189  virtual double getPriority() const = 0;
190 
191  virtual std::size_t getChainID() const = 0;
192 
193  virtual void layout() = 0;
194  virtual bool layout(double, const Math::Vector2D&, std::size_t&, std::size_t, bool) = 0;
195 
196  virtual bool layoutChildNodes(std::size_t&, std::size_t, bool) = 0;
197 
198  virtual Type getType() const = 0;
199 
200  virtual double getAngularDemand(const Atom*) const;
201 
202  virtual bool setParentEdge(const LGEdge*, Direction) = 0;
203 
204  protected:
205  std::size_t countAtomCollisions(const AtomIndexList&, const AtomIndexList&, const Math::Vector2DArray&);
206  std::size_t countAtomCollisionsForAtom(std::size_t, const AtomIndexList&, const Math::Vector2DArray&);
207 
208  std::size_t countBondCollisions(const BondList&, const BondList&, const Math::Vector2DArray&);
209  std::size_t countBondCollisionsForBond(const Bond*, const BondList&, const Math::Vector2DArray&);
210 
211  std::size_t countAtomBondCollisions(const AtomIndexList&, const BondList&, const Math::Vector2DArray&);
212  std::size_t countBondCollisionsForAtom(std::size_t, const BondList&, const Math::Vector2DArray&);
213 
214  std::size_t countBondAtomCollisions(const BondList&, const AtomIndexList&, const Math::Vector2DArray&);
215  std::size_t countAtomCollisionsForBond(const Bond*, const AtomIndexList&, const Math::Vector2DArray&);
216 
217  bool testAtomBondCollision(std::size_t, const Bond*, const Math::Vector2DArray&);
218 
219  struct NodeLayoutInfo
220  {
221 
222  NodeLayoutInfo(const LGEdge* edge, double angle):
223  edge(edge), angle(angle) {}
224 
225  const LGEdge* edge;
226  double angle;
227  };
228 
229  typedef std::vector<NodeLayoutInfo> NodeLayoutInfoList;
230  typedef std::pair<double, double> AngleRange;
231 
232  class EdgePriorityGreaterCmpFunc;
233 
234  class LinkedNodePriorityLessCmpFunc;
235  class LinkedNodePriorityEqualCmpFunc;
236 
237  class NodeLayoutInfoListEqualCmpFunc;
238 
239  const MolecularGraph* molGraph;
240  };
241 
242  typedef std::list<RingInfo*> RingInfoList;
243  typedef std::vector<const LGEdge*> EdgeList;
244 
245  class RingSysNode : public LGNode
246  {
247 
248  public:
249  void init(const MolecularGraph*, const RingInfo*, Math::Vector2DArray&,
250  AtomIndexList&, BondList&);
251 
252  const Util::BitSet& getAtomMask() const;
253  const Util::BitSet& getBondMask() const;
254 
255  bool containsAtom(std::size_t) const;
256 
257  bool addRing(const RingInfo*);
258 
259  void addEdge(const Atom*, const LGEdge*);
260 
261  void getChildNodes(NodeList&) const;
262 
263  void init();
264 
265  double getPriority() const;
266 
267  std::size_t getChainID() const;
268 
269  void layout();
270  bool layout(double, const Math::Vector2D&, std::size_t&, std::size_t, bool);
271 
272  bool layoutChildNodes(std::size_t&, std::size_t, bool);
273 
274  Type getType() const;
275 
276  double getAngularDemand(const Atom*) const;
277 
278  bool setParentEdge(const LGEdge*, Direction);
279 
280  private:
281  bool layoutChildNodes(double, double, bool, double, std::size_t&, std::size_t, bool);
282  bool layoutChildNodes(std::size_t, std::size_t&, std::size_t, bool);
283 
284  void createChildLayouts();
285  void createChildLayouts(const Atom*, EdgeList&);
286 
287  bool layout(std::size_t, const Math::Vector2D&, double, bool, double, std::size_t&, std::size_t);
288 
289  void transformCoords(std::size_t, const Math::Vector2D&, double, bool, double);
290 
291  double transformEdgeAngle(double) const;
292 
293  void copyCoords();
294 
295  void commitAtomAndBondList() const;
296 
297  void calcCoords();
298 
299  void calcCoordsForRing(const RingInfo*);
300  void calcCoordsForRingSegment(const RingInfo*);
301 
302  void refineLayout();
303 
304  void initSpringLayoutParams();
305  void performSpringLayout();
306 
307  Math::Vector2D computePartialDerivatives(std::size_t) const;
308  Math::Vector2D computePartialDerivative(std::size_t, std::size_t) const;
309 
310  bool layoutFinished(bool, double, double&, double&) const;
311 
312  void distributeWeightFactors(std::size_t, double, const Math::ULMatrix&);
313 
314  void calcFreeSweeps();
315 
316  bool getNextRingSegment(const RingInfo*);
317 
318  double calcCongestionFactor(const Math::Vector2D&) const;
319  double calcCongestionFactor(const Math::Vector2D&, const Util::BitSet&) const;
320 
321  typedef std::vector<const RingInfo*> RingInfoList;
322  typedef std::list<const RingInfo*> RingLayoutQueue;
323  typedef std::map<const Atom*, EdgeList> EdgeListMap;
324  typedef std::map<const Atom*, AngleRange> AngleRangeMap;
325  typedef std::deque<std::size_t> RingSegment;
326  typedef std::vector<std::vector<NodeLayoutInfoList> > NodeLayoutInfoListTable;
327  typedef std::vector<std::size_t> LayoutIndexTable;
328  typedef std::vector<const Atom*> AtomTable;
329  typedef std::vector<Math::Vector2D> EnergyDerivativeTable;
330  typedef std::vector<double> WeightFactorTable;
331 
332  Util::BitSet atomMask;
333  Util::BitSet bondMask;
334  Util::BitSet procAtomMask;
335  Util::BitSet tmpBitMask;
336  double priority;
337  RingInfoList ringList;
338  RingLayoutQueue ringLayoutQueue;
339  RingSegment ringSegment;
340  EdgeListMap edgeListMap;
341  AngleRangeMap freeSweepMap;
342  AtomIndexList atomList;
343  BondList bondList;
344  AtomIndexList* procAtomList;
345  BondList* procBondList;
346  Math::Vector2DArray localCoords;
347  Math::Vector2DArray* outputCoords;
348  const LGEdge* parentEdge;
349  const Atom* parentEdgeAtom;
350  EdgeList parentEdgeAtomEdges;
351  NodeLayoutInfoListTable childLayouts;
352  LayoutIndexTable childLayoutIndexTable;
353  AtomTable edgeAtomTable;
354  Math::Vector2D parentPos;
355  std::size_t rsysLayoutIndex;
356  double parentEdgeAngle;
357  double rsysRotAngle;
358  double rsysAxisAngle;
359  bool flipped;
360  WeightFactorTable layoutWeightFactors;
361  EnergyDerivativeTable layoutEnergyDerivatives;
362  Math::DMatrix layoutAtomDistances;
363  Math::DMatrix layoutSpringStrengths;
364  };
365 
366  class AtomNode : public LGNode
367  {
368 
369  public:
370  void init(const MolecularGraph*, const Atom*, double, Math::Vector2DArray&, AtomIndexList&, BondList&);
371 
372  void addEdge(const Atom*, const LGEdge*);
373 
374  const Atom* getAtom() const;
375  std::size_t getAtomIndex() const;
376 
377  void getChildNodes(NodeList&) const;
378 
379  void init();
380 
381  double getPriority() const;
382 
383  std::size_t getChainID() const;
384 
385  void setChainID(std::size_t);
386 
387  void layout();
388  bool layout(double, const Math::Vector2D&, std::size_t&, std::size_t, bool);
389 
390  bool layoutChildNodes(std::size_t&, std::size_t, bool);
391 
392  Type getType() const;
393 
394  bool setParentEdge(const LGEdge*, Direction);
395 
396  private:
397  struct LayoutParameters
398  {
399 
400  LayoutParameters(std::size_t num_colls):
401  numCollisions(num_colls) {}
402 
403  std::size_t numCollisions;
404  double bondLength;
405  double edgeAngle;
406  };
407 
408  void layout(double, double, const Math::Vector2D&, std::size_t, std::size_t, LayoutParameters&);
409 
410  std::size_t getChildNodeTypePattern() const;
411 
412  void createChildLayouts();
413 
414  void createChildLayoutsD1();
415  void createChildLayoutsD2();
416  void createChildLayoutsD3();
417  void createChildLayoutsD4();
418  void createChildLayoutsDN();
419 
420  void removeChildLayoutSymmetryDuplicates();
421 
422  void removeParentEdge();
423 
424  void sortChildEdges();
425 
426  typedef std::vector<NodeLayoutInfoList> NodeLayoutInfoListTable;
427 
428  const Atom* atom;
429  std::size_t atomIndex;
430  bool isHydrogen;
431  Type type;
432  double priority;
433  std::size_t chainID;
434  AtomIndexList* procAtomList;
435  BondList* procBondList;
436  Math::Vector2DArray* outputCoords;
437  Direction chainDirection;
438  double parentEdgeAngle;
439  EdgeList edges;
440  const LGEdge* parentEdge;
441  NodeLayoutInfoListTable childLayouts;
442  std::size_t childLayoutIndex;
443  Direction childChainDirections[4];
444  };
445 
446  typedef std::pair<Math::Vector2D, Math::Vector2D> BoundingBox;
447 
448  Atom2DCoordinatesCalculator(const Atom2DCoordinatesCalculator&);
449 
450  Atom2DCoordinatesCalculator& operator=(const Atom2DCoordinatesCalculator&);
451 
452  void init(const MolecularGraph&, Math::Vector2DArray&);
453 
454  void extractRingInformation();
455 
456  void calcAtomPriorities();
457  void calcRingPriorities();
458 
459  void layoutComponents(Math::Vector2DArray&);
460  void layoutComponent(const Fragment&, Math::Vector2DArray&);
461 
462  void alignComponents(Math::Vector2DArray&);
463 
464  void moveComponent(const BoundingBox&, double, double, const Fragment&, Math::Vector2DArray&);
465  void addPoint(BoundingBox&, const Math::Vector2D&) const;
466  void calcBounds(BoundingBox&, const Fragment&, Math::Vector2DArray&) const;
467 
468  void createLayoutTree(const Fragment&, Math::Vector2DArray&);
469  void createRingSysNodes(const Fragment&, Math::Vector2DArray&);
470  void createAtomNodes(const Fragment&, Math::Vector2DArray&);
471  void createBondEdges(const Fragment&);
472  void createSpiroEdges(const Fragment&);
473 
474  void setAtomNodeChainIDs();
475 
476  void findLongestNodePath(AtomNode*, const AtomNode*);
477 
478  void createBFSNodeList();
479  void initNodes() const;
480 
481  void layoutNodes();
482  bool layoutChildNodes(std::size_t);
483 
484  LGEdge* allocEdge(const Atom*, LGNode*, LGNode*);
485  LGEdge* allocEdge(const Bond*, LGNode*, LGNode*);
486 
487  RingInfo* allocRingInfo(const Fragment&);
488  RingSysNode* allocRingSysNode(const RingInfo*, Math::Vector2DArray&);
489 
490  AtomNode* allocAtomNode(const Atom*, Math::Vector2DArray&);
491 
492  void freeAllocEdges();
493  void freeAllocRingInfos();
494  void freeAllocRingSysNodes();
495  void freeAllocAtomNodes();
496 
497  typedef std::vector<AtomNode*> AtomNodeList;
498  typedef std::vector<std::size_t> AtomPriorityTable;
499  typedef Util::ObjectStack<RingInfo> RingInfoCache;
500  typedef Util::ObjectStack<RingSysNode> RingSysNodeCache;
501  typedef Util::ObjectStack<AtomNode> AtomNodeCache;
502  typedef Util::ObjectStack<LGEdge> EdgeCache;
503  typedef std::vector<RingSysNode*> RingSysNodeList;
504 
505  const MolecularGraph* molGraph;
506  RingInfoCache ringInfoCache;
507  RingSysNodeCache ringSysNodeCache;
508  AtomNodeCache atomNodeCache;
509  EdgeCache edgeCache;
510  EdgeList edgeList;
511  RingInfoList ringList;
512  RingSysNodeList ringSysNodeList;
513  AtomNodeList atomNodeList;
514  RingInfoList tmpRingList;
515  NodeList bfsNodeList;
516  AtomNodeList atomNodeTable;
517  AtomNodeList longestAtomNodePath;
518  AtomNodeList currAtomNodePath;
519  AtomIndexList procAtomList;
520  BondList procBondList;
521  Util::BitSet atomMask;
522  Util::BitSet ringAtomMask;
523  Util::BitSet tmpBitMask;
524  AtomPriorityTable atomPriorityTable;
525  std::size_t numAtoms;
526  std::size_t numBonds;
527  bool strictLayoutGeometry;
528  std::size_t numLayoutCollisions;
529  std::size_t maxNumLayoutCollisions;
530  std::size_t backtrackingCount;
531  };
532  } // namespace Chem
533 } // namespace CDPL
534 
535 #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::Chem::MolecularGraph
MolecularGraph.
Definition: MolecularGraph.hpp:52
BitSet.hpp
Definition of the type CDPL::Util::BitSet.
CDPL::Chem::Atom2DCoordinatesCalculator
Atom2DCoordinatesCalculator.
Definition: Atom2DCoordinatesCalculator.hpp:61
CDPL::Chem::Atom2DCoordinatesCalculator::LGNode::NodeLayoutInfo::angle
double angle
Definition: Atom2DCoordinatesCalculator.hpp:226
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:222
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
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:225
CDPL::Biomol::setChainID
CDPL_BIOMOL_API void setChainID(Chem::Atom &atom, const std::string &id)
CDPL::Chem::Atom2DCoordinatesCalculator::LGNode::NodeLayoutInfo
Definition: Atom2DCoordinatesCalculator.hpp:220
Generated by doxygen 1.8.20