Chemical Data Processing Library C++ API - Version 1.1.1
TopologicalEntityAlignment.hpp
Go to the documentation of this file.
1 /*
2  * TopologicalEntityAlignment.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_TOPOLOGICALENTITYALIGNMENT_HPP
30 #define CDPL_CHEM_TOPOLOGICALENTITYALIGNMENT_HPP
31 
32 #include <cstddef>
33 #include <vector>
34 #include <functional>
35 
36 #include <boost/iterator/indirect_iterator.hpp>
37 
39 #include "CDPL/Util/Array.hpp"
40 #include "CDPL/Base/Exceptions.hpp"
41 
42 
43 namespace CDPL
44 {
45 
46  namespace Chem
47  {
48 
52  template <typename T>
54  {
55 
56  public:
60  typedef T EntityType;
61 
65  typedef std::vector<const EntityType*> EntitySet;
66 
70  typedef boost::indirect_iterator<typename EntitySet::const_iterator, const EntityType> ConstEntityIterator;
71 
75  typedef std::function<bool(const EntityType&, const EntityType&)> EntityMatchFunction;
76 
80  typedef std::function<bool(const EntityType&, const EntityType&, const EntityType&, const EntityType&)> EntityPairMatchFunction;
81 
86  changes(true) {}
87 
92 
98 
104 
111 
117 
124  void addEntity(const EntityType& entity, bool first_set);
125 
130  void clearEntities(bool first_set);
131 
136  std::size_t getNumEntities(bool first_set) const;
137 
143  ConstEntityIterator getEntitiesBegin(bool first_set) const;
144 
150  ConstEntityIterator getEntitiesEnd(bool first_set) const;
151 
159  const EntityType& getEntity(std::size_t idx, bool first_set) const;
160 
168 
169  void reset();
170 
171  private:
172  void init();
173 
174  typedef std::vector<Util::STPair> CompatGraphNodeArray;
175 
176  EntityMatchFunction entityMatchFunc;
177  EntityPairMatchFunction entityPairMatchFunc;
178  Util::BronKerboschAlgorithm bkAlgorithm;
179  CompatGraphNodeArray compatGraphNodes;
180  Util::BitSetArray adjMatrix;
181  Util::BitSet clique;
182  EntitySet firstEntities;
183  EntitySet secondEntities;
184  bool changes;
185  };
186  } // namespace Chem
187 } // namespace CDPL
188 
189 
190 // Implementation
191 
192 template <typename T>
194 {
195  entityMatchFunc = func;
196  changes = true;
197 }
198 
199 template <typename T>
202 {
203  return entityMatchFunc;
204 }
205 
206 template <typename T>
208 {
209  entityPairMatchFunc = func;
210  changes = true;
211 }
212 
213 template <typename T>
216 {
217  return entityPairMatchFunc;
218 }
219 
220 template <typename T>
222 {
223  return (first_set ? firstEntities : secondEntities).size();
224 }
225 
226 template <typename T>
228 {
229  (first_set ? firstEntities : secondEntities).push_back(&entity);
230  changes = true;
231 }
232 
233 template <typename T>
235 {
236  (first_set ? firstEntities : secondEntities).clear();
237  changes = true;
238 }
239 
240 template <typename T>
243 {
244  return (first_set ? firstEntities : secondEntities).begin();
245 }
246 
247 template <typename T>
250 {
251  return (first_set ? firstEntities : secondEntities).end();
252 }
253 
254 template <typename T>
256 CDPL::Chem::TopologicalEntityAlignment<T>::getEntity(std::size_t idx, bool first_set) const
257 {
258  const EntitySet& entity_set = (first_set ? firstEntities : secondEntities);
259 
260  if (idx >= entity_set.size())
261  throw Base::IndexError("TopologicalEntityAlignment: entity index out of bounds");
262 
263  return *entity_set[idx];
264 }
265 
266 template <typename T>
268 {
269  compatGraphNodes.clear();
270 
271  if (entityMatchFunc) {
272  std::size_t i = 0;
273 
274  for (typename EntitySet::const_iterator it1 = firstEntities.begin(), end1 = firstEntities.end(); it1 != end1; ++it1, i++) {
275  const EntityType* ent1 = *it1;
276  std::size_t j = 0;
277 
278  for (typename EntitySet::const_iterator it2 = secondEntities.begin(), end2 = secondEntities.end(); it2 != end2; ++it2, j++)
279  if (entityMatchFunc(*ent1, **it2))
280  compatGraphNodes.push_back(Util::STPair(i, j));
281  }
282 
283  } else {
284  for (std::size_t i = 0, num_ents1 = firstEntities.size(); i < num_ents1; i++)
285  for (std::size_t j = 0, num_ents2 = secondEntities.size(); j < num_ents2; j++)
286  compatGraphNodes.push_back(Util::STPair(i, j));
287  }
288 
289  std::size_t num_nodes = compatGraphNodes.size();
290 
291  adjMatrix.resize(num_nodes);
292 
293  for (std::size_t i = 0; i < num_nodes; i++) {
294  adjMatrix[i].resize(num_nodes);
295  adjMatrix[i].reset();
296  }
297 
298  for (std::size_t i = 0; i < num_nodes; i++) {
299  const Util::STPair& p1 = compatGraphNodes[i];
300 
301  for (std::size_t j = i + 1; j < num_nodes; j++) {
302  const Util::STPair& p2 = compatGraphNodes[j];
303 
304  if (p1.first == p2.first)
305  continue;
306 
307  if (p1.second == p2.second)
308  continue;
309 
310  if (!entityPairMatchFunc || entityPairMatchFunc(*firstEntities[p1.first], *firstEntities[p2.first],
311  *secondEntities[p1.second], *secondEntities[p2.second])) {
312  adjMatrix[i].set(j);
313  adjMatrix[j].set(i);
314  }
315  }
316  }
317 
318  bkAlgorithm.init(adjMatrix);
319 
320  changes = false;
321 }
322 
323 template <typename T>
325 {
326  if (changes)
327  init();
328 
329  if (!bkAlgorithm.nextClique(clique))
330  return false;
331 
332  mapping.clear();
333 
334  for (std::size_t i = clique.find_first(); i != Util::BitSet::npos; i = clique.find_next(i))
335  mapping.addElement(compatGraphNodes[i]);
336 
337  return true;
338 }
339 
340 template <typename T>
342 {
343  changes = true;
344 }
345 
346 #endif // CDPL_CHEM_TOPOLOGICALENTITYALIGNMENT_HPP
CDPL::Chem::TopologicalEntityAlignment::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
BronKerboschAlgorithm.hpp
Implementation of the Bron-Kerbosch algorithm.
CDPL::Chem::TopologicalEntityAlignment::TopologicalEntityAlignment
TopologicalEntityAlignment()
Constructs the TopologicalEntityAlignment instance.
Definition: TopologicalEntityAlignment.hpp:85
CDPL::Chem::TopologicalEntityAlignment::reset
void reset()
Definition: TopologicalEntityAlignment.hpp:341
CDPL::Chem::TopologicalEntityAlignment::EntityType
T EntityType
The actual entity type.
Definition: TopologicalEntityAlignment.hpp:60
CDPL::Chem::TopologicalEntityAlignment::getEntityMatchFunction
const EntityMatchFunction & getEntityMatchFunction() const
Returns the function that was registered for restricting allowed entity mappings.
Definition: TopologicalEntityAlignment.hpp:201
CDPL::Chem::TopologicalEntityAlignment
TopologicalEntityAlignment.
Definition: TopologicalEntityAlignment.hpp:54
CDPL::Chem::TopologicalEntityAlignment::getEntityPairMatchFunction
const EntityPairMatchFunction & getEntityPairMatchFunction() const
Returns the function that was registered for checking the compatibility of entity-pairs.
Definition: TopologicalEntityAlignment.hpp:215
CDPL::Util::BitSet
boost::dynamic_bitset BitSet
A dynamic bitset class.
Definition: BitSet.hpp:46
CDPL::Chem::TopologicalEntityAlignment::EntitySet
std::vector< const EntityType * > EntitySet
The container storing the entities to align.
Definition: TopologicalEntityAlignment.hpp:65
CDPL::Util::Array
A dynamic array class providing amortized constant time access to arbitrary elements.
Definition: Array.hpp:92
CDPL::Chem::TopologicalEntityAlignment::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::Chem::TopologicalEntityAlignment::getEntitiesBegin
ConstEntityIterator getEntitiesBegin(bool first_set) const
Returns a constant iterator pointing to the beginning of the entities stored in the specified set.
Definition: TopologicalEntityAlignment.hpp:242
CDPL::Util::BronKerboschAlgorithm
Implementation of the Bron-Kerbosch clique-detection algorithm [BKA].
Definition: BronKerboschAlgorithm.hpp:49
CDPL::Chem::TopologicalEntityAlignment::setEntityPairMatchFunction
void setEntityPairMatchFunction(const EntityPairMatchFunction &func)
Specifies a function for checking the compatibility of entity-pairs in the search for alignment solut...
Definition: TopologicalEntityAlignment.hpp:207
bool
CDPL::Util::Array::clear
void clear()
Erases all elements.
Definition: Array.hpp:732
CDPL::Base::IndexError
Thrown to indicate that an index is out of range.
Definition: Base/Exceptions.hpp:152
Array.hpp
Definition of the class CDPL::Util::Array.
CDPL::Chem::TopologicalEntityAlignment::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: TopologicalEntityAlignment.hpp:256
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::TopologicalEntityAlignment::nextAlignment
bool nextAlignment(Util::STPairArray &mapping)
Searches for the next alignment solution and stores the corresponding mapping of the entities in the ...
Definition: TopologicalEntityAlignment.hpp:324
Array< BitSet >
CDPL::Chem::AtomType::T
const unsigned int T
Specifies Hydrogen (Tritium).
Definition: AtomType.hpp:67
Exceptions.hpp
Definition of exception classes.
CDPL::Chem::TopologicalEntityAlignment::addEntity
void addEntity(const EntityType &entity, bool first_set)
Adds an entity to the specified alignment entity set.
Definition: TopologicalEntityAlignment.hpp:227
CDPL
The namespace of the Chemical Data Processing Library.
CDPL::Chem::TopologicalEntityAlignment::getNumEntities
std::size_t getNumEntities(bool first_set) const
Returns the number of entities in the specified alignment entity set.
Definition: TopologicalEntityAlignment.hpp:221
CDPL::Chem::TopologicalEntityAlignment::getEntitiesEnd
ConstEntityIterator getEntitiesEnd(bool first_set) const
Returns a constant iterator pointing to the end of the entities stored in the specified set.
Definition: TopologicalEntityAlignment.hpp:249
CDPL::Chem::TopologicalEntityAlignment::ConstEntityIterator
boost::indirect_iterator< typename EntitySet::const_iterator, const EntityType > ConstEntityIterator
A constant iterator over the stored entities.
Definition: TopologicalEntityAlignment.hpp:70
CDPL::Chem::TopologicalEntityAlignment::setEntityMatchFunction
void setEntityMatchFunction(const EntityMatchFunction &func)
Specifies a function for restricting allowed entity mappings in the search for alignment solutions.
Definition: TopologicalEntityAlignment.hpp:193
CDPL::Chem::TopologicalEntityAlignment::clearEntities
void clearEntities(bool first_set)
Removes all entities in the specified alignment entity set.
Definition: TopologicalEntityAlignment.hpp:234
CDPL::Util::STPair
std::pair< std::size_t, std::size_t > STPair
A pair of unsigned integers of type std::size_t.
Definition: Array.hpp:577
CDPL::Chem::TopologicalEntityAlignment::~TopologicalEntityAlignment
virtual ~TopologicalEntityAlignment()
Virtual destructor.
Definition: TopologicalEntityAlignment.hpp:91