BALL
1.4.1
|
00001 // -*- Mode: C++; tab-width: 2; -*- 00002 // vi: set ts=2: 00003 // 00004 // $Id: ringPerceptionProcessor.h,v 1.17.4.2 2007/04/03 13:29:45 bertsch Exp $ 00005 // 00006 00007 #ifndef BALL_QSAR_RINGPERCEPTIONPROCESSOR_H 00008 #define BALL_QSAR_RINGPERCEPTIONPROCESSOR_H 00009 00010 #ifndef BALL_KERNEL_ATOMCONTAINER_H 00011 #include <BALL/KERNEL/atomContainer.h> 00012 #endif 00013 00014 #ifndef BALL_STRUCTURE_SIMPLEMOLECULARGRAPH_H 00015 #include <BALL/STRUCTURE/simpleMolecularGraph.h> 00016 #endif 00017 00018 #ifndef BALL_DATATYPE_OPTIONS_H 00019 #include <BALL/DATATYPE/options.h> 00020 #endif 00021 00022 #include <stack> 00023 #include <vector> 00024 00025 namespace BALL 00026 { 00037 class BALL_EXPORT RingPerceptionProcessor 00038 : public UnaryProcessor<AtomContainer> 00039 { 00040 public: 00041 00045 00046 struct Option 00047 { 00055 static const char* ALGORITHM_NAME; 00056 }; 00057 00059 struct Default 00060 { 00065 static const char* ALGORITHM_NAME; 00066 }; 00067 00068 00069 BALL_CREATE(RingPerceptionProcessor) 00070 00071 00076 RingPerceptionProcessor(); 00077 00080 RingPerceptionProcessor(const RingPerceptionProcessor& rp); 00081 00084 virtual ~RingPerceptionProcessor(); 00085 00087 00090 00093 RingPerceptionProcessor& operator = (const RingPerceptionProcessor& rp); 00094 00096 00099 00104 Size calculateSSSR(vector<vector<Atom*> >& sssr, AtomContainer& ac); 00106 00110 const vector<vector<Atom*> >& getAllSmallRings() const; 00111 00115 Processor::Result operator () (AtomContainer& ac); 00117 00122 Size findAllBCC(std::vector<SimpleMolecularGraph*>& bcc, SimpleMolecularGraph& graph); 00123 00124 /*_ Options for the ring perception 00125 */ 00126 Options options; 00127 00130 void setDefaultOptions(); 00131 00132 protected: 00133 00134 /*_ @name Accessors 00135 */ 00137 /*_ Implementation of the Figueras algorithm. This algorithm has some build 00138 in bugs, and should not be used any more. Hence as default the provable 00139 correct Balducci/Pearlman algorithm is used. 00140 */ 00141 Size FiguerasAlgorithm_(vector<vector<Atom*> >& sssr, AtomContainer& ac); 00142 00143 /*_ Method that return the smallest ring which atom n participates 00144 @param atom from which the search is started 00145 @param ring set in which the found ring is stored (if any) 00146 */ 00147 Size getRing_(Atom* n, HashSet<Atom*>& ring_set); 00148 00149 /*_ A bond, which when deleted leads to the smallest ring 00150 is deleted. 00151 @param ring_set atoms to test 00152 @param ac the atom container the algorithm works on 00153 */ 00154 void checkEdges_(HashSet<Atom*>& ring_set, AtomContainer& ac); 00155 00156 /*_ Method that finds all biconnected components, the algorithm is freely 00157 adapted from a standard bcc algorithm. 00158 */ 00159 Size findAllBCC_(std::vector<SimpleMolecularGraph*>& bcc, SimpleMolecularGraph& graph); 00160 00161 /*_ recursive function that finds bccs 00162 */ 00163 void DFSBCC_( std::vector<SimpleMolecularGraph*>& bccs, Size dfbi, 00164 HashMap<NodeItem<Index, Index>*, Size> DFBIndex, 00165 NodeItem<Index, Index>* v); 00166 00167 HashSet<NodeItem<Index, Index>* > visited_; 00168 HashSet<EdgeItem<Index, Index>* > visited_bonds_; 00169 HashMap<NodeItem<Index, Index>* , Size> P_; 00170 HashMap<NodeItem<Index, Index>*, NodeItem<Index, Index>* > parents_; 00171 std::stack<EdgeItem<Index, Index>* > BCC_; 00172 00173 00174 // Balducci and Pearlman algorithm 00175 struct PathMessage_; 00176 00177 /*_ The tnode structure described in the paper 00178 */ 00179 struct TNode_ 00180 { 00182 void recieve(); 00183 00185 void send(); 00186 00188 std::vector<PathMessage_> recieve_buffer; 00189 00191 std::vector<PathMessage_> send_buffer; 00192 }; 00193 00194 /*_ The pathMsg structure described in the paper 00195 */ 00196 struct PathMessage_ 00197 { 00198 void push(EdgeItem<Index, Index>* bond, TNode_* node); 00199 00200 // path of the message 00201 BitVector beep; 00202 00204 TNode_* nfirst; 00205 00206 // pointer to the last node of the messages' path 00207 TNode_* nlast; 00208 00210 EdgeItem<Index, Index>* efirst; 00211 }; 00212 00214 static HashMap<TNode_*, NodeItem<Index, Index>* > tnode_to_atom_; 00215 static HashMap<NodeItem<Index, Index>* , TNode_*> atom_to_tnode_; 00216 00218 static HashMap<EdgeItem<Index, Index>*, Size> bond_to_index_; 00219 static HashMap<Size, EdgeItem<Index, Index>*> index_to_bond_; 00220 00222 static std::vector<BitVector> rings_; 00223 00225 static std::vector<BitVector> matrix_; 00226 00228 static std::vector<BitVector> forwarded_rings_; 00229 00231 static std::vector<BitVector> tested_beers_; 00232 00234 static std::vector<std::vector<Atom*> > all_small_rings_; 00235 00237 static std::vector<BitVector> all_small_beers_; 00238 00239 /*_ function that gets a binary edge-encoded ring as a BitVector 00240 and adds it to the ringset if its linearly independend 00241 */ 00242 static void BalducciPearlmanRingSelector_(BitVector bit_vector); 00243 00244 /*_ Implementation of the Balducci/Pearlman algorithm 00245 */ 00246 Size BalducciPearlmanAlgorithm_(std::vector<std::vector<Atom*> >& sssr, SimpleMolecularGraph& graph); 00247 }; 00248 } // namespace BALL 00249 00250 #endif // BALL_QSAR_RINGPERCEPTIONPROCESSOR_H