IMP logo
IMP Reference Guide  2.14.0
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-2020 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/particle_index.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 include symmetry).
25 
26  The LowerBound and UpperBound templates should be functors that bound 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. The signature should be `double operator()(Model *m, const
31  ParticleIndexPair &pip) const`
32 
33  The algorithm works by building an index using `sqrt(n)` of the `n` input
34  particles, assigning each particle to a bucket 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](https://pubs.acs.org/doi/abs/10.1021/ci034150f)
40  */
41 template <class LowerBound, class UpperBound>
43  LowerBound lb_;
44  UpperBound ub_;
45 
46  IMP_NAMED_TUPLE_2(Data, Datas, ParticleIndexes, indexes, double,
47  width, );
48 
49  typedef boost::unordered_map<ParticleIndex, Data> Index;
50  Index get_index(Model *m, 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  ParticleIndexes indexes(inputs.begin(),
56  inputs.begin() + index_size);
57  for (unsigned int i = 0; i < index_size; ++i) {
58  ret[inputs[i]] = Data(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  ParticleIndex min_index;
64  for (unsigned int j = 0; j < indexes.size(); ++j) {
66  lb_(m, ParticleIndexPair(inputs[i], indexes[j])) <=
67  ub_(m, ParticleIndexPair(inputs[i], indexes[j])),
68  "The bounds are not ordered.");
69  double cur_dist =
70  ub_(m, 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  ParticleIndexPairs get_close_pairs_internal(
86  Model *m, const 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, ParticleIndexPair(p[i], p[j])) <=
91  ub_(m, ParticleIndexPair(p[i], p[j])),
92  "The bounds are not ordered.");
93  if (lb_(m, ParticleIndexPair(p[i], p[j])) < get_distance()) {
94  ret.push_back(ParticleIndexPair(p[i], p[j]));
95  }
96  }
97  }
98  return ret;
99  }
100  ParticleIndexPairs get_close_pairs_internal(
101  Model *m, const ParticleIndexes &pa,
102  const ParticleIndexes &pb) const {
103  ParticleIndexPairs ret;
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, ParticleIndexPair(pa[i], pb[j])) <=
107  ub_(m, ParticleIndexPair(pa[i], pb[j])),
108  "The bounds are not ordered.");
109  if (lb_(m, ParticleIndexPair(pa[i], pb[j])) < get_distance()) {
110  ret.push_back(ParticleIndexPair(pa[i], pb[j]));
111  }
112  }
113  }
114  return ret;
115  }
116  ParticleIndexPairs get_close_pairs_internal(Model *m,
117  const Index &ia,
118  const Index &ib,
119  bool is_same) const {
120  ParticleIndexPairs ret;
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, ParticleIndexPair(ita->first, itb->first)) <=
134  ub_(m, ParticleIndexPair(ita->first, itb->first)),
135  "The bounds are not ordered.");
136  if (lb_(m, 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  /** Not supported.*/
152  IMP_OVERRIDE {
153  IMP_FAILURE("Bounding boxes are not supported.");
154  }
155  /** Not supported.*/
157  const algebra::BoundingBox3Ds &) const
158  IMP_OVERRIDE {
159  IMP_FAILURE("Bounding boxes are not supported.");
160  }
161 
163  Model *m, const ParticleIndexes &pc) const IMP_OVERRIDE {
165  if (pc.empty()) return ParticleIndexPairs();
166  Index index = get_index(m, pc);
167  return get_close_pairs_internal(m, index, index, true);
168  }
170  Model *m, const ParticleIndexes &pca,
171  const ParticleIndexes &pcb) const IMP_OVERRIDE {
173  if (pca.empty() || pcb.empty()) return ParticleIndexPairs();
174  Index indexa = get_index(m, pca);
175  Index indexb = get_index(m, pcb);
176  return get_close_pairs_internal(m, indexa, indexb, false);
177  }
179  Model *m, const ParticleIndexes &pis) const IMP_OVERRIDE {
180  // for now assume we just read the particles
181  return IMP::get_particles(m, pis);
182  }
183 
185 };
186 
187 /** Create a new MetricClosePairsFinder, handling types. */
188 template <class LowerBound, class UpperBound>
190  UpperBound ub) {
192 }
193 
194 IMPMISC_END_NAMESPACE
195 
196 #endif /* IMPMISC_METRIC_CLOSE_PAIRS_FINDER_H */
virtual IntPairs get_close_pairs(const algebra::BoundingBox3Ds &, const algebra::BoundingBox3Ds &) const
A base class for algorithms to find spatial proximities.
Various general useful functions for IMP.
IMP::Vector< ParticleIndexPair > ParticleIndexPairs
Definition: base_types.h:165
#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
virtual IntPairs get_close_pairs(const algebra::BoundingBox3Ds &) const
ParticlesTemp get_particles(Model *m, const ParticleIndexes &ps)
#define IMP_LOG_VERBOSE(expr)
Definition: log_macros.h:83
virtual ParticleIndexPairs get_close_pairs(Model *m, const ParticleIndexes &pc) const
return all close pairs among pc in model m
Class for storing model, its restraints, constraints, and particles.
Definition: Model.h:72
Ints get_index(const ParticlesTemp &particles, const Subset &subset, const Subsets &excluded)
virtual ParticleIndexPairs get_close_pairs(Model *m, const ParticleIndexes &pca, const ParticleIndexes &pcb) const
return all close pairs among pc in model m
core::ClosePairsFinder * create_metric_close_pairs_finder(LowerBound lb, UpperBound ub)
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
virtual ModelObjectsTemp do_get_inputs(Model *m, const ParticleIndexes &pis) const
Overload this method to specify the inputs.
double get_distance(const Line3D &s, const Vector3D &p)
Get closest distance between a line and a point.
#define IMP_OVERRIDE
Cause a compile error if this method does not override a parent method.