Line data    Source code

       1             : /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
       2             :    Copyright (c) 2014-2020 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             : #include "ClusteringBase.h"
      23             : #include "core/ActionRegister.h"
      24             : 
      25             : //+PLUMEDOC MATRIXF DFSCLUSTERING
      26             : /*
      27             : Find the connected components of the matrix using the depth first search clustering algorithm.
      28             : 
      29             : This action is useful if you are looking at a phenomenon such as nucleation where the aim is to detect the sizes of the crystalline nuclei that have formed
      30             : in your simulation cell and is used in conjustion with tools from the adjmat module.  The adjmat modlule contains a number of different methods that can be
      31             : used to calculate adjacency matrices. An adjacency matrix is an $N \times N$ matrix
      32             : in which the $i$th, $j$th element tells you whether or not the $i$th and $j$th atoms/molecules from a set of $N$ atoms/molecules are adjacent or not.  The
      33             : simplest of these adjcency matrix methods is the one for calculating a [CONTACT_MATRIX](CONTACT_MATRIX.md).  All adjacency matrices provide a representation of a graph and can thus
      34             : can be analyzed using tools from graph theory. This particular action thus performs
      35             : [a depth first search clustering](https://en.wikipedia.org/wiki/Depth-first_search) to find the connected components of this graph.
      36             : 
      37             : The input below calculates a CONTACT_MATRIX for 100 atoms. In the graph that is created from this CONTACT_MATRIX atoms are connected if they are within
      38             : a distance of D_MAX of each other and are disconnected otherwise.  The [DFSCLUSTERING](DFSCLUSTERING.md) method is used to find the connected components in this graph.  This
      39             : method outputs a 100-dimensional vector.  The 1st element in this vector tells you which cluster the first atom is within, the second element tells you which
      40             : cluster the second atom is in and so on.  If an atom is in the largest cluster its corresponding element in the vector `dfs` will be one. We can thus print
      41             : the positions of the atoms in the largest cluster by using a [DUMPATOMS](DUMPATOMS.md) command like the one shown below:
      42             : 
      43             : ```plumed
      44             : cm: CONTACT_MATRIX GROUP=1-100 SWITCH={CUBIC D_0=0.45  D_MAX=0.55}
      45             : dfs: DFSCLUSTERING ARG=cm
      46             : DUMPATOMS FILE=cluster.xyz ATOMS=1-100 ARG=dfs LESS_THAN_OR_EQUAL=1.5 GREATER_THAN_OR_EQUAL=0.5
      47             : ```
      48             : 
      49             : */
      50             : //+ENDPLUMEDOC
      51             : 
      52             : namespace PLMD {
      53             : namespace clusters {
      54             : 
      55             : class DFSClustering : public ClusteringBase {
      56             : private:
      57             : /// The number of neighbors each atom has
      58             :   std::vector<unsigned> nneigh;
      59             : /// The adjacency list
      60             :   Matrix<unsigned> adj_list;
      61             : /// The color that tells us whether a node has been visited
      62             :   std::vector<unsigned> color;
      63             : /// The recursive function at the heart of this method
      64             :   int explore( const unsigned& index );
      65             : public:
      66             : /// Create manual
      67             :   static void registerKeywords( Keywords& keys );
      68             : /// Constructor
      69             :   explicit DFSClustering(const ActionOptions&);
      70             : /// Do the clustering
      71             :   void performClustering() override;
      72             : };
      73             : 
      74             : PLUMED_REGISTER_ACTION(DFSClustering,"DFSCLUSTERING")
      75             : 
      76          26 : void DFSClustering::registerKeywords( Keywords& keys ) {
      77          26 :   ClusteringBase::registerKeywords( keys );
      78          52 :   keys.addDeprecatedFlag("LOWMEM","");
      79          26 : }
      80             : 
      81          20 : DFSClustering::DFSClustering(const ActionOptions&ao):
      82             :   Action(ao),
      83          20 :   ClusteringBase(ao) {
      84          20 :   nneigh.resize( getNumberOfNodes() );
      85          20 :   color.resize(getNumberOfNodes());
      86             :   bool lowmem;
      87          20 :   parseFlag("LOWMEM",lowmem);
      88          20 :   if( lowmem ) {
      89           0 :     warning("LOWMEM flag is deprecated and is no longer required for this action");
      90             :   }
      91          20 : }
      92             : 
      93          47 : void DFSClustering::performClustering() {
      94             :   // Get the adjacency matrix
      95          47 :   retrieveAdjacencyLists( nneigh, adj_list );
      96             : 
      97             :   // Perform clustering
      98          47 :   number_of_cluster=-1;
      99          47 :   color.assign(color.size(),0);
     100       21407 :   for(unsigned i=0; i<getNumberOfNodes(); ++i) {
     101       21360 :     if( color[i]==0 ) {
     102       11384 :       number_of_cluster++;
     103       11384 :       color[i]=explore(i);
     104             :     }
     105             :   }
     106          47 : }
     107             : 
     108       21360 : int DFSClustering::explore( const unsigned& index ) {
     109             : 
     110       21360 :   color[index]=1;
     111      155248 :   for(unsigned i=0; i<nneigh[index]; ++i) {
     112      133888 :     unsigned j=adj_list(index,i);
     113      133888 :     if( color[j]==0 ) {
     114        9976 :       color[j]=explore(j);
     115             :     }
     116             :   }
     117             : 
     118             :   // Count the size of the cluster
     119       21360 :   cluster_sizes[number_of_cluster].first++;
     120       21360 :   which_cluster[index] = number_of_cluster;
     121       21360 :   return color[index];
     122             : }
     123             : 
     124             : }
     125             : }