|
BALL
1.4.79
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
|
BALL
1.4.79
|
#include <BALL/STRUCTURE/BONDORDERS/FPTBondOrderStrategy.h>
Public Member Functions | |
| FPTBondOrderAssignment_ (FPTBondOrderStrategy &parent, boost::shared_ptr< TreeDecomposition > &ntd, Penalty upper_bound=infinite_penalty) | |
| ~FPTBondOrderAssignment_ () | |
| Penalty | compute () |
Protected Member Functions | |
| DPTable_ * | operator() (TreeDecompositionBag &bag, std::vector< DPTable_ * >::const_iterator begin, std::vector< DPTable_ * >::const_iterator end) |
| std::vector < MolecularGraphTraits::EdgeType > | getBondsInBag (TreeDecompositionBag &bag) |
| void | computeLeafIntroduceBag (AdditionalBagProperties_ &bag_properties) |
| void | computeIntroduceBag (TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &bag_properties) |
| void | computeForgetBag (TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &property) |
| void | computeJoinBag (TreeDecompositionBag &bag, DPTable_ &leftChild, DPTable_ &rightChild, AdditionalBagProperties_ &bag_properties) |
| 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) |
Protected Attributes | |
| FPTBondOrderStrategy * | parent_ |
| MolecularGraph * | molecule_ |
| boost::shared_ptr < TreeDecomposition > | ntd_ |
| vector< AdditionalBagProperties_ > | properties_ |
| Penalty | upper_bound_ |
| BondOrder | max_bond_order_ |
| Valence | max_valence_ |
Friends | |
| class | DPBackTracking_ |
| class | DPBackTrackingCombiner_ |
| class | GRAPH::PostOrderFolding< TreeDecomposition, TreeDecompositionBag, DPTable_ *, FPTBondOrderAssignment_ > |
bond assignment algorithm. Traverse in post-order the nice tree decomposition and computes the dynamic programming table for each vertex This class uses a pointer to a graph, to a penalty map and to a nice tree decomposition. So you should take care that all three objects aren't deleted during this algorithm, because this class neither uses shared pointers, nor make copies of the objects.
Definition at line 478 of file FPTBondOrderStrategy.h.
| BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::FPTBondOrderAssignment_ | ( | FPTBondOrderStrategy & | parent, |
| boost::shared_ptr< TreeDecomposition > & | ntd, | ||
| Penalty | upper_bound = infinite_penalty |
||
| ) |
Construct a new FPTBondOrder with the given molecule, a PenaltyMap and a built nice tree decomposition
| parent | the bond order assignment algorithm |
| ntd | a nice tree decomposition of the graph |
| upperbound | the algorithm will only compute solutions which are better than the upperbound. By default the upperbound is infinity. |
| BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::~FPTBondOrderAssignment_ | ( | ) |
Destructor. Just delete the AdditionalBagProperties_, which were computed during this algorithm. So don't delete this instance before backtracking. Furthermore this destructor doesn't delete the nice tree decomposition and the penalty map. You have to take care for this yourself.
| Penalty BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::compute | ( | ) |
Call this to start the bond assignment computing. This function returns the optimal penalty for the graph. If you want to know the bond order assignment or the penalties of other solutions, you have to start the backtracking by DPBackTracking.
|
protected |
computes the dynamic programming table for a given forget node. This is done by removing the columns of each bond which is incident to the forget node. It's bond value (+1) is added to the consumed valence of the both incident atoms. After this, the forget-atom is removed itself and the penalty for its valences is added to the penalty of the table entry. If multiple entries have the same bond and valence values, just the entry with the lowest penalty is kept. So this operation removes many entries from the table. This is important, because introduce nodes insert many entries in the table. So during the algorithm the tables doesn't grow very much, because there is a sucession of forgetting table entries and introducing new table entries. The complexity of forgetting a vertex is linear in O(number of bonds + number of atoms + PenaltyMap lookup). This is done for each table entry. Furthermore there comes a lookup cost for finding duplicate entries in the table which is done in O(log(number of entries) * (number of bonds + number of atoms)), because the table is implemented as search tree.
|
protected |
computes the dynamic programming table for a given introduce node. This is done by insert a new column for the introduced vertex in each entry, filled with the value 0. If the bag introduces new bonds, each entry is duplicated for each possible bond value. Then new bond order columns are inserted into the entries, filled with the different possible combinations of bond values. So at the end of this function, the bag contains each possible bond order combination of the introduced bonds. This could be very heavy, but usually we have never more than two or three bonds in a bag. So the complexity of this operation is O([number of bond values]^[number of introduced bonds] * [number of table entries] * insertion-costs), where insertion-costs are logarithmic, because the table is implemented as search tree.
|
protected |
computes the dynamic programming table for a given join node. The child bags of a join node contains the same vertices and bonds as the join bag itself. So the table of the join bag is computed by merging the tables of the both childs. This is done by finding each pair of table entries from first and second child, which have the same bond values but - maybe - different penalties and valence values. The valence values and penalties of this pairs are added and the merged entry is inserted in the table of the join node. Again, entries with the same values but greater penalty than other one are removed from the table. To avoid quadratic complexity by finding pairs, the table entries are inserted into a search tree which compares just the bond values of its keys. So just the entries with the same bond values are combined, which is quadratic in worst case, too. But usually the number of entries in the table is not so huge, because the forget bags remove many entries which can not have better solutions than the kept one.
|
protected |
computes the dynamic programming table for a given leaf node. This is done by filling an entry with just one valence-entry (with value 0) into the table. So the complexity of this operation is constant.
| bagProperties | contains the dynamic programming table |
|
protected |
computes the dynamic programming table for a given root node. A root bag is nothing more than a forget bag, so this operations does the same as the computeForgetBag function.
|
protected |
delete the column of the forgotten vertex and it's incident bonds in a given table entry. Sum the bond values of the forgotten bonds to the valence values of their incident non-forgotten vertices. This function is reused in DPBackTracking and is called in the computeForgetBag function.
|
protected |
Remember which bond belonging to the given bag. Because this information is reused in backtracking, the bonds are saved in the AdditionalBagProperties_ object.
| bag | the bag of the nice tree decomposition |
|
protected |
Compute the dynamic programming table for a given bag. On this time, the dynamic programming tables of all vertices of the subtree, rooted by this bag, should are computed. This function shouldn't be called directly. Instead use the compute function.
| bag | the bag which is visited during the tree traversal |
| type | the type of this bag. Isn't used because the bag gives also access to it's bag type |
| begin | an iterator to the first computed child-table of this bag. For join-nodes there are two childs, leaf nodes have no childs. All other vertices have one child. |
| end | an iterator the end of the computed child-tables of this bag |
| BALL::Exception::IllegalTreeOperation | if the nice tree decomposition is damaged |
|
friend |
Definition at line 481 of file FPTBondOrderStrategy.h.
|
friend |
Definition at line 482 of file FPTBondOrderStrategy.h.
|
friend |
Definition at line 483 of file FPTBondOrderStrategy.h.
|
protected |
The maximum value which can be assigned to a bond
Definition at line 543 of file FPTBondOrderStrategy.h.
|
protected |
The maximum valence which can be assigned to an atom
Definition at line 548 of file FPTBondOrderStrategy.h.
|
protected |
the graph with the bonds, which were assigned to a bond value during this algorithm
Definition at line 518 of file FPTBondOrderStrategy.h.
|
protected |
The nice tree decomposition which is built from the graph
Definition at line 523 of file FPTBondOrderStrategy.h.
|
protected |
A pointer to our parent
Definition at line 513 of file FPTBondOrderStrategy.h.
|
protected |
A vector of AdditionalBagProperties_. Contains the bonds and the dynamic programming tables for each vertex in the nice tree decomposition
Definition at line 529 of file FPTBondOrderStrategy.h.
|
protected |
The algorithm will just compute solutions which are better than the upperbound (they have to be BETTER, not equal, so "upperbound" is maybe not the best word for it). The upperbound is infinite_penalty by default, but you can change this if you know that your molecule has a better solution. This can improve the performance - but usually the algorithm is fast enough to compute without an upperbound.
Definition at line 538 of file FPTBondOrderStrategy.h.
1.8.7