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

`#include <BALL/STRUCTURE/BONDORDERS/FPTBondOrderStrategy.h>`

## Classes

struct | StateComparator_

## Public Types

typedef TreeWidth< MolecularGraph >::TreeDecomposition | TreeDecomposition
typedef TreeWidth< MolecularGraph >::TreeDecompositionBag | TreeDecompositionBag
typedef TreeWidth< MolecularGraph >::TreeDecompositionContent | TreeDecompositionContent

## Public Member Functions

| DPBackTracking_ (FPTBondOrderAssignment_ &bond_assignment, Size max_number_of_solutions, std::vector< MolecularGraphTraits::EdgeType > const &bonds, Penalty upperbound=infinite_penalty)
| DPBackTracking_ (DPBackTracking_ const &copy)
| ~DPBackTracking_ ()
DPBackTracking_ & | operator= (DPBackTracking_ const &copy)
Assignment_ & | getSolution ()
Assignment_ const & | getSolution () const
bool | hasMoreSolutions () const
void | nextSolution ()
Penalty | penaltyOfNextSolution () const
void | clear ()
void | preorder (TreeDecompositionBag node, TreeDecomposition &)
void | inorder (TreeDecompositionBag, TreeDecomposition &)
void | postorder (TreeDecompositionBag, TreeDecomposition &)

## Protected Types

typedef vector< TreeDecompositionBag > | BagVector

## Protected Member Functions

DPTable_ & | getTable (Size order)
AdditionalBagProperties_ & | getProperties (Size order)
void | visitLeaf (BackTrackingState_ &state)
void | visitJoin (BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &leftTable, DPTable_ &rightTable)
void | visitForget (BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &table)
void | visitIntroduce (BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &table)
Size | bondIndexFor (MolecularGraphTraits::EdgeType bond) const
void | remember (BackTrackingState_ &state)
bool | isSolutionNeeded (Penalty penalty)
void | setStateAssignment (BackTrackingState_ &state, TreeDecompositionBag &bag, DPConfig_ &antecessor, MolecularGraphTraits::VertexType forgotten_vertex)
void | extendState (BackTrackingState_ &state, DPConfig_ const &antecessor, Penalty additional_penalty)
void | branchState (BackTrackingState_ &state, TreeDecompositionBag const &child, DPConfig_ const &antecessor)

## Protected Attributes

FPTBondOrderAssignment_ * | bond_assignment_
BackTrackingState_ * | current_state_
std::multiset< BackTrackingState_ *, StateComparator_ > | queue_
Size | max_num_solutions_
std::vector< MolecularGraphTraits::EdgeType > const * | bonds_
boost::shared_ptr< std::vector< TreeDecompositionBag > > | bags_
Size | max_heap_size_
Size | num_computed_solutions_
Penalty | upper_bound_

## Detailed Description

The backtracking algorithm. It traverses the nice tree decomposition in pre-order and chooses from the next table the entry, which was used to computed the previous one. We call a table entry successor, if we choosed it in the previous backtracking step. And we call a table entry antecessor, if it was used in the bond assignment algorithm to compute the successor. The backtracking starts in the root vertex which has just one table entry which becomes the first successor. The antecessor entry is gotten by finding the entry of the root's child bag, which can be used to compute the table entry in the root bag. This entry is used as successor for the next table. Often more than one table entry can be used to compute the successor entry. If we don't look at the penalty, there are even more possible antecessor entries. In each step the algorithm uses any antecessor, which computes the successor with the correct penalty. The other possible antecessors are inserted into a priority queue. After finding the successor of the last vertex in the tree, we can get the assignment by insert all bond values of the forgotten bonds in the choosed antecessor entries of visited forgot bags. Furthermore we can backtrack the next best solution by picking up the best antecessor in our priority queue and continue the backtracking with this entry as new successor. Remark that it's easy to get the penalty of the next solution (because we just have to look into the penalty of the antecessor entry). Just the computing of the bond order requires to traverse the whole tree. Furthermore if we don't specify an upperbound, this backtracking algorithm can iterate about EACH possible solution of this bond order problem.

Definition at line 979 of file FPTBondOrderStrategy.h.

## Member Typedef Documentation

