IMP  2.2.1
The Integrative Modeling Platform
MetricClosePairsFinder.h
Go to the documentation of this file.
1 /**
2  * \file IMP/misc/MetricClosePairsFinder.h
3  * \brief Decorator for a sphere-like particle.
4  *
5  * Copyright 2007-2014 IMP Inventors. All rights reserved.
6  *
7  */
8 
9 #ifndef IMPMISC_METRIC_CLOSE_PAIRS_FINDER_H
10 #define IMPMISC_METRIC_CLOSE_PAIRS_FINDER_H
11 
12 #include <IMP/misc/misc_config.h>
14 #include <IMP/base/Pointer.h>
16 #include <boost/unordered_map.hpp>
17 #include <algorithm>
18 #include <limits>
19 
20 IMPMISC_BEGIN_NAMESPACE
21 
22 /** A close pairs finder that only depends on metrics on the underlying
23  particles. As a result, it should be usable with weird metrics (eg ones
24  that incude symmetry).
25 
26  The LowerBound template should be a functors that bounds the
27  distance between two particles. For example the LowerBound
28  distance between two balls is the center distance minus the radii,
29  and the upperbound distance is the center distance plus the
30  radii. They signature should be `double operator()(kernel::Model *m, const
31  kernel::ParticleIndexPair &pip) const`
32 
33  The algorithm works by building an index used `sqrt(n)` of the `n` input
34  particles, assigning each particle to a bucked based on the closest index
35  particle, and then checking for close pairs in buckets such that they can
36  be close enough.
37 
38  If we need something more involved, we can try
39  [this paper](http://dimitris-agrafiotis.com/Papers/ci034150f.pdf).
40  */
41 template <class LowerBound, class UpperBound>
43  LowerBound lb_;
44  UpperBound ub_;
45 
46  IMP_NAMED_TUPLE_2(Data, Datas, kernel::ParticleIndexes, indexes, double,
47  width, );
48 
49  typedef boost::unordered_map<kernel::ParticleIndex, Data> Index;
50  Index get_index(kernel::Model *m, kernel::ParticleIndexes inputs) const {
51  unsigned int index_size = std::min<unsigned int>(
52  1U, std::sqrt(static_cast<double>(inputs.size())));
53  std::random_shuffle(inputs.begin(), inputs.end());
54  Index ret;
55  kernel::ParticleIndexes indexes(inputs.begin(),
56  inputs.begin() + index_size);
57  for (unsigned int i = 0; i < index_size; ++i) {
58  ret[inputs[i]] = Data(kernel::ParticleIndexes(), 0.0);
59  }
60  IMP_LOG_VERBOSE("Index points are " << indexes << std::endl);
61  for (unsigned int i = 0; i < inputs.size(); ++i) {
62  double min_dist = std::numeric_limits<double>::max();
63  kernel::ParticleIndex min_index;
64  for (unsigned int j = 0; j < indexes.size(); ++j) {
66  lb_(m, kernel::ParticleIndexPair(inputs[i], indexes[j])) <=
67  ub_(m, kernel::ParticleIndexPair(inputs[i], indexes[j])),
68  "The bounds are not ordered.");
69  double cur_dist =
70  ub_(m, kernel::ParticleIndexPair(inputs[i], indexes[j]));
71  if (cur_dist < min_dist) {
72  min_index = indexes[j];
73  min_dist = cur_dist;
74  }
75  }
76  ret[min_index].access_indexes().push_back(inputs[i]);
77  ret[min_index].set_width(std::min(min_dist, ret[min_index].get_width()));
78  }
79  for (typename Index::const_iterator it = ret.begin(); it != ret.end();
80  ++it) {
81  IMP_LOG_VERBOSE(it->first << ": " << it->second << std::endl);
82  }
83  return ret;
84  }
85  kernel::ParticleIndexPairs get_close_pairs_internal(
86  kernel::Model *m, const kernel::ParticleIndexes &p) const {
88  for (unsigned int i = 0; i < p.size(); ++i) {
89  for (unsigned int j = 0; j < i; ++j) {
90  IMP_USAGE_CHECK(lb_(m, kernel::ParticleIndexPair(p[i], p[j])) <=
91  ub_(m, kernel::ParticleIndexPair(p[i], p[j])),
92  "The bounds are not ordered.");
93  if (lb_(m, kernel::ParticleIndexPair(p[i], p[j])) < get_distance()) {
94  ret.push_back(kernel::ParticleIndexPair(p[i], p[j]));
95  }
96  }
97  }
98  return ret;
99  }
100  kernel::ParticleIndexPairs get_close_pairs_internal(
102  const kernel::ParticleIndexes &pb) const {
104  for (unsigned int i = 0; i < pa.size(); ++i) {
105  for (unsigned int j = 0; j < pb.size(); ++j) {
106  IMP_USAGE_CHECK(lb_(m, kernel::ParticleIndexPair(pa[i], pb[j])) <=
107  ub_(m, kernel::ParticleIndexPair(pa[i], pb[j])),
108  "The bounds are not ordered.");
109  if (lb_(m, kernel::ParticleIndexPair(pa[i], pb[j])) < get_distance()) {
110  ret.push_back(kernel::ParticleIndexPair(pa[i], pb[j]));
111  }
112  }
113  }
114  return ret;
115  }
116  kernel::ParticleIndexPairs get_close_pairs_internal(kernel::Model *m,
117  const Index &ia,
118  const Index &ib,
119  bool is_same) const {
121  for (typename Index::const_iterator ita = ia.begin(); ita != ia.end();
122  ++ita) {
123  for (typename Index::const_iterator itb = ib.begin(); itb != ib.end();
124  ++itb) {
125  if (is_same) {
126  if (ita->first < itb->first) continue;
127  if (ita->first == itb->first) {
128  ret += get_close_pairs_internal(m, ita->second.get_indexes());
129  continue;
130  }
131  }
133  lb_(m, kernel::ParticleIndexPair(ita->first, itb->first)) <=
134  ub_(m, kernel::ParticleIndexPair(ita->first, itb->first)),
135  "The bounds are not ordered.");
136  if (lb_(m, kernel::ParticleIndexPair(ita->first, itb->first)) -
137  ita->second.get_width() - itb->second.get_width()) {
138  ret += get_close_pairs_internal(m, ita->second.get_indexes(),
139  itb->second.get_indexes());
140  }
141  }
142  }
143  return ret;
144  }
145 
146  public:
147  MetricClosePairsFinder(LowerBound lb, UpperBound ub,
148  std::string name = "MetricClosePairsFinder%1%")
149  : core::ClosePairsFinder(name), lb_(lb), ub_(ub) {}
150 #ifndef SWIG
151  using ClosePairsFinder::get_close_pairs;
152 #else
153  kernel::ParticlePairsTemp get_close_pairs(const kernel::ParticlesTemp &pc)
154  const;
155  kernel::ParticlePairsTemp get_close_pairs(
156  const kernel::ParticlesTemp &pca, const kernel::ParticlesTemp &pcb) const;
157 #endif
158  /** Not supported.*/
160  IMP_OVERRIDE {
161  IMP_FAILURE("Bounding boxes are not supported.");
162  }
163  /** Not supported.*/
165  const algebra::BoundingBox3Ds &) const
166  IMP_OVERRIDE {
167  IMP_FAILURE("Bounding boxes are not supported.");
168  }
169 
170  virtual kernel::ParticleIndexPairs get_close_pairs(
171  kernel::Model *m, const kernel::ParticleIndexes &pc) const IMP_OVERRIDE {
173  if (pc.empty()) return kernel::ParticleIndexPairs();
174  Index index = get_index(m, pc);
175  return get_close_pairs_internal(m, index, index, true);
176  }
177  virtual kernel::ParticleIndexPairs get_close_pairs(
178  kernel::Model *m, const kernel::ParticleIndexes &pca,
179  const kernel::ParticleIndexes &pcb) const IMP_OVERRIDE {
181  if (pca.empty() || pcb.empty()) return kernel::ParticleIndexPairs();
182  Index indexa = get_index(m, pca);
183  Index indexb = get_index(m, pcb);
184  return get_close_pairs_internal(m, indexa, indexb, false);
185  }
187  kernel::Model *m, const kernel::ParticleIndexes &pis) const IMP_OVERRIDE {
188  // for now assume we just read the particles
189  return IMP::kernel::get_particles(m, pis);
190  }
191 
193 };
194 
195 /** Create a new MetricClosePairsFinder, handling types. */
196 template <class LowerBound, class UpperBound>
198  UpperBound ub) {
200 }
201 
202 IMPMISC_END_NAMESPACE
203 
204 #endif /* IMPMISC_METRIC_CLOSE_PAIRS_FINDER_H */
virtual IntPairs get_close_pairs(const algebra::BoundingBox3Ds &, const algebra::BoundingBox3Ds &) const
Various general useful functions for IMP.
Ints get_index(const kernel::ParticlesTemp &particles, const Subset &subset, const Subsets &excluded)
A base class for algorithms to find spatial proximities.
A nullptr-initialized pointer to an IMP Object.
ParticlesTemp get_particles(kernel::Model *m, const ParticleIndexes &ps)
virtual IntPairs get_close_pairs(const algebra::BoundingBox3Ds &) const
#define IMP_USAGE_CHECK(expr, message)
A runtime test for incorrect usage of a class or method.
virtual kernel::ModelObjectsTemp do_get_inputs(kernel::Model *m, const kernel::ParticleIndexes &pis) const
A class to store an fixed array of same-typed values.
Definition: base/Array.h:33
double get_distance(const Plane3D &pln, const Vector3D &p)
Return the distance between a plane and a point in 3D.
Definition: Plane3D.h:67
#define IMP_OBJECT_METHODS(Name)
Define the basic things needed by any Object.
#define IMP_OBJECT_LOG
Set the log level to the object's log level.
core::ClosePairsFinder * create_metric_close_pairs_finder(LowerBound lb, UpperBound ub)
A base class for algorithms to detect proximities.
#define IMP_FAILURE(message)
A runtime failure for IMP.
#define IMP_LOG_VERBOSE(expr)
Class for storing model, its restraints, constraints, and particles.
Definition: kernel/Model.h:72