Chemical Data Processing Library C++ API - Version 1.1.1
SpatialEntityAlignment.hpp
Go to the documentation of this file.
1 /*
2  * SpatialEntityAlignment.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_SPATIALENTITYALIGNMENT_HPP
30 #define CDPL_CHEM_SPATIALENTITYALIGNMENT_HPP
31 
32 #include <cstddef>
33 #include <algorithm>
34 #include <vector>
35 #include <set>
36 #include <unordered_set>
37 #include <functional>
38 
39 #include <boost/functional/hash.hpp>
40 
43 #include "CDPL/Math/Matrix.hpp"
44 #include "CDPL/Math/Vector.hpp"
46 
47 
48 namespace CDPL
49 {
50 
51  namespace Chem
52  {
53 
57  template <typename T>
59  {
60 
61  typedef TopologicalEntityAlignment<T> TopologicalAlignment;
62 
63  public:
67  typedef T EntityType;
68 
73 
78 
82  typedef std::function<const Math::Vector3D&(const EntityType&)> Entity3DCoordinatesFunction;
83 
87  typedef std::function<double(const EntityType&)> EntityWeightFunction;
88 
93 
98 
103 
108 
114  void setMinTopologicalMappingSize(std::size_t min_size);
115 
122 
128 
134 
140 
146 
152 
158 
164 
170 
177 
183 
184  void performExhaustiveSearch(bool exhaustive);
185 
187 
193  void addEntity(const EntityType& entity, bool first_set);
194 
199  void clearEntities(bool first_set);
200 
205  std::size_t getNumEntities(bool first_set) const;
206 
212  ConstEntityIterator getEntitiesBegin(bool first_set) const;
213 
219  ConstEntityIterator getEntitiesEnd(bool first_set) const;
220 
228  const EntityType& getEntity(std::size_t idx, bool first_set) const;
229 
235 
236  void reset();
237 
246  const Math::Matrix4D& getTransform() const;
247 
253 
254  private:
255  void init();
256 
257  Util::STPairArray* allocTopMapping();
258 
259  struct TopMappingCmpFunc
260  {
261 
262  bool operator()(const Util::STPairArray* m1, const Util::STPairArray* m2) const
263  {
264  return (m1->getSize() > m2->getSize());
265  }
266  };
267 
268  struct TopMappingHashFunc
269  {
270 
271  std::size_t operator()(const Util::STPairArray* m) const
272  {
273  return boost::hash_value(m->getData());
274  }
275  };
276 
277  struct TopMappingEqCmpFunc
278  {
279 
280  bool operator()(const Util::STPairArray* m1, const Util::STPairArray* m2) const
281  {
282  return (m1->getData() == m2->getData());
283  }
284  };
285 
286  typedef Util::ObjectStack<Util::STPairArray> TopMappingCache;
287  typedef std::vector<Math::Vector3D> Vector3DArray;
288  typedef std::vector<double> DoubleArray;
289  typedef std::multiset<Util::STPairArray*, TopMappingCmpFunc> TopMappingSet;
290  typedef typename TopMappingSet::iterator TopMappingSetIterator;
291  typedef std::unordered_set<const Util::STPairArray*, TopMappingHashFunc, TopMappingEqCmpFunc> TopMappingHashSet;
292 
293  TopologicalAlignment topAlignment;
294  TopMappingSet topMappings;
295  TopMappingSetIterator nextTopMappingIter;
296  Util::STPairArray* currTopMapping;
297  TopologicalAlignmentConstraintFunction topAlignConstrFunc;
298  Entity3DCoordinatesFunction coordsFunc;
299  EntityWeightFunction weightFunc;
300  Math::KabschAlgorithm<double> kabschAlgorithm;
301  Vector3DArray firstSetCoords;
302  DoubleArray firstSetWeights;
303  Vector3DArray secondSetCoords;
304  DoubleArray secondSetWeights;
305  Math::DMatrix refPoints;
306  Math::DMatrix alignedPoints;
307  Math::DVector almntWeights;
308  Math::Matrix4D transform;
309  std::size_t minTopMappingSize;
310  bool changes;
311  bool exhaustiveMode;
312  TopMappingHashSet seenTopMappings;
313  TopMappingCache topMappingCache;
314  };
315  } // namespace Chem
316 } // namespace CDPL
317 
318 
319 // Implementation
320 
321 template <typename T>
323  minTopMappingSize(3), changes(true), exhaustiveMode(true), topMappingCache(5000)
324 {
325  currTopMapping = allocTopMapping();
326 }
327 
328 template <typename T>
330 {
331  minTopMappingSize = min_size;
332  changes = true;
333 }
334 
335 template <typename T>
337 {
338  return minTopMappingSize;
339 }
340 
341 template <typename T>
343 {
344  coordsFunc = func;
345  changes = true;
346 }
347 
348 template <typename T>
351 {
352  return coordsFunc;
353 }
354 
355 template <typename T>
357 {
358  weightFunc = func;
359  changes = true;
360 }
361 
362 template <typename T>
365 {
366  return weightFunc;
367 }
368 
369 template <typename T>
371 {
372  topAlignConstrFunc = func;
373  changes = true;
374 }
375 
376 template <typename T>
379 {
380  return topAlignConstrFunc;
381 }
382 
383 template <typename T>
385 {
386  topAlignment.setEntityMatchFunction(func);
387 }
388 
389 template <typename T>
392 {
393  return topAlignment.getEntityMatchFunction();
394 }
395 
396 template <typename T>
398 {
399  topAlignment.setEntityPairMatchFunction(func);
400 }
401 
402 template <typename T>
405 {
406  return topAlignment.getEntityPairMatchFunction();
407 }
408 
409 template <typename T>
411 {
412  exhaustiveMode = exhaustive;
413  changes = true;
414 }
415 
416 template <typename T>
418 {
419  return exhaustiveMode;
420 }
421 
422 template <typename T>
424 {
425  return topAlignment.getNumEntities(first_set);
426 }
427 
428 template <typename T>
430 {
431  topAlignment.addEntity(entity, first_set);
432  changes = true;
433 }
434 
435 template <typename T>
437 {
438  topAlignment.clearEntities(first_set);
439  changes = true;
440 }
441 
442 template <typename T>
445 {
446  return topAlignment.getEntitiesBegin(first_set);
447 }
448 
449 template <typename T>
452 {
453  return topAlignment.getEntitiesEnd(first_set);
454 }
455 
456 template <typename T>
458 CDPL::Chem::SpatialEntityAlignment<T>::getEntity(std::size_t idx, bool first_set) const
459 {
460  return topAlignment.getEntity(idx, first_set);
461 }
462 
463 template <typename T>
465 {
466  changes = true;
467 }
468 
469 template <typename T>
471 {
472  if (changes)
473  init();
474 
475  if (firstSetCoords.empty() || secondSetCoords.empty())
476  return false;
477 
478  bool have_weights = !firstSetWeights.empty();
479  std::size_t min_sub_mpg_size = (minTopMappingSize < 3 ? minTopMappingSize : std::size_t(3));
480 
481  while (nextTopMappingIter != topMappings.end()) {
482  currTopMapping = *nextTopMappingIter;
483 
484  std::size_t num_points = currTopMapping->getSize();
485 
486  refPoints.resize(3, num_points, false);
487  alignedPoints.resize(3, num_points, false);
488 
489  if (have_weights)
490  almntWeights.resize(num_points, 1.0);
491 
492  std::size_t i = 0;
493 
494  for (Util::STPairArray::ConstElementIterator it = currTopMapping->getElementsBegin(), end = currTopMapping->getElementsEnd();
495  it != end; ++it, i++) {
496 
497  std::size_t first_idx = it->first;
498  std::size_t sec_idx = it->second;
499 
500  column(refPoints, i) = firstSetCoords[first_idx];
501  column(alignedPoints, i) = secondSetCoords[sec_idx];
502 
503  if (have_weights)
504  almntWeights(i) = std::max(firstSetWeights[first_idx], secondSetWeights[sec_idx]);
505  }
506 
507  if (exhaustiveMode && (num_points > min_sub_mpg_size)) {
508  Util::STPairArray* sub_mpg = 0;
509 
510  for (std::size_t j = 0; j < num_points; j++) {
511  if (!sub_mpg)
512  sub_mpg = allocTopMapping();
513 
514  sub_mpg->clear();
515 
516  for (std::size_t k = 0; k < num_points; k++)
517  if (k != j)
518  sub_mpg->addElement(currTopMapping->getElement(k));
519 
520  if (!seenTopMappings.insert(sub_mpg).second) {
521  continue;
522  }
523 
524  topMappings.insert(sub_mpg);
525  sub_mpg = 0;
526  }
527 
528  if (sub_mpg)
529  topMappingCache.put();
530  }
531 
532  if (!have_weights) {
533  if (!kabschAlgorithm.align(alignedPoints, refPoints)) {
534  ++nextTopMappingIter;
535  continue;
536  }
537 
538  } else if (!kabschAlgorithm.align(alignedPoints, refPoints, almntWeights)) {
539  ++nextTopMappingIter;
540  continue;
541  }
542 
543  transform.assign(kabschAlgorithm.getTransform());
544  ++nextTopMappingIter;
545 
546  return true;
547  }
548 
549  return false;
550 }
551 
552 template <typename T>
554 {
555  return transform;
556 }
557 
558 template <typename T>
561 {
562  return *currTopMapping;
563 }
564 
565 template <typename T>
567 {
568  firstSetCoords.clear();
569  secondSetCoords.clear();
570 
571  firstSetWeights.clear();
572  secondSetWeights.clear();
573 
574  if (coordsFunc) {
575  for (ConstEntityIterator it = getEntitiesBegin(true), end = getEntitiesEnd(true); it != end; ++it) {
576  const EntityType& entity = *it;
577 
578  firstSetCoords.push_back(coordsFunc(entity));
579 
580  if (weightFunc)
581  firstSetWeights.push_back(weightFunc(entity));
582  }
583 
584  for (ConstEntityIterator it = getEntitiesBegin(false), end = getEntitiesEnd(false); it != end; ++it) {
585  const EntityType& entity = *it;
586 
587  secondSetCoords.push_back(coordsFunc(entity));
588 
589  if (weightFunc)
590  secondSetWeights.push_back(weightFunc(entity));
591  }
592  }
593 
594  topAlignment.reset();
595  topMappingCache.putAll();
596  seenTopMappings.clear();
597  topMappings.clear();
598 
599  currTopMapping = allocTopMapping();
600 
601  while (topAlignment.nextAlignment(*currTopMapping)) {
602  if (currTopMapping->getSize() < minTopMappingSize)
603  continue;
604 
605  if (topAlignConstrFunc && !topAlignConstrFunc(*currTopMapping))
606  continue;
607 
608  topMappings.insert(currTopMapping);
609  currTopMapping = allocTopMapping();
610  }
611 
612  currTopMapping->clear();
613 
614  nextTopMappingIter = topMappings.begin();
615  changes = false;
616 }
617 
618 template <typename T>
621 {
622  return topMappingCache.get();
623 }
624 
625 #endif // CDPL_CHEM_SPATIALENTITYALIGNMENT_HPP
CDPL::Chem::TopologicalEntityAlignment< Feature >::EntityPairMatchFunction
std::function< bool(const EntityType &, const EntityType &, const EntityType &, const EntityType &)> EntityPairMatchFunction
A generic wrapper class used to store a user-defined entity-pair match constraint function.
Definition: TopologicalEntityAlignment.hpp:80
CDPL::Chem::SpatialEntityAlignment::~SpatialEntityAlignment
virtual ~SpatialEntityAlignment()
Virtual destructor.
Definition: SpatialEntityAlignment.hpp:107
CDPL::Chem::SpatialEntityAlignment::getEntityWeightFunction
const EntityWeightFunction & getEntityWeightFunction() const
Returns the function that was registered for the retrieval of entity weights for spatial alignment.
Definition: SpatialEntityAlignment.hpp:364
ObjectStack.hpp
Definition of the class CDPL::Util::ObjectStack.
CDPL::Chem::SpatialEntityAlignment::getEntityMatchFunction
const EntityMatchFunction & getEntityMatchFunction() const
Returns the function that was registered for restricting allowed topological entity mappings.
Definition: SpatialEntityAlignment.hpp:391
CDPL::Chem::SpatialEntityAlignment::exhaustiveSearchPerformed
bool exhaustiveSearchPerformed() const
Definition: SpatialEntityAlignment.hpp:417
CMatrix< double, 4, 4 >
CDPL::Math::DMatrix
Matrix< double > DMatrix
An unbounded dense matrix holding floating point values of type double..
Definition: Matrix.hpp:1814
CDPL::Math::column
MatrixColumn< M > column(MatrixExpression< M > &e, typename MatrixColumn< M >::SizeType j)
Definition: MatrixProxy.hpp:730
CDPL::Math::Vector3D
CVector< double, 3 > Vector3D
A bounded 3 element vector holding floating point values of type double.
Definition: Vector.hpp:1637
CDPL::Chem::SpatialEntityAlignment::getEntity3DCoordinatesFunction
const Entity3DCoordinatesFunction & getEntity3DCoordinatesFunction() const
Returns the function that was registered for the retrieval of entity 3D-coordinates.
Definition: SpatialEntityAlignment.hpp:350
CDPL::Chem::TopologicalEntityAlignment
TopologicalEntityAlignment.
Definition: TopologicalEntityAlignment.hpp:54
CDPL::Chem::SpatialEntityAlignment
SpatialEntityAlignment.
Definition: SpatialEntityAlignment.hpp:59
CDPL::Chem::SpatialEntityAlignment::getNumEntities
std::size_t getNumEntities(bool first_set) const
Returns the number of entities in the specified alignment entity set.
Definition: SpatialEntityAlignment.hpp:423
CDPL::Util::Array
A dynamic array class providing amortized constant time access to arbitrary elements.
Definition: Array.hpp:92
CDPL::Chem::TopologicalEntityAlignment< Feature >::EntityMatchFunction
std::function< bool(const EntityType &, const EntityType &)> EntityMatchFunction
A generic wrapper class used to store a user-defined entity match constraint function.
Definition: TopologicalEntityAlignment.hpp:75
CDPL::Math::Matrix4D
CMatrix< double, 4, 4 > Matrix4D
A bounded 4x4 matrix holding floating point values of type double.
Definition: Matrix.hpp:1854
bool
CDPL::Util::Array::clear
void clear()
Erases all elements.
Definition: Array.hpp:732
CDPL::Chem::SpatialEntityAlignment::getMinTopologicalMappingSize
std::size_t getMinTopologicalMappingSize()
Returns the minimum number of topologically mapped entities that is required to enable a subsequent s...
Definition: SpatialEntityAlignment.hpp:336
CDPL::Chem::SpatialEntityAlignment::getEntitiesEnd
ConstEntityIterator getEntitiesEnd(bool first_set) const
Returns a constant iterator pointing to the end of the entities stored in the specified set.
Definition: SpatialEntityAlignment.hpp:451
double
CDPL::Util::Array::addElement
void addElement(const ValueType &value=ValueType())
Inserts a new element at the end of the array.
Definition: Array.hpp:757
CDPL::Chem::SpatialEntityAlignment::setTopAlignmentConstraintFunction
void setTopAlignmentConstraintFunction(const TopologicalAlignmentConstraintFunction &func)
Specifies a function for restricting allowed topological entity alignments.
Definition: SpatialEntityAlignment.hpp:370
CDPL::Math::DVector
Vector< double > DVector
An unbounded dense vector holding floating point values of type double.
Definition: Vector.hpp:1687
CDPL::Util::Array::getSize
std::size_t getSize() const
Returns the number of elements stored in the array.
Definition: Array.hpp:696
CDPL::Chem::SpatialEntityAlignment::ConstEntityIterator
TopologicalAlignment::ConstEntityIterator ConstEntityIterator
A constant iterator over the stored entities.
Definition: SpatialEntityAlignment.hpp:72
CDPL::Math::transform
void transform(VectorArray< CVector< T, Dim > > &va, const CMatrix< T1, Dim, Dim > &xform)
Transforms each -dimensional vector in the array with the -dimensional square matrix xform.
Definition: VectorArrayFunctions.hpp:51
CDPL::Util::Array::ConstElementIterator
StorageType::const_iterator ConstElementIterator
A constant random access iterator used to iterate over the elements of the array.
Definition: Array.hpp:125
CDPL::Chem::SpatialEntityAlignment::setMinTopologicalMappingSize
void setMinTopologicalMappingSize(std::size_t min_size)
Specifies the minimum number of topologically mapped entities that is required to enable a subsequent...
Definition: SpatialEntityAlignment.hpp:329
CDPL::Math::Vector3DArray
VectorArray< Vector3D > Vector3DArray
An array of Math::Vector3D objects.
Definition: VectorArray.hpp:84
CDPL::Chem::CIPDescriptor::m
const unsigned int m
Specifies that the stereocenter has m configuration.
Definition: CIPDescriptor.hpp:116
CDPL::Chem::SpatialEntityAlignment::EntityType
T EntityType
The actual entity type.
Definition: SpatialEntityAlignment.hpp:67
CDPL::Util::STPairArray
Array< STPair > STPairArray
An array of pairs of unsigned integers of type std::size_t.
Definition: Array.hpp:582
CDPL::Chem::SpatialEntityAlignment::setEntity3DCoordinatesFunction
void setEntity3DCoordinatesFunction(const Entity3DCoordinatesFunction &func)
Specifies a function for the retrieval of entity 3D-coordinates.
Definition: SpatialEntityAlignment.hpp:342
CDPL::Chem::SpatialEntityAlignment::reset
void reset()
Definition: SpatialEntityAlignment.hpp:464
CDPL::Chem::AtomType::T
const unsigned int T
Specifies Hydrogen (Tritium).
Definition: AtomType.hpp:67
KabschAlgorithm.hpp
Implementation of the Kabsch algorithm.
CDPL::Chem::SpatialEntityAlignment::getTopAlignmentConstraintFunction
const TopologicalAlignmentConstraintFunction & getTopAlignmentConstraintFunction() const
Returns the function that was registered for restricting allowed topological entity alignments.
Definition: SpatialEntityAlignment.hpp:378
CDPL::Chem::SpatialEntityAlignment::getEntity
const EntityType & getEntity(std::size_t idx, bool first_set) const
Returns a non-const reference to the stored entity at index idx in the specified set.
Definition: SpatialEntityAlignment.hpp:458
CDPL::Chem::SpatialEntityAlignment::clearEntities
void clearEntities(bool first_set)
Removes all entities in the specified alignment entity set.
Definition: SpatialEntityAlignment.hpp:436
CDPL::Chem::SpatialEntityAlignment::setEntityWeightFunction
void setEntityWeightFunction(const EntityWeightFunction &func)
Specifies a function for the retrieval of entity weights for spatial alignment.
Definition: SpatialEntityAlignment.hpp:356
CDPL
The namespace of the Chemical Data Processing Library.
CDPL::Chem::SpatialEntityAlignment::EntityWeightFunction
std::function< double(const EntityType &)> EntityWeightFunction
A generic wrapper class used to store a user-defined entity alignment weight function.
Definition: SpatialEntityAlignment.hpp:87
CDPL::Chem::SpatialEntityAlignment::addEntity
void addEntity(const EntityType &entity, bool first_set)
Adds an entity to the specified alignment entity set.
Definition: SpatialEntityAlignment.hpp:429
CDPL::Chem::SpatialEntityAlignment::SpatialEntityAlignment
SpatialEntityAlignment()
Constructs the SpatialEntityAlignment instance.
Definition: SpatialEntityAlignment.hpp:322
CDPL::Chem::SpatialEntityAlignment::getEntitiesBegin
ConstEntityIterator getEntitiesBegin(bool first_set) const
Returns a constant iterator pointing to the beginning of the entities stored in the specified set.
Definition: SpatialEntityAlignment.hpp:444
CDPL::Chem::TopologicalEntityAlignment< Feature >::ConstEntityIterator
boost::indirect_iterator< typename EntitySet::const_iterator, const EntityType > ConstEntityIterator
A constant iterator over the stored entities.
Definition: TopologicalEntityAlignment.hpp:70
CDPL::Chem::SpatialEntityAlignment::setEntityMatchFunction
void setEntityMatchFunction(const EntityMatchFunction &func)
Specifies a function for restricting allowed topological entity mappings in the search for alignment ...
Definition: SpatialEntityAlignment.hpp:384
CDPL::Chem::SpatialEntityAlignment::setEntityPairMatchFunction
void setEntityPairMatchFunction(const EntityPairMatchFunction &func)
Specifies a function for checking the compatibility of entity-pairs in the search for alignment solut...
Definition: SpatialEntityAlignment.hpp:397
Matrix.hpp
Definition of matrix data types.
CDPL::Chem::SpatialEntityAlignment::getTransform
const Math::Matrix4D & getTransform() const
Returns the alignment transformation matrix that was calculated in the last successful call to nextAl...
Definition: SpatialEntityAlignment.hpp:553
CDPL::Chem::SpatialEntityAlignment::EntityMatchFunction
TopologicalAlignment::EntityMatchFunction EntityMatchFunction
A generic wrapper class used to store a user-defined topological entity match constraint function.
Definition: SpatialEntityAlignment.hpp:92
CDPL::Chem::SpatialEntityAlignment::EntityPairMatchFunction
TopologicalAlignment::EntityPairMatchFunction EntityPairMatchFunction
A generic wrapper class used to store a user-defined entity-pair match constraint function.
Definition: SpatialEntityAlignment.hpp:97
CDPL::Chem::SpatialEntityAlignment::nextAlignment
bool nextAlignment()
Searches for the next alignment solution.
Definition: SpatialEntityAlignment.hpp:470
CDPL::Chem::SpatialEntityAlignment::performExhaustiveSearch
void performExhaustiveSearch(bool exhaustive)
Definition: SpatialEntityAlignment.hpp:410
CDPL::Chem::SpatialEntityAlignment::getEntityPairMatchFunction
const EntityPairMatchFunction & getEntityPairMatchFunction() const
Returns the function that was registered for checking the compatibility of entity-pairs.
Definition: SpatialEntityAlignment.hpp:404
TopologicalEntityAlignment.hpp
Definition of the class CDPL::Chem::TopologicalEntityAlignment.
CDPL::Chem::SpatialEntityAlignment::TopologicalAlignmentConstraintFunction
std::function< bool(const Util::STPairArray &)> TopologicalAlignmentConstraintFunction
A generic wrapper class used to store a user-defined predicate to restrict allowed topological entity...
Definition: SpatialEntityAlignment.hpp:77
Vector.hpp
Definition of vector data types.
CDPL::Chem::SpatialEntityAlignment< Feature >::Entity3DCoordinatesFunction
std::function< const Math::Vector3D &(const EntityType &)> Entity3DCoordinatesFunction
A generic wrapper class used to store a user-defined entity 3D-coordinates function.
Definition: SpatialEntityAlignment.hpp:82
CDPL::Chem::SpatialEntityAlignment::getTopologicalMapping
const Util::STPairArray & getTopologicalMapping() const
Returns the topological entity mapping resulting from the last successful call to nextAlignment().
Definition: SpatialEntityAlignment.hpp:560