## BagVector

typedef vector<TreeDecompositionBag> BALL::FPTBondOrderStrategy::DPBackTracking_::BagVector

protected

Definition at line 1125 of file FPTBondOrderStrategy.h.

## TreeDecomposition

typedef TreeWidth<MolecularGraph>::TreeDecomposition BALL::FPTBondOrderStrategy::DPBackTracking_::TreeDecomposition

Definition at line 982 of file FPTBondOrderStrategy.h.

## TreeDecompositionBag

typedef TreeWidth<MolecularGraph>::TreeDecompositionBag BALL::FPTBondOrderStrategy::DPBackTracking_::TreeDecompositionBag

Definition at line 983 of file FPTBondOrderStrategy.h.

## TreeDecompositionContent

typedef TreeWidth<MolecularGraph>::TreeDecompositionContent BALL::FPTBondOrderStrategy::DPBackTracking_::TreeDecompositionContent

Definition at line 984 of file FPTBondOrderStrategy.h.

## Constructor & Destructor Documentation

## DPBackTracking_() [1/2]

BALL::FPTBondOrderStrategy::DPBackTracking_::DPBackTracking_ | ( | FPTBondOrderAssignment_ & | bond_assignment,
|  | Size | max_number_of_solutions,
|  | std::vector< MolecularGraphTraits::EdgeType > const & | bonds,
|  | Penalty | upperbound = infinite_penalty )

Construct a new DPBackTracking_ for a given FPTBondOrder algorithm, which backtracks not more than maxNumberOfSolutions. By default, the backtracking backtracks only the optimal solution. You have to call the FPTBondOrder#compute method before constructing the DPBackTracking_. Furthermore you should take care to delete the DPBackTracking_ before the FPTBondOrder, because this class operates on a pointer to the bond assignment algorithm, not on a copy.

Parameters

  bondAssignment | a reference to a FPTBondOrder which is already computed
  maxNumberOfSolutions | the number of solutions you want to backtrack. Is by default 1. The size of the priority queue can never be greater than maxNumberOfSolutions

## DPBackTracking_() [2/2]

BALL::FPTBondOrderStrategy::DPBackTracking_::DPBackTracking_ | ( | DPBackTracking_ const & | copy | ) |

Copy constructor

## ~DPBackTracking_()

BALL::FPTBondOrderStrategy::DPBackTracking_::~DPBackTracking_ | ( |  | ) |

Destructor. Removes just the BackTrackingStates, not the bond assignment algorithm instance.

## Member Function Documentation

## bondIndexFor()

Size BALL::FPTBondOrderStrategy::DPBackTracking_::bondIndexFor | ( | MolecularGraphTraits::EdgeType | bond | ) | const

protected

searchs the index of this bond in the assignment array. Because there is a strict ordering of bonds, this search is computed as binary search in logarithmic time.

## branchState()

void BALL::FPTBondOrderStrategy::DPBackTracking_::branchState | ( | BackTrackingState_ & | state,
|  | TreeDecompositionBag const & | child,
|  | DPConfig_ const & | antecessor )

protected

Remember the choosed entry of the right child's table by adding it into the joinBranch stack.

Parameters

  state | the backtracking state
  child | the right child of the join bag
  antecessor | the choosed entry in the right child's table

## clear()

void BALL::FPTBondOrderStrategy::DPBackTracking_::clear | ( |  | ) |

## extendState()

void BALL::FPTBondOrderStrategy::DPBackTracking_::extendState | ( | BackTrackingState_ & | state,
|  | DPConfig_ const & | antecessor,
|  | Penalty | additional_penalty )

protected

Make the antecessor entry to the new successor entry of the given state and adding the penalty

Parameters

  state | the backtracking state
  antecessor | the choosed entry which becomes the new successor
  additionalPenalty | the penalty which is added to the best previous solution for choosing this antecessor

## getProperties()

AdditionalBagProperties_ & BALL::FPTBondOrderStrategy::DPBackTracking_::getProperties | ( | Size | order | ) |

protected

returns the bag properties of the bag with the given pre-order index

## getSolution() [1/2]

Assignment_ & BALL::FPTBondOrderStrategy::DPBackTracking_::getSolution | ( |  | ) |

