Loading...
Searching...
No Matches
BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_ Class Reference

`#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_ >

## Detailed Description

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.

## Constructor & Destructor Documentation

## FPTBondOrderAssignment_()

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

Parameters

  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.

## ~FPTBondOrderAssignment_()

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.

## Member Function Documentation

## compute()

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.

## computeForgetBag()

void BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::computeForgetBag | ( | TreeDecompositionBag & | bag,
|  | DPTable_ & | child,
|  | AdditionalBagProperties_ & | property )

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.

## computeIntroduceBag()

void BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::computeIntroduceBag | ( | TreeDecompositionBag & | bag,
|  | DPTable_ & | child,
|  | AdditionalBagProperties_ & | bag_properties )

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.

## computeJoinBag()

void BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::computeJoinBag | ( | TreeDecompositionBag & | bag,
|  | DPTable_ & | leftChild,
|  | DPTable_ & | rightChild,
|  | AdditionalBagProperties_ & | bag_properties )

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.

## computeLeafIntroduceBag()

void BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::computeLeafIntroduceBag | ( | AdditionalBagProperties_ & | bag_properties | ) |

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.

Parameters

  bagProperties | contains the dynamic programming table

## computeRootBag()

void BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::computeRootBag | ( | TreeDecompositionBag & | bag,
|  | DPTable_ & | child,
|  | AdditionalBagProperties_ & | bag_properties )

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.

## forgetInnerVertexIn()

Penalty BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::forgetInnerVertexIn | ( | TreeDecompositionBag & | bag,
|  | DPConstRow_ | child_row,
|  | DPConfig_ & | entry,
|  | std::vector< MolecularGraphTraits::EdgeType > & | child_bonds,
|  | Size | forgotten_index )

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.

## getBondsInBag()

std::vector< MolecularGraphTraits::EdgeType > BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::getBondsInBag | ( | TreeDecompositionBag & | bag | ) |

protected

Remember which bond belonging to the given bag. Because this information is reused in backtracking, the bonds are saved in the AdditionalBagProperties_ object.

Parameters

  bag | the bag of the nice tree decomposition

Returns
  a vector of edges which are only incident to vertices in this bag

## operator()()

DPTable_ * BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::operator() | ( | TreeDecompositionBag & | bag,
|  | std::vector< DPTable_ * >::const_iterator | begin,
|  | std::vector< DPTable_ * >::const_iterator | end )

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.

Parameters

  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

Exceptions

  BALL::Exception::IllegalTreeOperation | if the nice tree decomposition is damaged

Returns
  the dynamic programming table for this bag

## Friends And Related Symbol Documentation

## DPBackTracking_

friend class DPBackTracking_

friend

Definition at line 481 of file FPTBondOrderStrategy.h.

## DPBackTrackingCombiner_

friend class DPBackTrackingCombiner_

friend

Definition at line 482 of file FPTBondOrderStrategy.h.

## GRAPH::PostOrderFolding< TreeDecomposition, TreeDecompositionBag, DPTable_ *, FPTBondOrderAssignment_ >

friend class GRAPH::PostOrderFolding< TreeDecomposition, TreeDecompositionBag, DPTable_ *, FPTBondOrderAssignment_ >

friend

Definition at line 482 of file FPTBondOrderStrategy.h.

## Member Data Documentation

## max_bond_order_

BondOrder BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::max_bond_order_

protected

The maximum value which can be assigned to a bond

Definition at line 543 of file FPTBondOrderStrategy.h.

## max_valence_

Valence BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::max_valence_

protected

The maximum valence which can be assigned to an atom

Definition at line 548 of file FPTBondOrderStrategy.h.

## molecule_

MolecularGraph* BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::molecule_

protected

the graph with the bonds, which were assigned to a bond value during this algorithm

Definition at line 518 of file FPTBondOrderStrategy.h.

## ntd_

boost::shared_ptr<TreeDecomposition> BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::ntd_

protected

The nice tree decomposition which is built from the graph

Definition at line 523 of file FPTBondOrderStrategy.h.

## parent_

FPTBondOrderStrategy* BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::parent_

protected

A pointer to our parent

Definition at line 513 of file FPTBondOrderStrategy.h.

## properties_

vector<AdditionalBagProperties_> BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::properties_

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.

## upper_bound_

Penalty BALL::FPTBondOrderStrategy::FPTBondOrderAssignment_::upper_bound_

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.