src/gromacs/selection/nbsearch.h

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2009-2018, The GROMACS development team.
   5  * Copyright (c) 2019,2021, by the GROMACS development team, led by
   6  * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   7  * and including many others, as listed in the AUTHORS file in the
   8  * top-level source directory and at http://www.gromacs.org.
   9  *
  10  * GROMACS is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public License
  12  * as published by the Free Software Foundation; either version 2.1
  13  * of the License, or (at your option) any later version.
  14  *
  15  * GROMACS is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with GROMACS; if not, see
  22  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  23  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  24  *
  25  * If you want to redistribute modifications to GROMACS, please
  26  * consider that scientific software is very special. Version
  27  * control is crucial - bugs must be traceable. We will be happy to
  28  * consider code for inclusion in the official distribution, but
  29  * derived work must not be called official GROMACS. Details are found
  30  * in the README & COPYING files - if they are missing, get the
  31  * official version at http://www.gromacs.org.
  32  *
  33  * To help us fund GROMACS development, we humbly ask that you cite
  34  * the research papers on the package. Check out http://www.gromacs.org.
  35  */
  36 /*! \file
  37  * \brief API for neighborhood searching for analysis.
  38  *
  39  * The main part of the API is the class gmx::AnalysisNeighborhood.
  40  * See \ref page_analysisnbsearch for an overview.
  41  *
  42  * The classes within this file can be used independently of the other parts
  43  * of the selection module.
  44  *
  45  * \author Teemu Murtola <teemu.murtola@gmail.com>
  46  * \inpublicapi
  47  * \ingroup module_selection
  48  */
  49 #ifndef GMX_SELECTION_NBSEARCH_H
  50 #define GMX_SELECTION_NBSEARCH_H
  51
  52 #include <memory>
  53 #include <vector>
  54
  55 #include "gromacs/math/vec.h"
  56 #include "gromacs/math/vectypes.h"
  57 #include "gromacs/utility/arrayref.h"
  58 #include "gromacs/utility/basedefinitions.h"
  59 #include "gromacs/utility/gmxassert.h"
  60 #include "gromacs/utility/real.h"
  61
  62 struct t_pbc;
  63
  64 namespace gmx
  65 {
  66 template<typename>
  67 class ListOfLists;
  68
  69 namespace internal
  70 {
  71 class AnalysisNeighborhoodSearchImpl;
  72 class AnalysisNeighborhoodPairSearchImpl;
  73 }; // namespace internal
  74
  75 class AnalysisNeighborhoodSearch;
  76 class AnalysisNeighborhoodPairSearch;
  77
  78 /*! \brief
  79  * Input positions for neighborhood searching.
  80  *
  81  * This class supports uniformly specifying sets of positions for various
  82  * methods in the analysis neighborhood searching classes
  83  * (AnalysisNeighborhood and AnalysisNeighborhoodSearch).
  84  *
  85  * Note that copies are not made: only a reference to the positions passed to
  86  * the constructors are kept.  The caller is responsible to ensure that those
  87  * positions remain in scope as long as the neighborhood search object requires
  88  * access to them.
  89  *
  90  * Also note that in addition to constructors here, Selection and
  91  * SelectionPosition provide conversions operators to this type.  It is done
  92  * this way to not introduce a cyclic dependency between the selection code and
  93  * the neighborhood search code, which in turn allows splitting this search
  94  * code into a separate lower-level module if desired at some point.
  95  *
  96  * Methods in this class do not throw.
  97  *
  98  * \inpublicapi
  99  * \ingroup module_selection
 100  */
 101 class AnalysisNeighborhoodPositions
 102 {
 103 public:
 104     /*! \brief
 105      * Initializes positions from a single position vector.
 106      *
 107      * For positions initialized this way, AnalysisNeighborhoodPair always
 108      * returns zero in the corresponding index.
 109      *
 110      * This constructor is not explicit to allow directly passing an rvec
 111      * to methods that accept positions.
 112      */
 113     AnalysisNeighborhoodPositions(const rvec& x) :
 114         count_(1),
 115         index_(-1),
 116         x_(&x),
 117         exclusionIds_(nullptr),
 118         indices_(nullptr)
 119     {
 120     }
 121     /*! \brief
 122      * Initializes positions from an array of position vectors.
 123      */
 124     AnalysisNeighborhoodPositions(const rvec x[], int count) :
 125         count_(count),
 126         index_(-1),
 127         x_(x),
 128         exclusionIds_(nullptr),
 129         indices_(nullptr)
 130     {
 131     }
 132     /*! \brief
 133      * Initializes positions from a vector of position vectors.
 134      */
 135     AnalysisNeighborhoodPositions(const std::vector<RVec>& x) :
 136         count_(ssize(x)),
 137         index_(-1),
 138         x_(as_rvec_array(x.data())),
 139         exclusionIds_(nullptr),
 140         indices_(nullptr)
 141     {
 142     }
 143
 144     /*! \brief
 145      * Sets indices to use for mapping exclusions to these positions.
 146      *
 147      * The exclusion IDs can always be set, but they are ignored unless
 148      * actual exclusions have been set with
 149      * AnalysisNeighborhood::setTopologyExclusions().
 150      */
 151     AnalysisNeighborhoodPositions& exclusionIds(ArrayRef<const int> ids)
 152     {
 153         GMX_ASSERT(ssize(ids) == count_, "Exclusion id array should match the number of positions");
 154         exclusionIds_ = ids.data();
 155         return *this;
 156     }
 157     /*! \brief
 158      * Sets indices that select a subset of all positions from the array.
 159      *
 160      * If called, selected positions from the array of positions passed to
 161      * the constructor is used instead of the whole array.
 162      * All returned indices from AnalysisNeighborhoodPair objects are
 163      * indices to the \p indices array passed here.
 164      */
 165     AnalysisNeighborhoodPositions& indexed(ArrayRef<const int> indices)
 166     {
 167         count_   = ssize(indices);
 168         indices_ = indices.data();
 169         return *this;
 170     }
 171
 172     /*! \brief
 173      * Selects a single position to use from an array.
 174      *
 175      * If called, a single position from the array of positions passed to
 176      * the constructor is used instead of the whole array.
 177      * In contrast to the AnalysisNeighborhoodPositions(const rvec &)
 178      * constructor, AnalysisNeighborhoodPair objects return \p index
 179      * instead of zero.
 180      *
 181      * If used together with indexed(), \p index references the index array
 182      * passed to indexed() instead of the position array.
 183      */
 184     AnalysisNeighborhoodPositions& selectSingleFromArray(int index)
 185     {
 186         GMX_ASSERT(index >= 0 && index < count_, "Invalid position index");
 187         index_ = index;
 188         return *this;
 189     }
 190
 191 private:
 192     int         count_;
 193     int         index_;
 194     const rvec* x_;
 195     const int*  exclusionIds_;
 196     const int*  indices_;
 197
 198     //! To access the positions for initialization.
 199     friend class internal::AnalysisNeighborhoodSearchImpl;
 200     //! To access the positions for initialization.
 201     friend class internal::AnalysisNeighborhoodPairSearchImpl;
 202 };
 203
 204 /*! \brief
 205  * Neighborhood searching for analysis tools.
 206  *
 207  * See \ref page_analysisnbsearch for an overview.
 208  *
 209  * To use the search, create an object of this type, call setCutoff() to
 210  * initialize it, and then repeatedly call initSearch() to start a search with
 211  * different sets of reference positions.  For each set of reference positions,
 212  * use methods in the returned AnalysisNeighborhoodSearch to find the reference
 213  * positions that are within the given cutoff from a provided position.
 214  *
 215  * initSearch() is thread-safe and can be called from multiple threads.  Each
 216  * call returns a different instance of the search object that can be used
 217  * independently of the others.  The returned AnalysisNeighborhoodSearch
 218  * objects are also thread-safe, and can be used concurrently from multiple
 219  * threads.  It is also possible to create multiple concurrent searches within
 220  * a single thread.
 221  *
 222  * \todo
 223  * Generalize the exclusion machinery to make it easier to use for other cases
 224  * than atom-atom exclusions from the topology.
 225  *
 226  * \inpublicapi
 227  * \ingroup module_selection
 228  */
 229 class AnalysisNeighborhood
 230 {
 231 public:
 232     //! Searching algorithm to use.
 233     enum SearchMode
 234     {
 235         //! Select algorithm based on heuristic efficiency considerations.
 236         eSearchMode_Automatic,
 237         //! Use a simple loop over all pairs.
 238         eSearchMode_Simple,
 239         //! Use grid-based searching whenever possible.
 240         eSearchMode_Grid
 241     };
 242
 243     //! Creates an uninitialized neighborhood search.
 244     AnalysisNeighborhood();
 245     ~AnalysisNeighborhood();
 246
 247     /*! \brief
 248      * Sets cutoff distance for the neighborhood searching.
 249      *
 250      * \param[in]  cutoff Cutoff distance for the search
 251      *   (<=0 stands for no cutoff).
 252      *
 253      * Currently, can only be called before the first call to initSearch().
 254      * If this method is not called, no cutoff is used in the searches.
 255      *
 256      * Does not throw.
 257      */
 258     void setCutoff(real cutoff);
 259     /*! \brief
 260      * Sets the search to only happen in the XY plane.
 261      *
 262      * Z component of the coordinates is not used in the searching,
 263      * and returned distances are computed in the XY plane.
 264      * Only boxes with the third box vector parallel to the Z axis are
 265      * currently implemented.
 266      *
 267      * Does not throw.
 268      */
 269     void setXYMode(bool bXY);
 270     /*! \brief
 271      * Sets atom exclusions from a topology.
 272      *
 273      * The \p excls structure specifies the exclusions from test positions
 274      * to reference positions, i.e., a block starting at `excls->index[i]`
 275      * specifies the exclusions for test position `i`, and the indices in
 276      * `excls->a` are indices of the reference positions.  If `excls->nr`
 277      * is smaller than a test position id, then such test positions do not
 278      * have any exclusions.
 279      * It is assumed that the indices within a block of indices in
 280      * `excls->a` is ascending.
 281      *
 282      * Does not throw.
 283      *
 284      * \see AnalysisNeighborhoodPositions::exclusionIds()
 285      */
 286     void setTopologyExclusions(const ListOfLists<int>* excls);
 287     /*! \brief
 288      * Sets the algorithm to use for searching.
 289      *
 290      * \param[in] mode  Search mode to use.
 291      *
 292      * Note that if \p mode is \ref eSearchMode_Grid, it is still only a
 293      * suggestion: grid-based searching may not be possible with the
 294      * provided input, in which case a simple search is still used.
 295      * This is mainly useful for testing purposes to force a mode.
 296      *
 297      * Does not throw.
 298      */
 299     void setMode(SearchMode mode);
 300     //! Returns the currently active search mode.
 301     SearchMode mode() const;
 302
 303     /*! \brief
 304      * Initializes neighborhood search for a set of positions.
 305      *
 306      * \param[in] pbc        PBC information for the frame.
 307      * \param[in] positions  Set of reference positions to use.
 308      * \returns   Search object that can be used to find positions from
 309      *      \p x within the given cutoff.
 310      * \throws    std::bad_alloc if out of memory.
 311      *
 312      * Currently, the input positions cannot use
 313      * AnalysisNeighborhoodPositions::selectSingleFromArray().
 314      */
 315     AnalysisNeighborhoodSearch initSearch(const t_pbc* pbc, const AnalysisNeighborhoodPositions& positions);
 316
 317 private:
 318     class Impl;
 319
 320     std::unique_ptr<Impl> impl_;
 321 };
 322
 323 /*! \brief
 324  * Value type to represent a pair of positions found in neighborhood searching.
 325  *
 326  * Methods in this class do not throw.
 327  *
 328  * \inpublicapi
 329  * \ingroup module_selection
 330  */
 331 class AnalysisNeighborhoodPair
 332 {
 333 public:
 334     //! Initializes an invalid pair.
 335     AnalysisNeighborhoodPair() : refIndex_(-1), testIndex_(0), distance2_(0.0), dx_() {}
 336     //! Initializes a pair object with the given data.
 337     AnalysisNeighborhoodPair(int refIndex, int testIndex, real distance2, const rvec dx) :
 338         refIndex_(refIndex),
 339         testIndex_(testIndex),
 340         distance2_(distance2),
 341         dx_()
 342     {
 343         copy_rvec(dx, dx_);
 344     }
 345
 346     /*! \brief
 347      * Whether this pair is valid.
 348      *
 349      * If isValid() returns false, other methods should not be called.
 350      */
 351     bool isValid() const { return refIndex_ >= 0; }
 352
 353     /*! \brief
 354      * Returns the index of the reference position in the pair.
 355      *
 356      * This index is always the index into the position array provided to
 357      * AnalysisNeighborhood::initSearch().
 358      */
 359     int refIndex() const
 360     {
 361         GMX_ASSERT(isValid(), "Accessing invalid object");
 362         return refIndex_;
 363     }
 364     /*! \brief
 365      * Returns the index of the test position in the pair.
 366      *
 367      * The contents of this index depends on the context (method call) that
 368      * produces the pair.
 369      * If there was no array in the call, this index is zero.
 370      */
 371     int testIndex() const
 372     {
 373         GMX_ASSERT(isValid(), "Accessing invalid object");
 374         return testIndex_;
 375     }
 376     /*! \brief
 377      * Returns the squared distance between the pair of positions.
 378      */
 379     real distance2() const
 380     {
 381         GMX_ASSERT(isValid(), "Accessing invalid object");
 382         return distance2_;
 383     }
 384     /*! \brief
 385      * Returns the shortest vector between the pair of positions.
 386      *
 387      * The vector is from the test position to the reference position.
 388      */
 389     const rvec& dx() const
 390     {
 391         GMX_ASSERT(isValid(), "Accessing invalid object");
 392         return dx_;
 393     }
 394
 395 private:
 396     int  refIndex_;
 397     int  testIndex_;
 398     real distance2_;
 399     rvec dx_;
 400 };
 401
 402 /*! \brief
 403  * Initialized neighborhood search with a fixed set of reference positions.
 404  *
 405  * An instance of this class is obtained through
 406  * AnalysisNeighborhood::initSearch(), and can be used to do multiple searches
 407  * against the provided set of reference positions.
 408  * It is possible to create concurrent pair searches (including from different
 409  * threads), as well as call other methods in this class while a pair search is
 410  * in progress.
 411  *
 412  * This class works like a pointer: copies of it point to the same search.
 413  * In general, avoid creating copies, and only use the copy/assignment support
 414  * for moving the variable around.  With C++11, this class would best be
 415  * movable.
 416  *
 417  * Methods in this class do not throw unless otherwise indicated.
 418  *
 419  * \todo
 420  * Make it such that reset() is not necessary to call in code that repeatedly
 421  * assigns the result of AnalysisNeighborhood::initSearch() to the same
 422  * variable (see sm_distance.cpp).
 423  *
 424  * \todo
 425  * Consider removing minimumDistance(), as nearestPoint() already returns the
 426  * distance.
 427  *
 428  * \inpublicapi
 429  * \ingroup module_selection
 430  */
 431 class AnalysisNeighborhoodSearch
 432 {
 433 public:
 434     /*! \brief
 435      * Internal short-hand type for a pointer to the implementation class.
 436      *
 437      * shared_ptr is used here to automatically keep a reference count to
 438      * track whether an implementation class is still used outside the
 439      * AnalysisNeighborhood object.  Ownership currently always stays with
 440      * AnalysisNeighborhood; it always keeps one instance of the pointer.
 441      */
 442     typedef std::shared_ptr<internal::AnalysisNeighborhoodSearchImpl> ImplPointer;
 443
 444     /*! \brief
 445      * Initializes an invalid search.
 446      *
 447      * Such an object cannot be used for searching.  It needs to be
 448      * assigned a value from AnalysisNeighborhood::initSearch() before it
 449      * can be used.  Provided to allow declaring a variable to hold the
 450      * search before calling AnalysisNeighborhood::initSearch().
 451      */
 452     AnalysisNeighborhoodSearch();
 453     /*! \brief
 454      * Internally initialize the search.
 455      *
 456      * Used to implement AnalysisNeighborhood::initSearch().
 457      * Cannot be called from user code.
 458      */
 459     explicit AnalysisNeighborhoodSearch(const ImplPointer& impl);
 460
 461     /*! \brief
 462      * Clears this search.
 463      *
 464      * Equivalent to \c "*this = AnalysisNeighborhoodSearch();".
 465      * Currently, this is necessary to avoid unnecessary memory allocation
 466      * if the previous search variable is still in scope when you want to
 467      * call AnalysisNeighborhood::initSearch() again.
 468      */
 469     void reset();
 470
 471     /*! \brief
 472      * Returns the searching algorithm that this search is using.
 473      *
 474      * The return value is never AnalysisNeighborhood::eSearchMode_Automatic.
 475      */
 476     AnalysisNeighborhood::SearchMode mode() const;
 477
 478     /*! \brief
 479      * Checks whether a point is within a neighborhood.
 480      *
 481      * \param[in] positions  Set of test positions to use.
 482      * \returns   true if any of the test positions is within the cutoff of
 483      *     any reference position.
 484      */
 485     bool isWithin(const AnalysisNeighborhoodPositions& positions) const;
 486     /*! \brief
 487      * Calculates the minimum distance from the reference points.
 488      *
 489      * \param[in] positions  Set of test positions to use.
 490      * \returns   The distance to the nearest reference position, or the
 491      *     cutoff value if there are no reference positions within the
 492      *     cutoff.
 493      */
 494     real minimumDistance(const AnalysisNeighborhoodPositions& positions) const;
 495     /*! \brief
 496      * Finds the closest reference point.
 497      *
 498      * \param[in] positions  Set of test positions to use.
 499      * \returns   The reference index identifies the reference position
 500      *     that is closest to the test positions.
 501      *     The test index identifies the test position that is closest to
 502      *     the provided test position.  The returned pair is invalid if
 503      *     no reference position is within the cutoff.
 504      */
 505     AnalysisNeighborhoodPair nearestPoint(const AnalysisNeighborhoodPositions& positions) const;
 506
 507     /*! \brief
 508      * Starts a search to find all reference position pairs within a cutoff.
 509      *
 510      * \returns   Initialized search object to loop through all reference
 511      *     position pairs within the configured cutoff.
 512      * \throws    std::bad_alloc if out of memory.
 513      *
 514      * This works as if the reference positions were passed to
 515      * startPairSearch(), except that it only returns each pair once,
 516      * instead of returning both i-j and j-i pairs, as startPairSearch()
 517      * does.  i-i pairs are not returned.  Note that the order of ref/test
 518      * indices in the returned pairs is not predictable.  That is, one of
 519      * i-j or j-i is always returned, but there is no control which one.
 520      */
 521     AnalysisNeighborhoodPairSearch startSelfPairSearch() const;
 522
 523     /*! \brief
 524      * Starts a search to find reference positions within a cutoff.
 525      *
 526      * \param[in] positions  Set of test positions to use.
 527      * \returns   Initialized search object to loop through all reference
 528      *     positions within the configured cutoff.
 529      * \throws    std::bad_alloc if out of memory.
 530      *
 531      * If you want to pass the same positions here as you used for the
 532      * reference positions, consider using startSelfPairSearch().
 533      * It can be up to 50% faster.
 534      */
 535     AnalysisNeighborhoodPairSearch startPairSearch(const AnalysisNeighborhoodPositions& positions) const;
 536
 537 private:
 538     typedef internal::AnalysisNeighborhoodSearchImpl Impl;
 539
 540     ImplPointer impl_;
 541 };
 542
 543 /*! \brief
 544  * Initialized neighborhood pair search with a fixed set of positions.
 545  *
 546  * This class is used to loop through pairs of neighbors within the cutoff
 547  * provided to AnalysisNeighborhood.  The following code demonstrates its use:
 548  * \code
 549    gmx::AnalysisNeighborhood       nb;
 550    nb.setCutoff(cutoff);
 551    gmx::AnalysisNeighborhoodPositions refPos(xref, nref);
 552    gmx::AnalysisNeighborhoodSearch search = nb.initSearch(pbc, refPos);
 553    gmx::AnalysisNeighborhoodPairSearch pairSearch = search.startPairSearch(selection);
 554    gmx::AnalysisNeighborhoodPair pair;
 555    while (pairSearch.findNextPair(&pair))
 556    {
 557        // <do something for each found pair the information in pair>
 558    }
 559  * \endcode
 560  *
 561  * It is not possible to use a single search object from multiple threads
 562  * concurrently.
 563  *
 564  * This class works like a pointer: copies of it point to the same search.
 565  * In general, avoid creating copies, and only use the copy/assignment support
 566  * for moving the variable around.  With C++11, this class would best be
 567  * movable.
 568  *
 569  * Methods in this class do not throw.
 570  *
 571  * \inpublicapi
 572  * \ingroup module_selection
 573  */
 574 class AnalysisNeighborhoodPairSearch
 575 {
 576 public:
 577     /*! \brief
 578      * Internal short-hand type for a pointer to the implementation class.
 579      *
 580      * See AnalysisNeighborhoodSearch::ImplPointer for rationale of using
 581      * shared_ptr and ownership semantics.
 582      */
 583     typedef std::shared_ptr<internal::AnalysisNeighborhoodPairSearchImpl> ImplPointer;
 584
 585     /*! \brief
 586      * Internally initialize the search.
 587      *
 588      * Used to implement AnalysisNeighborhoodSearch::startPairSearch().
 589      * Cannot be called from user code.
 590      */
 591     explicit AnalysisNeighborhoodPairSearch(const ImplPointer& impl);
 592
 593     /*! \brief
 594      * Finds the next pair within the cutoff.
 595      *
 596      * \param[out] pair  Information about the found pair.
 597      * \returns    false if there were no more pairs.
 598      *
 599      * If the method returns false, \p pair will be invalid.
 600      *
 601      * \see AnalysisNeighborhoodPair
 602      * \see AnalysisNeighborhoodSearch::startPairSearch()
 603      */
 604     bool findNextPair(AnalysisNeighborhoodPair* pair);
 605     /*! \brief
 606      * Skip remaining pairs for a test position in the search.
 607      *
 608      * When called after findNextPair(), makes subsequent calls to
 609      * findNextPair() skip any pairs that have the same test position as
 610      * that previously returned.
 611      * This is useful if the caller wants to search whether any reference
 612      * position within the cutoff satisfies some condition.  This method
 613      * can be used to skip remaining pairs after the first such position
 614      * has been found if the remaining pairs would not have an effect on
 615      * the outcome.
 616      */
 617     void skipRemainingPairsForTestPosition();
 618
 619 private:
 620     ImplPointer impl_;
 621 };
 622
 623 } // namespace gmx
 624
 625 #endif