returns the current solution. Remark that after constructing the backtracking, there is no solution computed. So you have to call nextSolution first.

Exceptions

  BALL::Exception::NullPointer | if you forgot to call nextSolution

## getSolution() [2/2]

Assignment_ const & BALL::FPTBondOrderStrategy::DPBackTracking_::getSolution | ( |  | ) | const

returns the current solution, const version. Remark that after constructing the backtracking, there is no solution computed. So you have to call nextSolution first.

Exceptions

  BALL::Exception::NullPointer | if you forgot to call nextSolution

## getTable()

DPTable_ & BALL::FPTBondOrderStrategy::DPBackTracking_::getTable | ( | Size | order | ) |

protected

returns the dynamic programming table of the bag with the given pre-order index

## hasMoreSolutions()

bool BALL::FPTBondOrderStrategy::DPBackTracking_::hasMoreSolutions | ( |  | ) | const

returns true if there is another solution. Call this method before calling nextSolution.

## inorder()

void BALL::FPTBondOrderStrategy::DPBackTracking_::inorder | ( | TreeDecompositionBag | ,
|  | TreeDecomposition & | )

inline

Definition at line 1054 of file FPTBondOrderStrategy.h.

## isSolutionNeeded()

bool BALL::FPTBondOrderStrategy::DPBackTracking_::isSolutionNeeded | ( | Penalty | penalty | ) |

protected

Checks if the penalty of this solution is good enough for backtracking. This happens if the penalty is better than the upperbound

## nextSolution()

void BALL::FPTBondOrderStrategy::DPBackTracking_::nextSolution | ( |  | ) |

Computes the next best solution. You can access it by calling getSolution.

Exceptions

  BALL::Exception::OutOfRange | if there are no more solutions

## operator=()

DPBackTracking_ & BALL::FPTBondOrderStrategy::DPBackTracking_::operator= | ( | DPBackTracking_ const & | copy | ) |

Assignment operator

## penaltyOfNextSolution()

Penalty BALL::FPTBondOrderStrategy::DPBackTracking_::penaltyOfNextSolution | ( |  | ) | const

returns the penalty of the next best solution. If there are no more solutions, this function returns infinite_penalty.

## postorder()

void BALL::FPTBondOrderStrategy::DPBackTracking_::postorder | ( | TreeDecompositionBag | ,
|  | TreeDecomposition & | )

inline

Definition at line 1058 of file FPTBondOrderStrategy.h.

## preorder()

void BALL::FPTBondOrderStrategy::DPBackTracking_::preorder | ( | TreeDecompositionBag | node,
|  | TreeDecomposition & | )

inline

Definition at line 1049 of file FPTBondOrderStrategy.h.

## remember()

void BALL::FPTBondOrderStrategy::DPBackTracking_::remember | ( | BackTrackingState_ & | state | ) |

protected

remembers the given state as another possible solution with higher penalty. The state is inserted in the queue. If the algorithm found enough solutions, it updates the upperbound to the worst solution in the queue. So just solutions with better penalty are inserted into the queue.

Parameters

  state | an alternative antecessor which has a greater or equal penalty than the choosed one

## setStateAssignment()

void BALL::FPTBondOrderStrategy::DPBackTracking_::setStateAssignment | ( | BackTrackingState_ & | state,
|  | TreeDecompositionBag & | bag,
|  | DPConfig_ & | antecessor,
|  | MolecularGraphTraits::VertexType | forgotten_vertex )

protected

Is called by visitForget. It writes the values of all forgotten bonds into the state's assignment.

Parameters

  state | the current state
  bag | the forget bag
  antecessor | the choosed entry in the bag's child bag
  forgottenVertex | the vertex which is forgotten in the forget bag

## visitForget()

void BALL::FPTBondOrderStrategy::DPBackTracking_::visitForget | ( | BackTrackingState_ & | state,
|  | TreeDecompositionBag & | bag,
|  | DPTable_ & | table )

protected

search the antecessor of this forget node. This is the entry which is equal to the successor after forgetting the forget-vertex and it's incident bonds.

Parameters

  state | the current backtracking state
  bag | the forget bag with the successor entry
  table | the child's table with the antecessor entry

