BALL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
FPTBondOrderStrategy.h
Go to the documentation of this file.
1 #ifndef BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H
2 #define BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H
3 
4 #ifndef BALL_COMMON_GLOBAL_H
5 # include <BALL/COMMON/global.h>
6 #endif
7 
8 #ifndef BALL_COMMON_LIMITS_H
9 # include <BALL/COMMON/limits.h>
10 #endif
11 
12 #ifndef BALL_MATHS_COMMON_H
13 # include <BALL/MATHS/common.h>
14 #endif
15 
16 #ifndef BALL_KERNEL_ATOMCONTAINER_H
18 #endif
19 
20 #ifndef BALL_KERNEL_BOND_H
21 # include <BALL/KERNEL/bond.h>
22 #endif
23 
24 #ifndef BALL_DATATYPE_HASHMAP_H
25 # include <BALL/DATATYPE/hashMap.h>
26 #endif
27 
28 #ifndef BALL_DATATYPE_GRAPH_H
30 #endif
31 
32 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
34 #endif
35 
36 #ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H
38 #endif
39 
40 #ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENTSTRATEGY_H
42 #endif
43 
44 #ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENT_H
46 #endif
47 
48 #include <algorithm>
49 #include <map>
50 #include <set>
51 #include <vector>
52 #include <stack>
53 #include <iterator>
54 #include <queue>
55 
56 #include <boost/shared_ptr.hpp>
57 #include <boost/ref.hpp>
58 
59 namespace BALL
60 {
61  //TODO: documentation is obsolete!
127  {
128  public:
131 
134 
136 
140  typedef float Penalty;
141 
146  typedef int Valence;
147 
152  typedef int BondOrder;
153 
156  static const Penalty infinite_penalty;
157  static const Valence max_valence;
158 
160 
162  {
168  };
169 
172  {
178  };
179 
181 
183 
188  virtual ~FPTBondOrderStrategy();
189 
195  virtual void clear();
196 
202  virtual void init();
203 
204  virtual bool readOptions(const Options& options);
205  virtual void setDefaultOptions();
206 
212  virtual boost::shared_ptr<BondOrderAssignment> computeNextSolution();
213 
214  protected:
224  class DPConfig_
225  {
226  public:
230  DPConfig_();
231 
237 
241  DPConfig_(std::vector<Valence> const& v, std::vector<BondOrder> const& bo);
242 
246  DPConfig_& operator=(DPConfig_ const& copy);
247 
251  template<typename ValenceIterator, typename BondIterator>
252  DPConfig_(ValenceIterator vit, ValenceIterator vend, BondIterator boit, BondIterator boend)
253  : consumed_valences(vit, vend),
254  bond_assignments(boit, boend)
255  {
256  }
257 
261  bool operator < (DPConfig_ const& conf) const;
262 
266  bool operator > (DPConfig_ const& conf) const;
267 
271  bool operator <= (DPConfig_ const& conf) const;
272 
276  bool operator >= (DPConfig_ const& conf) const;
277 
281  bool operator == (DPConfig_ const& conf) const;
282 
293  int compare(DPConfig_ const& other) const;
294 
298  Size numberOfAtoms() const;
299 
303  Size numberOfBonds() const;
304 
309  std::vector<Valence> consumed_valences;
310 
318  std::vector<BondOrder> bond_assignments;
319 
320  };
321 
326  typedef std::pair<boost::reference_wrapper<DPConfig_>, Penalty> DPRow_;
327 
332  typedef std::pair<boost::reference_wrapper<DPConfig_ const>, Penalty> DPConstRow_;
333 
339  typedef std::pair<DPConfig_*, Penalty> DPPointerRow_;
340 
345  typedef std::map<DPConfig_, Penalty> DPMap_;
346 
354  class DPTable_
355  {
356  protected:
362 
363  public:
367  DPTable_();
368 
372  DPTable_(DPTable_ const& table);
373 
377  typedef DPMap_::iterator iterator;
378 
382  typedef DPMap_::const_iterator const_iterator;
383 
387  Penalty operator[](DPConfig_ const& config) const;
388 
393  bool insert(DPConfig_ const& config, Penalty penalty);
394 
398  Size size() const;
399 
403  Penalty bestPenalty() const;
404 
410  DPConstRow_ bestEntry() const;
411 
415  iterator begin();
416 
420  iterator end();
421 
425  const_iterator begin() const;
426 
430  const_iterator end() const;
431  };
432 
439  {
440  public:
445 
450 
454  AdditionalBagProperties_& operator=(AdditionalBagProperties_ const& copy);
455 
460 
464  std::vector<MolecularGraphTraits::EdgeType> bonds;
465 
470  };
471 
472  class DPBackTracking_;
474 
483  {
484  public:
485  friend class DPBackTracking_;
488 
496  FPTBondOrderAssignment_(FPTBondOrderStrategy& parent, boost::shared_ptr<TreeDecomposition>& ntd,
497  Penalty upper_bound = infinite_penalty);
498 
505 
511  Penalty compute();
512 
513  protected:
518 
523 
527  boost::shared_ptr<TreeDecomposition> ntd_;
528 
533  vector<AdditionalBagProperties_> properties_;
534 
543 
548 
553 
566  DPTable_* operator() (TreeDecompositionBag& bag,
567  std::vector<DPTable_*>::const_iterator begin, std::vector<DPTable_*>::const_iterator end);
568 
576  std::vector<MolecularGraphTraits::EdgeType> getBondsInBag(TreeDecompositionBag& bag);
577 
584  void computeLeafIntroduceBag(AdditionalBagProperties_& bag_properties);
585 
596  void computeIntroduceBag(TreeDecompositionBag& bag,
597  DPTable_& child, AdditionalBagProperties_& bag_properties);
598 
613  void computeForgetBag(TreeDecompositionBag& bag,
614  DPTable_& child, AdditionalBagProperties_& property);
615 
629  void computeJoinBag(TreeDecompositionBag& bag,
630  DPTable_& leftChild, DPTable_& rightChild, AdditionalBagProperties_& bag_properties);
631 
637  void computeRootBag(TreeDecompositionBag& bag, DPTable_& child, AdditionalBagProperties_& bag_properties);
638 
644  Penalty forgetInnerVertexIn(TreeDecompositionBag& bag, DPConstRow_ child_row, DPConfig_& entry,
645  std::vector<MolecularGraphTraits::EdgeType>& child_bonds, Size forgotten_index);
646 
647  };
648 
655  {
656  public:
660  ComputingData_();
661 
665  ~ComputingData_();
666 
670  vector<FPTBondOrderAssignment_*> bond_assignments;
671 
676 
680  boost::shared_ptr<TreeWidth<MolecularGraph> > tw;
681 
686  vector<Bond const *> bonds;
687  };
688 
703  {
704  public:
708  Assignment_();
709 
714  Assignment_(Size num_bonds);
715 
719  Assignment_(Assignment_ const& copy);
720 
725  Assignment_(std::vector<BondOrder> const& bonds, Penalty penalty);
726 
730  Assignment_& operator=(Assignment_ const& copy);
731 
736  BondOrder operator [](Size index) const;
737 
742  BondOrder& operator [](Size index);
743 
754  void combine(Assignment_ const& other);
755 
759  std::vector<BondOrder> const& getBondOrders() const;
760 
766  int compare(Assignment_ const& a) const;
767 
771  bool operator < (Assignment_ const& a) const;
772 
776  bool operator > (Assignment_ const& a) const;
777 
781  bool operator <= (Assignment_ const& a) const;
782 
786  bool operator >= (Assignment_ const& a) const;
787 
791  bool operator == (Assignment_ const& a) const;
792 
801  bool isValid(MolecularGraph& molecule, FPTBondOrderStrategy& parent);
802 
807 
808  protected:
812  std::vector<BondOrder> bonds_;
813 
814  };
815 
822  {
827  bool operator() (DPConfig_ const* leftp, DPConfig_ const* rightp) const;
828 
834  int compare(DPConfig_ const* leftp, DPConfig_ const* rightp) const;
835  };
836 
840  {
841  public:
843 
845  : graph_(graph)
846  { }
847 
848  bool operator() (Edge const& e1, Edge const& e2);
849 
850  protected:
852  };
853 
861  {
862  public:
867 
872 
877 
881  BackTrackingState_& operator=(BackTrackingState_ const& other);
882 
887  int compare(BackTrackingState_ const& other) const;
888 
892  bool operator < (BackTrackingState_ const&) const;
893 
897  bool operator > (BackTrackingState_ const&) const;
898 
902  bool operator <= (BackTrackingState_ const&) const;
903 
907  bool operator >= (BackTrackingState_ const&) const;
908 
912  bool operator == (BackTrackingState_ const&) const;
913 
919 
925 
931  std::stack<std::pair<DPConfig_, Size> > join_branches;
932 
938 
939 
940  };
941 
946  typedef std::pair<DPTable_::const_iterator, DPTable_::const_iterator> DPPairIt_;
947 
951  static bool compareJoinTablePairs_(DPPairIt_ const& left, DPPairIt_ const& right);
952 
956  static bool compareTablePointerEntries_(DPPointerRow_ const& left, DPPointerRow_ const& right);
957 
962  typedef std::multimap<DPConfig_ const*, Penalty, DPJoinMapComparator_> DPJoinMap_;
963 
984  {
985  public:
989 
1000  DPBackTracking_(FPTBondOrderAssignment_& bond_assignment, Size max_number_of_solutions,
1001  std::vector<MolecularGraphTraits::EdgeType> const& bonds, Penalty upperbound = infinite_penalty);
1002 
1006  DPBackTracking_(DPBackTracking_ const& copy);
1007 
1011  ~DPBackTracking_();
1012 
1016  DPBackTracking_& operator= (DPBackTracking_ const& copy);
1017 
1023  Assignment_& getSolution();
1024 
1031  Assignment_ const& getSolution() const;
1032 
1037  bool hasMoreSolutions() const;
1038 
1043  void nextSolution();
1044 
1049  Penalty penaltyOfNextSolution() const;
1050 
1051  void clear();
1052 
1054  {
1055  bags_->push_back(node);
1056  }
1057 
1059  {
1060  }
1061 
1063  {
1064  }
1065 
1066  protected:
1067 
1072  {
1076  bool operator () (BackTrackingState_ const * left, BackTrackingState_ const * right) const;
1077  };
1078 
1085 
1090 
1095  std::multiset<BackTrackingState_*, StateComparator_> queue_;
1096 
1101 
1106  std::vector<MolecularGraphTraits::EdgeType> const* bonds_;
1107 
1111  boost::shared_ptr<std::vector<TreeDecompositionBag> > bags_;
1112 
1118 
1123 
1128 
1129  typedef vector<TreeDecompositionBag> BagVector;
1130 
1134  DPTable_& getTable(Size order);
1135 
1139  AdditionalBagProperties_& getProperties(Size order);
1140 
1146  void visitLeaf(BackTrackingState_& state);
1147 
1160  void visitJoin(BackTrackingState_& state, TreeDecompositionBag& bag,
1161  DPTable_& leftTable, DPTable_& rightTable);
1162 
1170  void visitForget(BackTrackingState_& state, TreeDecompositionBag& bag, DPTable_& table);
1171 
1179  void visitIntroduce(BackTrackingState_& state, TreeDecompositionBag& bag, DPTable_& table);
1180 
1186  Size bondIndexFor(MolecularGraphTraits::EdgeType bond) const;
1187 
1195  void remember(BackTrackingState_& state);
1196 
1201  bool isSolutionNeeded(Penalty penalty);
1202 
1211  void setStateAssignment(BackTrackingState_& state, TreeDecompositionBag& bag,
1212  DPConfig_& antecessor, MolecularGraphTraits::VertexType forgotten_vertex);
1213 
1221  void extendState(BackTrackingState_& state, DPConfig_ const& antecessor, Penalty additional_penalty);
1222 
1229  void branchState(BackTrackingState_& state, TreeDecompositionBag const& child, DPConfig_ const& antecessor);
1230 
1231  };
1232 
1245  {
1246  public:
1252  DPBackTrackingCombiner_(std::vector<FPTBondOrderAssignment_*>& bond_assignments,
1253  Size solution_number, Penalty upper_bound = infinite_penalty);
1254 
1259 
1264 
1265  void clear();
1266 
1270  DPBackTrackingCombiner_& operator = (DPBackTrackingCombiner_ const& copy);
1271 
1275  bool hasMoreSolutions() const;
1276 
1281  void nextSolution();
1282 
1286  Assignment_& getSolution();
1287 
1291  Assignment_ const& getSolution() const;
1292 
1297  Penalty penaltyOfNextSolution() const;
1298 
1303  std::vector<MolecularGraphTraits::EdgeType> sorted_edges;
1304 
1305  protected:
1309  std::vector<DPBackTracking_*> backtrackers_;
1310 
1316  std::priority_queue<Assignment_, std::vector<Assignment_>, std::greater<Assignment_> > priority_queue_;
1317 
1322  std::vector<std::vector<Assignment_> > component_solutions_;
1323 
1328 
1333 
1338 
1343 
1348  std::pair<Size, Penalty> getNextMinimumBackTracker_() const;
1349 
1355  void applyAssignment_(Size backtracker_index, Size solution_index);
1356 
1360  void initialize_();
1361 
1366  void combineEachSolution_(Size mindex);
1367 
1371  std::vector<DPBackTracking_*> deepCopyOfBacktrackers_() const;
1372 
1373  };
1374 
1375 
1377  void initPenaltyData_();
1378 
1380  Penalty getPenaltyFor_(MolecularGraphTraits::VertexType vertex, Valence valence) const;
1381 
1385  std::vector<int> const* penalties_;
1386 
1390  std::vector<Position> const * block_to_start_idx_;
1391 
1395  std::vector<Size> const * block_to_length_;
1396 
1400  std::vector<int> const * block_to_start_valence_;
1401 
1405  std::vector<std::vector<int> > const* atom_to_block_;
1406 
1411  boost::shared_ptr<ComputingData_> computing_data_;
1412 
1416  boost::shared_ptr<DPBackTrackingCombiner_> combiner_;
1417  };
1418 }
1419 #endif // BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H