BALL 1.5.0
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_MATHS_COMMON_H
9# include <BALL/MATHS/common.h>
10#endif
11
12#ifndef BALL_KERNEL_ATOMCONTAINER_H
14#endif
15
16#ifndef BALL_KERNEL_BOND_H
17# include <BALL/KERNEL/bond.h>
18#endif
19
20#ifndef BALL_DATATYPE_HASHMAP_H
22#endif
23
24#ifndef BALL_DATATYPE_GRAPH_H
26#endif
27
28#ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
30#endif
31
32#ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H
34#endif
35
36#ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENTSTRATEGY_H
38#endif
39
40#ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENT_H
42#endif
43
44#include <algorithm>
45#include <map>
46#include <set>
47#include <vector>
48#include <stack>
49#include <iterator>
50#include <queue>
51
52#include <boost/shared_ptr.hpp>
53#include <boost/ref.hpp>
54
55namespace BALL
56{
57 //TODO: documentation is obsolete!
123 {
124 public:
127
130
132
136 typedef float Penalty;
137
142 typedef int Valence;
143
148 typedef int BondOrder;
149
153 static const Valence max_valence;
154
156
158 {
164 };
165
168 {
174 };
175
177
179
185
191 virtual void clear();
192
198 virtual void init();
199
200 virtual bool readOptions(const Options& options);
201 virtual void setDefaultOptions();
202
208 virtual boost::shared_ptr<BondOrderAssignment> computeNextSolution();
209
210 protected:
221 {
222 public:
227
233
237 DPConfig_(std::vector<Valence> const& v, std::vector<BondOrder> const& bo);
238
243
247 template<typename ValenceIterator, typename BondIterator>
248 DPConfig_(ValenceIterator vit, ValenceIterator vend, BondIterator boit, BondIterator boend)
249 : consumed_valences(vit, vend),
250 bond_assignments(boit, boend)
251 {
252 }
253
257 bool operator < (DPConfig_ const& conf) const;
258
262 bool operator > (DPConfig_ const& conf) const;
263
267 bool operator <= (DPConfig_ const& conf) const;
268
272 bool operator >= (DPConfig_ const& conf) const;
273
277 bool operator == (DPConfig_ const& conf) const;
278
289 int compare(DPConfig_ const& other) const;
290
295
300
305 std::vector<Valence> consumed_valences;
306
314 std::vector<BondOrder> bond_assignments;
315
316 };
317
322 typedef std::pair<boost::reference_wrapper<DPConfig_>, Penalty> DPRow_;
323
328 typedef std::pair<boost::reference_wrapper<DPConfig_ const>, Penalty> DPConstRow_;
329
335 typedef std::pair<DPConfig_*, Penalty> DPPointerRow_;
336
341 typedef std::map<DPConfig_, Penalty> DPMap_;
342
351 {
352 protected:
358
359 public:
364
368 DPTable_(DPTable_ const& table);
369
373 typedef DPMap_::iterator iterator;
374
378 typedef DPMap_::const_iterator const_iterator;
379
383 Penalty operator[](DPConfig_ const& config) const;
384
389 bool insert(DPConfig_ const& config, Penalty penalty);
390
394 Size size() const;
395
400
407
412
417
422
427 };
428
435 {
436 public:
441
446
451
456
460 std::vector<MolecularGraphTraits::EdgeType> bonds;
461
466 };
467
468 class DPBackTracking_;
470
479 {
480 public:
481 friend class DPBackTracking_;
484
492 FPTBondOrderAssignment_(FPTBondOrderStrategy& parent, boost::shared_ptr<TreeDecomposition>& ntd,
493 Penalty upper_bound = infinite_penalty);
494
501
508
509 protected:
514
519
523 boost::shared_ptr<TreeDecomposition> ntd_;
524
529 vector<AdditionalBagProperties_> properties_;
530
539
544
549
562 DPTable_* operator() (TreeDecompositionBag& bag,
563 std::vector<DPTable_*>::const_iterator begin, std::vector<DPTable_*>::const_iterator end);
564
572 std::vector<MolecularGraphTraits::EdgeType> getBondsInBag(TreeDecompositionBag& bag);
573
581
593 DPTable_& child, AdditionalBagProperties_& bag_properties);
594
610 DPTable_& child, AdditionalBagProperties_& property);
611
626 DPTable_& leftChild, DPTable_& rightChild, AdditionalBagProperties_& bag_properties);
627
634
641 std::vector<MolecularGraphTraits::EdgeType>& child_bonds, Size forgotten_index);
642
643 };
644
651 {
652 public:
657
662
666 vector<FPTBondOrderAssignment_*> bond_assignments;
667
672
676 boost::shared_ptr<TreeWidth<MolecularGraph> > tw;
677
682 vector<Bond const *> bonds;
683 };
684
699 {
700 public:
705
710 Assignment_(Size num_bonds);
711
716
721 Assignment_(std::vector<BondOrder> const& bonds, Penalty penalty);
722
727
732 BondOrder operator [](Size index) const;
733
738 BondOrder& operator [](Size index);
739
750 void combine(Assignment_ const& other);
751
755 std::vector<BondOrder> const& getBondOrders() const;
756
762 int compare(Assignment_ const& a) const;
763
767 bool operator < (Assignment_ const& a) const;
768
772 bool operator > (Assignment_ const& a) const;
773
777 bool operator <= (Assignment_ const& a) const;
778
782 bool operator >= (Assignment_ const& a) const;
783
787 bool operator == (Assignment_ const& a) const;
788
798
803
804 protected:
808 std::vector<BondOrder> bonds_;
809
810 };
811
818 {
823 bool operator() (DPConfig_ const* leftp, DPConfig_ const* rightp) const;
824
830 int compare(DPConfig_ const* leftp, DPConfig_ const* rightp) const;
831 };
832
836 {
837 public:
839
841 : graph_(graph)
842 { }
843
844 bool operator() (Edge const& e1, Edge const& e2);
845
846 protected:
848 };
849
857 {
858 public:
863
868
873
878
883 int compare(BackTrackingState_ const& other) const;
884
888 bool operator < (BackTrackingState_ const&) const;
889
893 bool operator > (BackTrackingState_ const&) const;
894
899
904
909
915
921
927 std::stack<std::pair<DPConfig_, Size> > join_branches;
928
934
935
936 };
937
942 typedef std::pair<DPTable_::const_iterator, DPTable_::const_iterator> DPPairIt_;
943
947 static bool compareJoinTablePairs_(DPPairIt_ const& left, DPPairIt_ const& right);
948
952 static bool compareTablePointerEntries_(DPPointerRow_ const& left, DPPointerRow_ const& right);
953
958 typedef std::multimap<DPConfig_ const*, Penalty, DPJoinMapComparator_> DPJoinMap_;
959
980 {
981 public:
985
996 DPBackTracking_(FPTBondOrderAssignment_& bond_assignment, Size max_number_of_solutions,
997 std::vector<MolecularGraphTraits::EdgeType> const& bonds, Penalty upperbound = infinite_penalty);
998
1003
1008
1012 DPBackTracking_& operator= (DPBackTracking_ const& copy);
1013
1020
1027 Assignment_ const& getSolution() const;
1028
1033 bool hasMoreSolutions() const;
1034
1040
1046
1047 void clear();
1048
1050 {
1051 bags_->push_back(node);
1052 }
1053
1055 {
1056 }
1057
1059 {
1060 }
1061
1062 protected:
1063
1068 {
1072 bool operator () (BackTrackingState_ const * left, BackTrackingState_ const * right) const;
1073 };
1074
1081
1086
1091 std::multiset<BackTrackingState_*, StateComparator_> queue_;
1092
1097
1102 std::vector<MolecularGraphTraits::EdgeType> const* bonds_;
1103
1107 boost::shared_ptr<std::vector<TreeDecompositionBag> > bags_;
1108
1114
1119
1124
1125 typedef vector<TreeDecompositionBag> BagVector;
1126
1131
1136
1143
1157 DPTable_& leftTable, DPTable_& rightTable);
1158
1167
1176
1183
1192
1198
1208 DPConfig_& antecessor, MolecularGraphTraits::VertexType forgotten_vertex);
1209
1217 void extendState(BackTrackingState_& state, DPConfig_ const& antecessor, Penalty additional_penalty);
1218
1225 void branchState(BackTrackingState_& state, TreeDecompositionBag const& child, DPConfig_ const& antecessor);
1226
1227 };
1228
1241 {
1242 public:
1248 DPBackTrackingCombiner_(std::vector<FPTBondOrderAssignment_*>& bond_assignments,
1249 Size solution_number, Penalty upper_bound = infinite_penalty);
1250
1255
1260
1261 void clear();
1262
1267
1271 bool hasMoreSolutions() const;
1272
1278
1283
1287 Assignment_ const& getSolution() const;
1288
1294
1299 std::vector<MolecularGraphTraits::EdgeType> sorted_edges;
1300
1301 protected:
1305 std::vector<DPBackTracking_*> backtrackers_;
1306
1312 std::priority_queue<Assignment_, std::vector<Assignment_>, std::greater<Assignment_> > priority_queue_;
1313
1318 std::vector<std::vector<Assignment_> > component_solutions_;
1319
1324
1329
1334
1339
1344 std::pair<Size, Penalty> getNextMinimumBackTracker_() const;
1345
1351 void applyAssignment_(Size backtracker_index, Size solution_index);
1352
1357
1363
1367 std::vector<DPBackTracking_*> deepCopyOfBacktrackers_() const;
1368
1369 };
1370
1371
1374
1377
1381 std::vector<int> const* penalties_;
1382
1386 std::vector<Position> const * block_to_start_idx_;
1387
1391 std::vector<Size> const * block_to_length_;
1392
1396 std::vector<int> const * block_to_start_valence_;
1397
1401 std::vector<std::vector<int> > const* atom_to_block_;
1402
1407 boost::shared_ptr<ComputingData_> computing_data_;
1408
1412 boost::shared_ptr<DPBackTrackingCombiner_> combiner_;
1413 };
1414}
1415#endif // BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H
BALL_EXPORT AtomList atoms(const AtomContainer &fragment, const String &expression=String())
Definition: constants.h:13
BALL_EXPORT bool operator<(const String &s1, const String &s2)
BALL_EXPORT bool operator>(const String &s1, const String &s2)
BALL_EXPORT bool operator==(const String &s1, const String &s2)
BALL_EXPORT bool operator>=(const String &s1, const String &s2)
BALL_EXPORT BondList bonds(const AtomContainer &fragment, bool selected_only=false)
BALL_EXPORT bool operator<=(const String &s1, const String &s2)
boost::graph_traits< Graph >::vertex_descriptor VertexType
boost::graph_traits< Graph >::edge_descriptor EdgeType
std::set< OriginalVertexType > TreeDecompositionContent
Definition: treeWidth.h:99
boost::graph_traits< TreeDecompositionGraph >::vertex_descriptor TreeDecompositionBag
Definition: treeWidth.h:107
boost::graph_as_tree< TreeDecompositionGraph, TreeDecompositionParentMap > TreeDecomposition
Definition: treeWidth.h:112
Assignment of bond orders from topology information.
Base class for bond order assignment algorithms.
GRAPH::GraphTraits< MolecularGraph >::VertexType VertexType
static const Penalty infinite_penalty
virtual void setDefaultOptions()
static bool compareTablePointerEntries_(DPPointerRow_ const &left, DPPointerRow_ const &right)
std::multimap< DPConfig_ const *, Penalty, DPJoinMapComparator_ > DPJoinMap_
std::vector< std::vector< int > > const * atom_to_block_
void initPenaltyData_()
Initialize pointers to penalty data.
TreeWidth< MolecularGraph >::TreeDecomposition TreeDecomposition
std::pair< DPTable_::const_iterator, DPTable_::const_iterator > DPPairIt_
GRAPH::GraphTraits< MolecularGraph >::EdgeType Edge
std::vector< int > const * penalties_
std::map< DPConfig_, Penalty > DPMap_
std::vector< int > const * block_to_start_valence_
boost::shared_ptr< DPBackTrackingCombiner_ > combiner_
TreeWidth< MolecularGraph >::TreeDecompositionBag TreeDecompositionBag
std::pair< DPConfig_ *, Penalty > DPPointerRow_
boost::shared_ptr< ComputingData_ > computing_data_
std::pair< boost::reference_wrapper< DPConfig_ >, Penalty > DPRow_
FPTBondOrderStrategy(AssignBondOrderProcessor *parent)
virtual bool readOptions(const Options &options)
static const Valence max_valence
Penalty getPenaltyFor_(MolecularGraphTraits::VertexType vertex, Valence valence) const
Return penalty value for given vertex and valence.
virtual boost::shared_ptr< BondOrderAssignment > computeNextSolution()
std::pair< boost::reference_wrapper< DPConfig_ const >, Penalty > DPConstRow_
static bool compareJoinTablePairs_(DPPairIt_ const &left, DPPairIt_ const &right)
std::vector< Position > const * block_to_start_idx_
std::vector< Size > const * block_to_length_
DPConfig_ & operator=(DPConfig_ const &copy)
DPConfig_(Size atoms, Size bonds)
DPConfig_(ValenceIterator vit, ValenceIterator vend, BondIterator boit, BondIterator boend)
int compare(DPConfig_ const &other) const
DPConfig_(std::vector< Valence > const &v, std::vector< BondOrder > const &bo)
bool insert(DPConfig_ const &config, Penalty penalty)
DPTable_(DPTable_ const &table)
Penalty operator[](DPConfig_ const &config) const
std::vector< MolecularGraphTraits::EdgeType > bonds
AdditionalBagProperties_(AdditionalBagProperties_ const &copy)
AdditionalBagProperties_ & operator=(AdditionalBagProperties_ const &copy)
std::vector< MolecularGraphTraits::EdgeType > getBondsInBag(TreeDecompositionBag &bag)
void computeJoinBag(TreeDecompositionBag &bag, DPTable_ &leftChild, DPTable_ &rightChild, AdditionalBagProperties_ &bag_properties)
void computeIntroduceBag(TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &bag_properties)
FPTBondOrderAssignment_(FPTBondOrderStrategy &parent, boost::shared_ptr< TreeDecomposition > &ntd, Penalty upper_bound=infinite_penalty)
void computeRootBag(TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &bag_properties)
Penalty forgetInnerVertexIn(TreeDecompositionBag &bag, DPConstRow_ child_row, DPConfig_ &entry, std::vector< MolecularGraphTraits::EdgeType > &child_bonds, Size forgotten_index)
void computeForgetBag(TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &property)
void computeLeafIntroduceBag(AdditionalBagProperties_ &bag_properties)
boost::shared_ptr< TreeWidth< MolecularGraph > > tw
vector< FPTBondOrderAssignment_ * > bond_assignments
bool isValid(MolecularGraph &molecule, FPTBondOrderStrategy &parent)
Assignment_ & operator=(Assignment_ const &copy)
Assignment_(Assignment_ const &copy)
void combine(Assignment_ const &other)
std::vector< BondOrder > const & getBondOrders() const
int compare(Assignment_ const &a) const
Assignment_(std::vector< BondOrder > const &bonds, Penalty penalty)
int compare(DPConfig_ const *leftp, DPConfig_ const *rightp) const
GRAPH::GraphTraits< MolecularGraph >::EdgeType Edge
int compare(BackTrackingState_ const &other) const
BackTrackingState_ & operator=(BackTrackingState_ const &other)
std::stack< std::pair< DPConfig_, Size > > join_branches
BackTrackingState_(BackTrackingState_ const &other)
std::vector< MolecularGraphTraits::EdgeType > const * bonds_
DPBackTracking_(DPBackTracking_ const &copy)
Size bondIndexFor(MolecularGraphTraits::EdgeType bond) const
void extendState(BackTrackingState_ &state, DPConfig_ const &antecessor, Penalty additional_penalty)
void preorder(TreeDecompositionBag node, TreeDecomposition &)
boost::shared_ptr< std::vector< TreeDecompositionBag > > bags_
TreeWidth< MolecularGraph >::TreeDecompositionContent TreeDecompositionContent
TreeWidth< MolecularGraph >::TreeDecompositionBag TreeDecompositionBag
std::multiset< BackTrackingState_ *, StateComparator_ > queue_
void remember(BackTrackingState_ &state)
Assignment_ const & getSolution() const
void visitForget(BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &table)
void visitIntroduce(BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &table)
void inorder(TreeDecompositionBag, TreeDecomposition &)
void visitJoin(BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &leftTable, DPTable_ &rightTable)
void setStateAssignment(BackTrackingState_ &state, TreeDecompositionBag &bag, DPConfig_ &antecessor, MolecularGraphTraits::VertexType forgotten_vertex)
AdditionalBagProperties_ & getProperties(Size order)
DPBackTracking_(FPTBondOrderAssignment_ &bond_assignment, Size max_number_of_solutions, std::vector< MolecularGraphTraits::EdgeType > const &bonds, Penalty upperbound=infinite_penalty)
TreeWidth< MolecularGraph >::TreeDecomposition TreeDecomposition
void branchState(BackTrackingState_ &state, TreeDecompositionBag const &child, DPConfig_ const &antecessor)
void postorder(TreeDecompositionBag, TreeDecomposition &)
void visitLeaf(BackTrackingState_ &state)
DPBackTrackingCombiner_(DPBackTrackingCombiner_ const &copy)
std::vector< std::vector< Assignment_ > > component_solutions_
std::vector< MolecularGraphTraits::EdgeType > sorted_edges
std::priority_queue< Assignment_, std::vector< Assignment_ >, std::greater< Assignment_ > > priority_queue_
DPBackTrackingCombiner_(std::vector< FPTBondOrderAssignment_ * > &bond_assignments, Size solution_number, Penalty upper_bound=infinite_penalty)
std::pair< Size, Penalty > getNextMinimumBackTracker_() const
std::vector< DPBackTracking_ * > deepCopyOfBacktrackers_() const
void applyAssignment_(Size backtracker_index, Size solution_index)
#define BALL_EXPORT
Definition: COMMON/global.h:50