## visitIntroduce()

void BALL::FPTBondOrderStrategy::DPBackTracking_::visitIntroduce | ( | BackTrackingState_ & | state,
|  | TreeDecompositionBag & | bag,
|  | DPTable_ & | table )

protected

search antecessor of this introduce node. This is the same entry as the successor, but without the introduced columns

Parameters

  state | the current backtracking state
  bag | the introduce bag with the successor entry
  table | the child's table with the antecessor entry

## visitJoin()

void BALL::FPTBondOrderStrategy::DPBackTracking_::visitJoin | ( | BackTrackingState_ & | state,
|  | TreeDecompositionBag & | bag,
|  | DPTable_ & | leftTable,
|  | DPTable_ & | rightTable )

protected

search the both antecessors of this join node. This is the pair of entries, which bond values are the same as the successor's bond values and which sum of consumed valences are the same as the successor's consumed valences. The best left entry becomes the new current state. The right entry is pushed on top of the state's join branch stack. Other possible pairs of antecessors are inserted into the priority queue

Parameters

  state | the current backtracking state
  bag | the join bag with the successor entry
  leftTable | the table of the first child
  rightTable | the table of the second child

## visitLeaf()

void BALL::FPTBondOrderStrategy::DPBackTracking_::visitLeaf | ( | BackTrackingState_ & | state | ) |

protected

Leaf-Nodes have no antecessors. So either the computing is finished, or there is an unfinished join node in join branch stack which has to be computed next.

## Member Data Documentation

## bags_

boost::shared_ptr<std::vector<TreeDecompositionBag> > BALL::FPTBondOrderStrategy::DPBackTracking_::bags_

protected

The nice tree decomposition bags in pre-order

Definition at line 1107 of file FPTBondOrderStrategy.h.

## bond_assignment_

FPTBondOrderAssignment_* BALL::FPTBondOrderStrategy::DPBackTracking_::bond_assignment_

protected

The instance of the FPTBondOrder algorithm, which gives access to the computed tables and the nice tree decomposition. This class doesn't make a copy of the bondAssignment, so take care that the bondAssignment isn't deleted before the instance of this class.

Definition at line 1080 of file FPTBondOrderStrategy.h.

## bonds_

std::vector<MolecularGraphTraits::EdgeType> const* BALL::FPTBondOrderStrategy::DPBackTracking_::bonds_

protected

A sorted vector of the edges of the graph. The bond values in the assignments are in the same order as the edges in this vector.

Definition at line 1102 of file FPTBondOrderStrategy.h.

## current_state_

BackTrackingState_* BALL::FPTBondOrderStrategy::DPBackTracking_::current_state_

protected

The current state of the backtracking. Each other state is in the priority queue

Definition at line 1085 of file FPTBondOrderStrategy.h.

## max_heap_size_

Size BALL::FPTBondOrderStrategy::DPBackTracking_::max_heap_size_

protected

maxHeapSize is the maxNumberOfSolutions - the number of backtracked solutions. So this attribute contains the current number of solutions we want to backtrack.

Definition at line 1113 of file FPTBondOrderStrategy.h.

## max_num_solutions_

Size BALL::FPTBondOrderStrategy::DPBackTracking_::max_num_solutions_

protected

the maximum number of solutions we want do backtrack.

Definition at line 1096 of file FPTBondOrderStrategy.h.

## num_computed_solutions_

Size BALL::FPTBondOrderStrategy::DPBackTracking_::num_computed_solutions_

protected

The number of solutions produced so far.

Definition at line 1118 of file FPTBondOrderStrategy.h.

## queue_

std::multiset<BackTrackingState_*, StateComparator_> BALL::FPTBondOrderStrategy::DPBackTracking_::queue_

protected

priority queue for backtracking states. It is implemented as search tree, because we need also access to the worst element (to limit the queues size).

Definition at line 1091 of file FPTBondOrderStrategy.h.

## upper_bound_

Penalty BALL::FPTBondOrderStrategy::DPBackTracking_::upper_bound_

protected

current upperbound. This algorithm will just iterate solutions which are better than this upperbound;

Definition at line 1123 of file FPTBondOrderStrategy.h.