IMP logo
IMP Reference Guide  2.20.2
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-2022 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/Pointer.h>
15 #include <IMP/random.h>
16 #include <IMP/particle_index.h>
17 #include <boost/unordered_map.hpp>
18 #include <algorithm>
19 #include <limits>
20 
21 IMPMISC_BEGIN_NAMESPACE
22 
23 /** A close pairs finder that only depends on metrics on the underlying
24  particles. As a result, it should be usable with weird metrics (eg ones
25  that include symmetry).
26 
27  The LowerBound and UpperBound templates should be functors that bound the
28  distance between two particles. For example the LowerBound
29  distance between two balls is the center distance minus the radii,
30  and the UpperBound distance is the center distance plus the
31  radii. The signature should be `double operator()(Model *m, const
32  ParticleIndexPair &pip) const`
33 
34  The algorithm works by building an index using `sqrt(n)` of the `n` input
35  particles, assigning each particle to a bucket based on the closest index
36  particle, and then checking for close pairs in buckets such that they can
37  be close enough.
38 
39  If we need something more involved, we can try
40  [this paper](https://pubs.acs.org/doi/abs/10.1021/ci034150f)
41  */
42 template <class LowerBound, class UpperBound>
44  LowerBound lb_;
45  UpperBound ub_;
46 
47  IMP_NAMED_TUPLE_2(Data, Datas, ParticleIndexes, indexes, double,
48  width, );
49 
50  typedef boost::unordered_map<ParticleIndex, Data> Index;
51  Index get_index(Model *m, ParticleIndexes inputs) const {
52  unsigned int index_size = std::min<unsigned int>(
53  1U, std::sqrt(static_cast<double>(inputs.size())));
54 #if IMP_COMPILER_HAS_RANDOM_SHUFFLE
55  std::random_shuffle(inputs.begin(), inputs.end());
56 #else
57  std::shuffle(inputs.begin(), inputs.end(), random_number_generator);
58 #endif
59  Index ret;
60  ParticleIndexes indexes(inputs.begin(),
61  inputs.begin() + index_size);
62  for (unsigned int i = 0; i < index_size; ++i) {
63  ret[inputs[i]] = Data(ParticleIndexes(), 0.0);
64  }
65  IMP_LOG_VERBOSE("Index points are " << indexes << std::endl);
66  for (unsigned int i = 0; i < inputs.size(); ++i) {
67  double min_dist = std::numeric_limits<double>::max();
68  ParticleIndex min_index;
69  for (unsigned int j = 0; j < indexes.size(); ++j) {
71  lb_(m, ParticleIndexPair(inputs[i], indexes[j])) <=
72  ub_(m, ParticleIndexPair(inputs[i], indexes[j])),
73  "The bounds are not ordered.");
74  double cur_dist =
75  ub_(m, ParticleIndexPair(inputs[i], indexes[j]));
76  if (cur_dist < min_dist) {
77  min_index = indexes[j];
78  min_dist = cur_dist;
79  }
80  }
81  ret[min_index].access_indexes().push_back(inputs[i]);
82  ret[min_index].set_width(std::min(min_dist, ret[min_index].get_width()));
83  }
84  for (typename Index::const_iterator it = ret.begin(); it != ret.end();
85  ++it) {
86  IMP_LOG_VERBOSE(it->first << ": " << it->second << std::endl);
87  }
88  return ret;
89  }
90  ParticleIndexPairs get_close_pairs_internal(
91  Model *m, const ParticleIndexes &p) const {
93  for (unsigned int i = 0; i < p.size(); ++i) {
94  for (unsigned int j = 0; j < i; ++j) {
95  IMP_USAGE_CHECK(lb_(m, ParticleIndexPair(p[i], p[j])) <=
96  ub_(m, ParticleIndexPair(p[i], p[j])),
97  "The bounds are not ordered.");
98  if (lb_(m, ParticleIndexPair(p[i], p[j])) < get_distance()) {
99  ret.push_back(ParticleIndexPair(p[i], p[j]));
100  }
101  }
102  }
103  return ret;
104  }
105  ParticleIndexPairs get_close_pairs_internal(
106  Model *m, const ParticleIndexes &pa,
107  const ParticleIndexes &pb) const {
108  ParticleIndexPairs ret;
109  for (unsigned int i = 0; i < pa.size(); ++i) {
110  for (unsigned int j = 0; j < pb.size(); ++j) {
111  IMP_USAGE_CHECK(lb_(m, ParticleIndexPair(pa[i], pb[j])) <=
112  ub_(m, ParticleIndexPair(pa[i], pb[j])),
113  "The bounds are not ordered.");
114  if (lb_(m, ParticleIndexPair(pa[i], pb[j])) < get_distance()) {
115  ret.push_back(ParticleIndexPair(pa[i], pb[j]));
116  }
117  }
118  }
119  return ret;
120  }
121  ParticleIndexPairs get_close_pairs_internal(Model *m,
122  const Index &ia,
123  const Index &ib,
124  bool is_same) const {
125  ParticleIndexPairs ret;
126  for (typename Index::const_iterator ita = ia.begin(); ita != ia.end();
127  ++ita) {
128  for (typename Index::const_iterator itb = ib.begin(); itb != ib.end();
129  ++itb) {
130  if (is_same) {
131  if (ita->first < itb->first) continue;
132  if (ita->first == itb->first) {
133  ret += get_close_pairs_internal(m, ita->second.get_indexes());
134  continue;
135  }
136  }
138  lb_(m, ParticleIndexPair(ita->first, itb->first)) <=
139  ub_(m, ParticleIndexPair(ita->first, itb->first)),
140  "The bounds are not ordered.");
141  if (lb_(m, ParticleIndexPair(ita->first, itb->first)) -
142  ita->second.get_width() - itb->second.get_width()) {
143  ret += get_close_pairs_internal(m, ita->second.get_indexes(),
144  itb->second.get_indexes());
145  }
146  }
147  }
148  return ret;
149  }
150 
151  public:
152  MetricClosePairsFinder(LowerBound lb, UpperBound ub,
153  std::string name = "MetricClosePairsFinder%1%")
154  : core::ClosePairsFinder(name), lb_(lb), ub_(ub) {}
155  /** Not supported.*/
157  override {
158  IMP_FAILURE("Bounding boxes are not supported.");
159  }
160  /** Not supported.*/
162  const algebra::BoundingBox3Ds &) const
163  override {
164  IMP_FAILURE("Bounding boxes are not supported.");
165  }
166 
168  Model *m, const ParticleIndexes &pc) const override {
170  if (pc.empty()) return ParticleIndexPairs();
171  Index index = get_index(m, pc);
172  return get_close_pairs_internal(m, index, index, true);
173  }
175  Model *m, const ParticleIndexes &pca,
176  const ParticleIndexes &pcb) const override {
178  if (pca.empty() || pcb.empty()) return ParticleIndexPairs();
179  Index indexa = get_index(m, pca);
180  Index indexb = get_index(m, pcb);
181  return get_close_pairs_internal(m, indexa, indexb, false);
182  }
184  Model *m, const ParticleIndexes &pis) const override {
185  // for now assume we just read the particles
186  return IMP::get_particles(m, pis);
187  }
188 
190 };
191 
192 /** Create a new MetricClosePairsFinder, handling types. */
193 template <class LowerBound, class UpperBound>
195  UpperBound ub) {
197 }
198 
199 IMPMISC_END_NAMESPACE
200 
201 #endif /* IMPMISC_METRIC_CLOSE_PAIRS_FINDER_H */
virtual ModelObjectsTemp do_get_inputs(Model *m, const ParticleIndexes &pis) const override
Overload this method to specify the inputs.
A base class for algorithms to find spatial proximities.
Functions and adaptors for dealing with particle indexes.
virtual IntPairs get_close_pairs(const algebra::BoundingBox3Ds &) const override
IMP::Vector< ParticleIndexPair > ParticleIndexPairs
Definition: base_types.h:185
#define IMP_FAILURE(message)
A runtime failure for IMP.
Definition: check_macros.h:72
#define IMP_OBJECT_METHODS(Name)
Define the basic things needed by any Object.
Definition: object_macros.h:25
#define IMP_OBJECT_LOG
Set the log level to the object's log level.
Definition: log_macros.h:284
ParticlesTemp get_particles(Model *m, const ParticleIndexes &ps)
Get the particles from a list of indexes.
#define IMP_LOG_VERBOSE(expr)
Definition: log_macros.h:83
Class for storing model, its restraints, constraints, and particles.
Definition: Model.h:86
Ints get_index(const ParticlesTemp &particles, const Subset &subset, const Subsets &excluded)
virtual IntPairs get_close_pairs(const algebra::BoundingBox3Ds &, const algebra::BoundingBox3Ds &) const override
virtual ParticleIndexPairs get_close_pairs(Model *m, const ParticleIndexes &pc) const override
return all close pairs among pc in model m
core::ClosePairsFinder * create_metric_close_pairs_finder(LowerBound lb, UpperBound ub)
virtual ParticleIndexPairs get_close_pairs(Model *m, const ParticleIndexes &pca, const ParticleIndexes &pcb) const override
return all close pairs among pc in model m
A nullptr-initialized pointer to an IMP Object.
A base class for algorithms to detect proximities.
#define IMP_USAGE_CHECK(expr, message)
A runtime test for incorrect usage of a class or method.
Definition: check_macros.h:168
Random number generators used by IMP.
double get_distance(const Line3D &s, const Vector3D &p)
Get closest distance between a line and a point.
RandomNumberGenerator random_number_generator
A shared non-GPU random number generator.