BALL
1.4.1
|
00001 #ifndef BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H 00002 #define BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H 00003 00004 #ifndef BALL_COMMON_GLOBAL_H 00005 # include <BALL/COMMON/global.h> 00006 #endif 00007 00008 #ifndef BALL_COMMON_LIMITS_H 00009 # include <BALL/COMMON/limits.h> 00010 #endif 00011 00012 #ifndef BALL_MATHS_COMMON_H 00013 # include <BALL/MATHS/common.h> 00014 #endif 00015 00016 #ifndef BALL_KERNEL_ATOMCONTAINER_H 00017 # include <BALL/KERNEL/atomContainer.h> 00018 #endif 00019 00020 #ifndef BALL_KERNEL_BOND_H 00021 # include <BALL/KERNEL/bond.h> 00022 #endif 00023 00024 #ifndef BALL_DATATYPE_HASHMAP_H 00025 # include <BALL/DATATYPE/hashMap.h> 00026 #endif 00027 00028 #ifndef BALL_DATATYPE_GRAPH_H 00029 # include <BALL/DATATYPE/GRAPH/molecularGraph.h> 00030 #endif 00031 00032 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H 00033 # include <BALL/DATATYPE/GRAPH/graphAlgorithms.h> 00034 #endif 00035 00036 #ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H 00037 # include <BALL/DATATYPE/GRAPH/treeWidth.h> 00038 #endif 00039 00040 #ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENTSTRATEGY_H 00041 # include <BALL/STRUCTURE/BONDORDERS/bondOrderAssignmentStrategy.h> 00042 #endif 00043 00044 #ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENT_H 00045 # include <BALL/STRUCTURE/BONDORDERS/bondOrderAssignment.h> 00046 #endif 00047 00048 #include <algorithm> 00049 #include <map> 00050 #include <set> 00051 #include <vector> 00052 #include <stack> 00053 #include <iterator> 00054 #include <queue> 00055 00056 #include <boost/shared_ptr.hpp> 00057 #include <boost/ref.hpp> 00058 00059 namespace BALL 00060 { 00061 //TODO: documentation is obsolete! 00125 class BALL_EXPORT FPTBondOrderStrategy 00126 : public BondOrderAssignmentStrategy 00127 { 00128 public: 00129 typedef GRAPH::GraphTraits<MolecularGraph>::EdgeType Edge; 00130 typedef GRAPH::GraphTraits<MolecularGraph>::VertexType VertexType; 00131 00132 typedef TreeWidth<MolecularGraph>::TreeDecomposition TreeDecomposition; 00133 typedef TreeWidth<MolecularGraph>::TreeDecompositionBag TreeDecompositionBag; 00134 00135 friend class FPTBondOrderAssignment_; 00136 00140 typedef float Penalty; 00141 00146 typedef int Valence; 00147 00152 typedef int BondOrder; 00153 00156 static const Penalty infinite_penalty; 00157 static const Valence max_valence; 00158 00160 00161 struct BALL_EXPORT Option 00162 { 00167 static String UPPER_PENALTY_BOUND; 00168 }; 00169 00171 struct BALL_EXPORT Default 00172 { 00177 static Penalty UPPER_PENALTY_BOUND; 00178 }; 00179 00181 00182 FPTBondOrderStrategy(AssignBondOrderProcessor* parent); 00183 00188 virtual ~FPTBondOrderStrategy(); 00189 00195 virtual void clear(); 00196 00202 virtual void init(); 00203 00204 virtual bool readOptions(const Options& options); 00205 virtual void setDefaultOptions(); 00206 00212 virtual boost::shared_ptr<BondOrderAssignment> computeNextSolution(); 00213 00214 protected: 00224 class DPConfig_ 00225 { 00226 public: 00230 DPConfig_(); 00231 00236 DPConfig_(Size atoms, Size bonds); 00237 00241 DPConfig_(std::vector<Valence> const& v, std::vector<BondOrder> const& bo); 00242 00246 DPConfig_& operator=(DPConfig_ const& copy); 00247 00251 template<typename ValenceIterator, typename BondIterator> 00252 DPConfig_(ValenceIterator vit, ValenceIterator vend, BondIterator boit, BondIterator boend) 00253 : consumed_valences(vit, vend), 00254 bond_assignments(boit, boend) 00255 { 00256 } 00257 00261 bool operator < (DPConfig_ const& conf) const; 00262 00266 bool operator > (DPConfig_ const& conf) const; 00267 00271 bool operator <= (DPConfig_ const& conf) const; 00272 00276 bool operator >= (DPConfig_ const& conf) const; 00277 00281 bool operator == (DPConfig_ const& conf) const; 00282 00293 int compare(DPConfig_ const& other) const; 00294 00298 Size numberOfAtoms() const; 00299 00303 Size numberOfBonds() const; 00304 00309 std::vector<Valence> consumed_valences; 00310 00318 std::vector<BondOrder> bond_assignments; 00319 00320 }; 00321 00326 typedef std::pair<boost::reference_wrapper<DPConfig_>, Penalty> DPRow_; 00327 00332 typedef std::pair<boost::reference_wrapper<DPConfig_ const>, Penalty> DPConstRow_; 00333 00339 typedef std::pair<DPConfig_*, Penalty> DPPointerRow_; 00340 00345 typedef std::map<DPConfig_, Penalty> DPMap_; 00346 00354 class DPTable_ 00355 { 00356 protected: 00361 DPMap_ table; 00362 00363 public: 00367 DPTable_(); 00368 00372 DPTable_(DPTable_ const& table); 00373 00377 typedef DPMap_::iterator iterator; 00378 00382 typedef DPMap_::const_iterator const_iterator; 00383 00387 Penalty operator[](DPConfig_ const& config) const; 00388 00393 bool insert(DPConfig_ const& config, Penalty penalty); 00394 00398 Size size() const; 00399 00403 Penalty bestPenalty() const; 00404 00410 DPConstRow_ bestEntry() const; 00411 00415 iterator begin(); 00416 00420 iterator end(); 00421 00425 const_iterator begin() const; 00426 00430 const_iterator end() const; 00431 }; 00432 00438 class AdditionalBagProperties_ 00439 { 00440 public: 00444 AdditionalBagProperties_(); 00445 00449 AdditionalBagProperties_(AdditionalBagProperties_ const& copy); 00450 00454 AdditionalBagProperties_& operator=(AdditionalBagProperties_ const& copy); 00455 00459 ~AdditionalBagProperties_(); 00460 00464 std::vector<MolecularGraphTraits::EdgeType> bonds; 00465 00469 DPTable_ * table; 00470 }; 00471 00472 class DPBackTracking_; 00473 class DPBackTrackingCombiner_; 00474 00482 class FPTBondOrderAssignment_ 00483 { 00484 public: 00485 friend class DPBackTracking_; 00486 friend class DPBackTrackingCombiner_; 00487 friend class GRAPH::PostOrderFolding<TreeDecomposition, TreeDecompositionBag, DPTable_*, FPTBondOrderAssignment_>; 00488 00496 FPTBondOrderAssignment_(FPTBondOrderStrategy& parent, boost::shared_ptr<TreeDecomposition>& ntd, 00497 Penalty upper_bound = infinite_penalty); 00498 00504 ~FPTBondOrderAssignment_(); 00505 00511 Penalty compute(); 00512 00513 protected: 00517 FPTBondOrderStrategy* parent_; 00518 00522 MolecularGraph * molecule_; 00523 00527 boost::shared_ptr<TreeDecomposition> ntd_; 00528 00533 vector<AdditionalBagProperties_> properties_; 00534 00542 Penalty upper_bound_; 00543 00547 BondOrder max_bond_order_; 00548 00552 Valence max_valence_; 00553 00566 DPTable_* operator() (TreeDecompositionBag& bag, 00567 std::vector<DPTable_*>::const_iterator begin, std::vector<DPTable_*>::const_iterator end); 00568 00576 std::vector<MolecularGraphTraits::EdgeType> getBondsInBag(TreeDecompositionBag& bag); 00577 00584 void computeLeafIntroduceBag(AdditionalBagProperties_& bag_properties); 00585 00596 void computeIntroduceBag(TreeDecompositionBag& bag, 00597 DPTable_& child, AdditionalBagProperties_& bag_properties); 00598 00613 void computeForgetBag(TreeDecompositionBag& bag, 00614 DPTable_& child, AdditionalBagProperties_& property); 00615 00629 void computeJoinBag(TreeDecompositionBag& bag, 00630 DPTable_& leftChild, DPTable_& rightChild, AdditionalBagProperties_& bag_properties); 00631 00637 void computeRootBag(TreeDecompositionBag& bag, DPTable_& child, AdditionalBagProperties_& bag_properties); 00638 00644 Penalty forgetInnerVertexIn(TreeDecompositionBag& bag, DPConstRow_ child_row, DPConfig_& entry, 00645 std::vector<MolecularGraphTraits::EdgeType>& child_bonds, Size forgotten_index); 00646 00647 }; 00648 00654 class ComputingData_ 00655 { 00656 public: 00660 ComputingData_(); 00661 00665 ~ComputingData_(); 00666 00670 vector<FPTBondOrderAssignment_*> bond_assignments; 00671 00675 MolecularGraph *molecule_graph; 00676 00680 boost::shared_ptr<TreeWidth<MolecularGraph> > tw; 00681 00686 vector<Bond const *> bonds; 00687 }; 00688 00702 class Assignment_ 00703 { 00704 public: 00708 Assignment_(); 00709 00714 Assignment_(Size num_bonds); 00715 00719 Assignment_(Assignment_ const& copy); 00720 00725 Assignment_(std::vector<BondOrder> const& bonds, Penalty penalty); 00726 00730 Assignment_& operator=(Assignment_ const& copy); 00731 00736 BondOrder operator [](Size index) const; 00737 00742 BondOrder& operator [](Size index); 00743 00754 void combine(Assignment_ const& other); 00755 00759 std::vector<BondOrder> const& getBondOrders() const; 00760 00766 int compare(Assignment_ const& a) const; 00767 00771 bool operator < (Assignment_ const& a) const; 00772 00776 bool operator > (Assignment_ const& a) const; 00777 00781 bool operator <= (Assignment_ const& a) const; 00782 00786 bool operator >= (Assignment_ const& a) const; 00787 00791 bool operator == (Assignment_ const& a) const; 00792 00801 bool isValid(MolecularGraph& molecule, FPTBondOrderStrategy& parent); 00802 00806 Penalty penalty; 00807 00808 protected: 00812 std::vector<BondOrder> bonds_; 00813 00814 }; 00815 00821 struct DPJoinMapComparator_ 00822 { 00827 bool operator() (DPConfig_ const* leftp, DPConfig_ const* rightp) const; 00828 00834 int compare(DPConfig_ const* leftp, DPConfig_ const* rightp) const; 00835 }; 00836 00839 class EdgeComparator_ 00840 { 00841 public: 00842 typedef GRAPH::GraphTraits<MolecularGraph>::EdgeType Edge; 00843 00844 EdgeComparator_(MolecularGraph* graph) 00845 : graph_(graph) 00846 { } 00847 00848 bool operator() (Edge const& e1, Edge const& e2); 00849 00850 protected: 00851 MolecularGraph* graph_; 00852 }; 00853 00860 class BackTrackingState_ 00861 { 00862 public: 00866 BackTrackingState_(); 00867 00871 BackTrackingState_(Size bonds); 00872 00876 BackTrackingState_(BackTrackingState_ const& other); 00877 00881 BackTrackingState_& operator=(BackTrackingState_ const& other); 00882 00887 int compare(BackTrackingState_ const& other) const; 00888 00892 bool operator < (BackTrackingState_ const&) const; 00893 00897 bool operator > (BackTrackingState_ const&) const; 00898 00902 bool operator <= (BackTrackingState_ const&) const; 00903 00907 bool operator >= (BackTrackingState_ const&) const; 00908 00912 bool operator == (BackTrackingState_ const&) const; 00913 00918 Assignment_ assignment; 00919 00924 DPConfig_ config; 00925 00931 std::stack<std::pair<DPConfig_, Size> > join_branches; 00932 00937 Size index; 00938 00939 00940 }; 00941 00946 typedef std::pair<DPTable_::const_iterator, DPTable_::const_iterator> DPPairIt_; 00947 00951 static bool compareJoinTablePairs_(DPPairIt_ const& left, DPPairIt_ const& right); 00952 00956 static bool compareTablePointerEntries_(DPPointerRow_ const& left, DPPointerRow_ const& right); 00957 00962 typedef std::multimap<DPConfig_ const*, Penalty, DPJoinMapComparator_> DPJoinMap_; 00963 00983 class DPBackTracking_ 00984 { 00985 public: 00986 typedef TreeWidth<MolecularGraph>::TreeDecomposition TreeDecomposition; 00987 typedef TreeWidth<MolecularGraph>::TreeDecompositionBag TreeDecompositionBag; 00988 typedef TreeWidth<MolecularGraph>::TreeDecompositionContent TreeDecompositionContent; 00989 01000 DPBackTracking_(FPTBondOrderAssignment_& bond_assignment, Size max_number_of_solutions, 01001 std::vector<MolecularGraphTraits::EdgeType> const& bonds, Penalty upperbound = infinite_penalty); 01002 01006 DPBackTracking_(DPBackTracking_ const& copy); 01007 01011 ~DPBackTracking_(); 01012 01016 DPBackTracking_& operator= (DPBackTracking_ const& copy); 01017 01023 Assignment_& getSolution(); 01024 01031 Assignment_ const& getSolution() const; 01032 01037 bool hasMoreSolutions() const; 01038 01043 void nextSolution(); 01044 01049 Penalty penaltyOfNextSolution() const; 01050 01051 void clear(); 01052 01053 void preorder(TreeDecompositionBag node, TreeDecomposition&) 01054 { 01055 bags_->push_back(node); 01056 } 01057 01058 void inorder(TreeDecompositionBag, TreeDecomposition&) 01059 { 01060 } 01061 01062 void postorder(TreeDecompositionBag, TreeDecomposition&) 01063 { 01064 } 01065 01066 protected: 01067 01071 struct StateComparator_ 01072 { 01076 bool operator () (BackTrackingState_ const * left, BackTrackingState_ const * right) const; 01077 }; 01078 01084 FPTBondOrderAssignment_* bond_assignment_; 01085 01089 BackTrackingState_* current_state_; 01090 01095 std::multiset<BackTrackingState_*, StateComparator_> queue_; 01096 01100 Size max_num_solutions_; 01101 01106 std::vector<MolecularGraphTraits::EdgeType> const* bonds_; 01107 01111 boost::shared_ptr<std::vector<TreeDecompositionBag> > bags_; 01112 01117 Size max_heap_size_; 01118 01122 Penalty upper_bound_; 01123 01124 typedef vector<TreeDecompositionBag> BagVector; 01125 01129 DPTable_& getTable(Size order); 01130 01134 AdditionalBagProperties_& getProperties(Size order); 01135 01141 void visitLeaf(BackTrackingState_& state); 01142 01155 void visitJoin(BackTrackingState_& state, TreeDecompositionBag& bag, 01156 DPTable_& leftTable, DPTable_& rightTable); 01157 01165 void visitForget(BackTrackingState_& state, TreeDecompositionBag& bag, DPTable_& table); 01166 01174 void visitIntroduce(BackTrackingState_& state, TreeDecompositionBag& bag, DPTable_& table); 01175 01181 Size bondIndexFor(MolecularGraphTraits::EdgeType bond) const; 01182 01190 void remember(BackTrackingState_& state); 01191 01196 bool isSolutionNeeded(Penalty penalty); 01197 01206 void setStateAssignment(BackTrackingState_& state, TreeDecompositionBag& bag, 01207 DPConfig_& antecessor, MolecularGraphTraits::VertexType forgotten_vertex); 01208 01216 void extendState(BackTrackingState_& state, DPConfig_ const& antecessor, Penalty additional_penalty); 01217 01224 void branchState(BackTrackingState_& state, TreeDecompositionBag const& child, DPConfig_ const& antecessor); 01225 01226 }; 01227 01239 class DPBackTrackingCombiner_ 01240 { 01241 public: 01247 DPBackTrackingCombiner_(std::vector<FPTBondOrderAssignment_*>& bond_assignments, 01248 Size solution_number, Penalty upper_bound = infinite_penalty); 01249 01255 DPBackTrackingCombiner_(std::vector<FPTBondOrderAssignment_>& bond_assignments, 01256 Size solution_number, Penalty upper_bound = infinite_penalty); 01257 01261 DPBackTrackingCombiner_(DPBackTrackingCombiner_ const& copy); 01262 01266 ~DPBackTrackingCombiner_(); 01267 01268 void clear(); 01269 01273 DPBackTrackingCombiner_& operator = (DPBackTrackingCombiner_ const& copy); 01274 01278 bool hasMoreSolutions() const; 01279 01284 void nextSolution(); 01285 01289 Assignment_& getSolution(); 01290 01294 Assignment_ const& getSolution() const; 01295 01300 Penalty penaltyOfNextSolution() const; 01301 01306 std::vector<MolecularGraphTraits::EdgeType> sorted_edges; 01307 01308 protected: 01312 std::vector<DPBackTracking_*> backtrackers_; 01313 01319 std::priority_queue<Assignment_, std::vector<Assignment_>, std::greater<Assignment_> > priority_queue_; 01320 01325 std::vector<std::vector<Assignment_> > component_solutions_; 01326 01330 Assignment_ assignment_; 01331 01335 Size solution_number_; 01336 01340 Penalty optimum_; 01341 01345 Penalty upper_bound_; 01346 01351 std::pair<Size, Penalty> getNextMinimumBackTracker_() const; 01352 01358 void applyAssignment_(Size backtracker_index, Size solution_index); 01359 01363 void initialize_(); 01364 01369 void combineEachSolution_(Size mindex); 01370 01374 std::vector<DPBackTracking_*> deepCopyOfBacktrackers_() const; 01375 01376 }; 01377 01378 01380 void initPenaltyData_(); 01381 01383 Penalty getPenaltyFor_(MolecularGraphTraits::VertexType vertex, Valence valence) const; 01384 01388 std::vector<int> const* penalties_; 01389 01393 std::vector<Position> const * block_to_start_idx_; 01394 01398 std::vector<Size> const * block_to_length_; 01399 01403 std::vector<int> const * block_to_start_valence_; 01404 01408 std::vector<std::vector<int> > const* atom_to_block_; 01409 01411 Penalty upper_bound_; 01412 01417 boost::shared_ptr<ComputingData_> computing_data_; 01418 01422 boost::shared_ptr<DPBackTrackingCombiner_> combiner_; 01423 }; 01424 } 01425 #endif // BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H