BALL  1.4.1
FPTBondOrderStrategy.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines