Chemical Data Processing Library C++ API - Version 1.1.1
SmallestSetOfSmallestRings.hpp
Go to the documentation of this file.
1 /*
2  * SmallestSetOfSmallestRings.hpp
3  *
4  * Implementation of Balducci's SSSR-finder algorithm
5  * (R. Balducci, R. S. Pearlman, J. Chem. Inf. Comput. Sci. 1994, 34, 822-831)
6  *
7  * This file is part of the Chemical Data Processing Toolkit
8  *
9  * Copyright (C) 2003 Thomas Seidel <thomas.seidel@univie.ac.at>
10  *
11  * This library is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU Lesser General Public
13  * License as published by the Free Software Foundation; either
14  * version 2 of the License, or (at your option) any later version.
15  *
16  * This library is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  * Lesser General Public License for more details.
20  *
21  * You should have received a copy of the GNU Lesser General Public License
22  * along with this library; see the file COPYING. If not, write to
23  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24  * Boston, MA 02111-1307, USA.
25  */
26 
32 #ifndef CDPL_CHEM_SMALLESTSETOFSMALLESTRINGS_HPP
33 #define CDPL_CHEM_SMALLESTSETOFSMALLESTRINGS_HPP
34 
35 #include <vector>
36 #include <cstddef>
37 #include <set>
38 #include <memory>
39 
40 #include "CDPL/Chem/APIPrefix.hpp"
43 #include "CDPL/Util/BitSet.hpp"
44 #include "CDPL/Util/ObjectPool.hpp"
45 
46 
47 namespace CDPL
48 {
49 
50  namespace Chem
51  {
52 
58  {
59 
60  public:
64  typedef std::shared_ptr<SmallestSetOfSmallestRings> SharedPointer;
65 
70 
76 
81  void perceive(const MolecularGraph& molgraph);
82 
83  private:
84  class PathMessage;
85 
88  typedef MessageCache::SharedObjectPointer MessagePtr;
89  typedef std::vector<MessagePtr> MessageList;
90 
92 
94 
95  void visitComponentAtom(const Atom& atom);
96 
97  void init();
98  void findSSSR();
99  void createRingFragments();
100 
101  Fragment::SharedPointer createRing(const MolecularGraph& molgraph, const MessagePtr& msg);
102 
103  bool sssrComplete() const;
104 
105  MessagePtr allocMessage();
106  MessagePtr allocMessage(std::size_t, std::size_t, std::size_t, std::size_t);
107 
108  bool processCollision(const MessagePtr&, const MessagePtr&, std::size_t, bool);
109  void processRing(const MessagePtr&);
110  void processEvenRings();
111 
112  const char* getClassName() const
113  {
114  return "SmallestSetOfSmallestRings";
115  }
116 
117  class TNode
118  {
119 
120  public:
121  TNode(std::size_t idx):
122  index(idx) {}
123 
124  bool send(Controller*);
125  bool receive(Controller*);
126 
127  std::size_t getIndex() const;
128  std::size_t getNumNeighbors() const;
129 
130  void initMessages(Controller* ctrl, std::size_t max_num_atoms, std::size_t max_num_bonds);
131 
132  static void connect(TNode*, TNode*, std::size_t);
133 
134  private:
135  typedef std::vector<TNode*> NodeList;
136  typedef std::vector<std::size_t> BondIndexList;
137 
138  NodeList nbrNodes;
139  BondIndexList bondIndices;
140  MessageList receiveBuffer;
141  MessageList sendBuffer;
142  std::size_t index;
143  };
144 
145  class PathMessage
146  {
147 
148  public:
149  struct LessCmpFunc
150  {
151 
152  bool operator()(const MessagePtr&, const MessagePtr&) const;
153  };
154 
155  void init(std::size_t, std::size_t, std::size_t, std::size_t);
156 
157  void copy(const MessagePtr&);
158  bool join(const MessagePtr&, const MessagePtr&);
159 
160  void addAtom(std::size_t);
161  void addBond(std::size_t);
162 
163  bool containsAtom(std::size_t const);
164  bool containsBond(std::size_t const);
165 
166  std::size_t getFirstAtomIndex() const;
167  std::size_t getFirstBondIndex() const;
168 
169  std::size_t getMaxBondIndex() const;
170 
171  const Util::BitSet& getAtomMask() const;
172  const Util::BitSet& getBondMask() const;
173 
174  void clearFlags();
175 
176  void setRemoveFlag();
177  void setEdgeCollisionFlag();
178 
179  bool getRemoveFlag() const;
180  bool getEdgeCollisionFlag() const;
181 
182  PathMessage& operator^=(const PathMessage&);
183 
184  private:
185  Util::BitSet atomPath;
186  Util::BitSet bondPath;
187  std::size_t firstAtomIdx;
188  std::size_t firstBondIdx;
189  std::size_t maxBondIdx;
190  bool removeFlag;
191  bool edgeCollFlag;
192  };
193 
194  struct TestMatrixRowCmpFunc
195  {
196 
197  bool operator()(const MessagePtr&, const MessagePtr&) const;
198  };
199 
200  typedef std::vector<TNode> NodeArray;
201  typedef std::set<MessagePtr, PathMessage::LessCmpFunc> ProcRingSet;
202 
203  MessageCache msgCache;
204  CyclicSubstructure cyclicSubstruct;
205  Fragment component;
206  Util::BitSet visAtomMask;
207  NodeArray nodes;
208  ProcRingSet procRings;
209  MessageList evenRings;
210  MessagePtr testRing;
211  MessagePtr linDepTestRing;
212  MessageList linDepTestMtx;
213  MessageList sssr;
214  std::size_t sssrSize;
215  };
216  } // namespace Chem
217 } // namespace CDPL
218 
219 #endif // CDPL_CHEM_SMALLESTSETOFSMALLESTRINGS_HPP
ObjectPool.hpp
Definition of the class CDPL::Util::ObjectPool.
APIPrefix.hpp
Definition of the preprocessor macro CDPL_CHEM_API.
CDPL::Chem::SmallestSetOfSmallestRings::SmallestSetOfSmallestRings
SmallestSetOfSmallestRings()
Constructs an empty SmallestSetOfSmallestRings instance.
CDPL_CHEM_API
#define CDPL_CHEM_API
Tells the compiler/linker which classes, functions and variables are part of the library API.
CDPL::Util::BitSet
boost::dynamic_bitset BitSet
A dynamic bitset class.
Definition: BitSet.hpp:46
CDPL::Chem::SmallestSetOfSmallestRings::PathMessage::LessCmpFunc::operator()
bool operator()(const MessagePtr &, const MessagePtr &) const
CDPL::Chem::Atom
Atom.
Definition: Atom.hpp:52
CDPL::Chem::Fragment
Fragment.
Definition: Fragment.hpp:52
CDPL::Chem::SmallestSetOfSmallestRings::perceive
void perceive(const MolecularGraph &molgraph)
Replaces the current set of rings by the SSSR of the molecular graph molgraph.
CDPL::Chem::CyclicSubstructure
Implements the perception of ring atoms and bonds in a molecular graph.
Definition: CyclicSubstructure.hpp:50
CDPL::Chem::MolecularGraph
MolecularGraph.
Definition: MolecularGraph.hpp:52
BitSet.hpp
Definition of the type CDPL::Util::BitSet.
CDPL::Util::ObjectPool< PathMessage >::SharedObjectPointer
std::shared_ptr< ObjectType > SharedObjectPointer
Definition: ObjectPool.hpp:65
CyclicSubstructure.hpp
Definition of the class CDPL::Chem::CyclicSubstructure.
CDPL::Util::ObjectPool< PathMessage >
CDPL::Chem::Fragment::SharedPointer
std::shared_ptr< Fragment > SharedPointer
A reference-counted smart pointer [SHPTR] for dynamically allocated Fragment instances.
Definition: Fragment.hpp:61
CDPL::Chem::FragmentList
A data type for the storage of Chem::Fragment objects.
Definition: FragmentList.hpp:49
CDPL::Chem::SmallestSetOfSmallestRings::SharedPointer
std::shared_ptr< SmallestSetOfSmallestRings > SharedPointer
A reference-counted smart pointer [SHPTR] for dynamically allocated SmallestSetOfSmallestRings instan...
Definition: SmallestSetOfSmallestRings.hpp:64
CDPL::Chem::SmallestSetOfSmallestRings
Implements the perception of the Smallest Set of Smallest Rings (SSSR) of a molecular graphs.
Definition: SmallestSetOfSmallestRings.hpp:58
CDPL
The namespace of the Chemical Data Processing Library.
CDPL::Chem::SmallestSetOfSmallestRings::PathMessage::LessCmpFunc
Definition: SmallestSetOfSmallestRings.hpp:150
CDPL::Chem::SmallestSetOfSmallestRings::SmallestSetOfSmallestRings
SmallestSetOfSmallestRings(const MolecularGraph &molgraph)
Constructs a SmallestSetOfSmallestRings instance containing the SSSR of the molecular graph molgraph.
FragmentList.hpp
Definition of the class CDPL::Chem::FragmentList.