Line data    Source code

       1             : /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
       2             :    Copyright (c) 2021-2023 The plumed team
       3             :    (see the PEOPLE file at the root of the distribution for a list of names)
       4             : 
       5             :    See http://www.plumed.org for more information.
       6             : 
       7             :    This file is part of plumed, version 2.
       8             : 
       9             :    plumed is free software: you can redistribute it and/or modify
      10             :    it under the terms of the GNU Lesser General Public License as published by
      11             :    the Free Software Foundation, either version 3 of the License, or
      12             :    (at your option) any later version.
      13             : 
      14             :    plumed is distributed in the hope that it will be useful,
      15             :    but WITHOUT ANY WARRANTY; without even the implied warranty of
      16             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      17             :    GNU Lesser General Public License for more details.
      18             : 
      19             :    You should have received a copy of the GNU Lesser General Public License
      20             :    along with plumed.  If not, see <http://www.gnu.org/licenses/>.
      21             : +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
      22             : 
      23             : #include "Tree.h"
      24             : #include "Tools.h"
      25             : #include "Vector.h"
      26             : #include "AtomNumber.h"
      27             : #include "core/GenericMolInfo.h"
      28             : #include <vector>
      29             : #include <limits>
      30             : 
      31             : namespace PLMD {
      32             : 
      33           3 : Tree::Tree(GenericMolInfo* moldat) {
      34             : // initialize class
      35           3 :   moldat_ = moldat;
      36             : // check if molinfo present
      37           3 :   if(!moldat_) {
      38           0 :     plumed_merror("MOLINFO DATA not found");
      39             :   }
      40             : // check if reference structure is whole
      41           3 :   if(!moldat_->isWhole()) {
      42           0 :     plumed_merror("Check that reference structure in PDB file is not broken by pbc and set WHOLE in MOLINFO line");
      43             :   }
      44           3 : }
      45             : 
      46           2 : void Tree::buildTree(const std::vector<AtomNumber> & atoms) {
      47             :   // Implementation inspired from:
      48             :   // https://mayanknatani.wordpress.com/2013/05/31/euclidean-minimummaximum-spanning-tree-emst/
      49             :   //
      50             :   // clear root_ vector
      51           2 :   root_.clear();
      52           2 :   tree_.clear();
      53           2 :   root_indexes_.clear();
      54           2 :   tree_indexes_.clear();
      55             : 
      56             :   std::vector<Vector> positions;
      57             : 
      58             :   // remove atoms not in PDB file
      59             :   std::vector<unsigned> addtotree, addtoroot;
      60             :   std::vector<unsigned> newatoms;
      61           2 :   newatoms.reserve(atoms.size());
      62           2 :   positions.reserve(atoms.size());
      63             : 
      64           2 :   tree_.reserve(atoms.size());
      65           2 :   root_.reserve(atoms.size());
      66           2 :   tree_indexes_.reserve(atoms.size());
      67           2 :   root_indexes_.reserve(atoms.size());
      68           2 :   if(!moldat_->checkForAtom(atoms[0])) {
      69           0 :     plumed_merror("The first atom in the list should be present in the PDB file");
      70             :   }
      71             :   // store first atom
      72           2 :   newatoms.push_back(0);
      73           2 :   positions.push_back(moldat_->getPosition(atoms[0]));
      74         245 :   for(unsigned i=1; i<atoms.size(); ++i) {
      75         243 :     if(!moldat_->checkForAtom(atoms[i])) {
      76             :       // store this atom for later
      77          61 :       addtotree.push_back(i);
      78             :       // along with its root (the previous atom)
      79          61 :       addtoroot.push_back(i-1);
      80             :     } else {
      81         182 :       newatoms.push_back(i);
      82         364 :       positions.push_back(moldat_->getPosition(atoms[i]));
      83             :     }
      84             :   }
      85             : 
      86             :   // start EMST
      87           2 :   std::vector<bool> intree(newatoms.size(), false);
      88           2 :   std::vector<double> mindist(newatoms.size(), std::numeric_limits<double>::max());
      89             :   // initialize tree with first atom
      90           2 :   mindist[0] = 0.0;
      91             :   // loops
      92         186 :   for(unsigned i=0; i<newatoms.size(); ++i) {
      93             :     int selected_vertex = -1;
      94       19034 :     for(unsigned j=0; j<newatoms.size(); ++j) {
      95       18850 :       if( !intree[j] && (selected_vertex==-1 || mindist[j] < mindist[selected_vertex]) ) {
      96        1078 :         selected_vertex = j;
      97             :       }
      98             :     }
      99             :     // add to tree
     100         184 :     plumed_assert(selected_vertex>=0);
     101         184 :     tree_indexes_.push_back(newatoms[selected_vertex]);
     102         184 :     tree_.push_back(atoms[newatoms[selected_vertex]]);
     103             :     intree[selected_vertex] = true;
     104             :     // update distances
     105             :     double minroot = std::numeric_limits<double>::max();
     106             :     int iroot = -1;
     107       19034 :     for(unsigned j=0; j<newatoms.size(); ++j) {
     108       18850 :       double dist = delta(positions[selected_vertex], positions[j]).modulo2();
     109       18850 :       if(dist < mindist[j]) {
     110        4312 :         mindist[j] = dist;
     111             :       }
     112       22401 :       if(dist < minroot && intree[j] && dist>0.0) {
     113             :         minroot = dist;
     114        2822 :         iroot = j;
     115             :       }
     116             :     }
     117             :     // add to root vector
     118         184 :     if(iroot>=0) {
     119         182 :       root_.push_back(atoms[newatoms[iroot]]);
     120         182 :       root_indexes_.push_back(newatoms[iroot]);
     121             :     }
     122             :   }
     123             : 
     124             :   // now re-add atoms not present in the PDB
     125          63 :   for(unsigned i=0; i<addtotree.size(); ++i) {
     126          61 :     tree_.push_back(atoms[addtotree[i]]);
     127          61 :     tree_indexes_.push_back(addtotree[i]);
     128          61 :     root_.push_back(atoms[addtoroot[i]]);
     129          61 :     root_indexes_.push_back(addtoroot[i]);
     130             :   }
     131           2 : }
     132             : 
     133           2 : const std::vector<AtomNumber> & Tree::getTree(const std::vector<AtomNumber> & atoms) {
     134           2 :   buildTree(atoms);
     135           2 :   return tree_;
     136             : }
     137             : 
     138           0 : const std::vector<AtomNumber> & Tree::getTree() const noexcept {
     139           0 :   return tree_;
     140             : }
     141             : 
     142           2 : const std::vector<AtomNumber> & Tree::getRoot() const noexcept {
     143           2 :   return root_;
     144             : }
     145             : 
     146           2 : const std::vector<unsigned> & Tree::getTreeIndexes() const noexcept {
     147           2 :   return tree_indexes_;
     148             : }
     149             : 
     150           2 : const std::vector<unsigned> & Tree::getRootIndexes() const noexcept {
     151           2 :   return root_indexes_;
     152             : }
     153             : 
     154             : 
     155             : }