BALL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines
Classes | Public Types | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes
BALL::FPTBondOrderStrategy::DPBackTracking_ Class Reference

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

List of all members.

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_
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 983 of file FPTBondOrderStrategy.h.


Member Typedef Documentation

Definition at line 1124 of file FPTBondOrderStrategy.h.

Definition at line 986 of file FPTBondOrderStrategy.h.

Definition at line 987 of file FPTBondOrderStrategy.h.

Definition at line 988 of file FPTBondOrderStrategy.h.


Constructor & Destructor Documentation

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:
bondAssignmenta reference to a FPTBondOrder which is already computed
maxNumberOfSolutionsthe number of solutions you want to backtrack. Is by default 1. The size of the priority queue can never be greater than maxNumberOfSolutions

Copy constructor

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


Member Function Documentation

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.

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:
statethe backtracking state
childthe right child of the join bag
antecessorthe choosed entry in the right child's table
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:
statethe backtracking state
antecessorthe choosed entry which becomes the new successor
additionalPenaltythe penalty which is added to the best previous solution for choosing this antecessor

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

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::NullPointerif you forgot to call nextSolution

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::NullPointerif you forgot to call nextSolution

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

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

Definition at line 1058 of file FPTBondOrderStrategy.h.

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

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

Exceptions:
BALL::Exception::OutOfRangeif there are no more solutions
DPBackTracking_& BALL::FPTBondOrderStrategy::DPBackTracking_::operator= ( DPBackTracking_ const &  copy)

Assignment operator

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

Definition at line 1062 of file FPTBondOrderStrategy.h.

Definition at line 1053 of file FPTBondOrderStrategy.h.

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:
statean alternative antecessor which has a greater or equal penalty than the choosed one

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

Parameters:
statethe current state
bagthe forget bag
antecessorthe choosed entry in the bag's child bag
forgottenVertexthe vertex which is forgotten in the forget bag

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:
statethe current backtracking state
bagthe forget bag with the successor entry
tablethe child's table with the antecessor entry

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

Parameters:
statethe current backtracking state
bagthe introduce bag with the successor entry
tablethe child's table with the antecessor entry
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:
statethe current backtracking state
bagthe join bag with the successor entry
leftTablethe table of the first child
rightTablethe table of the second child

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

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

The nice tree decomposition bags in pre-order

Definition at line 1111 of file FPTBondOrderStrategy.h.

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 1084 of file FPTBondOrderStrategy.h.

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 1106 of file FPTBondOrderStrategy.h.

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

Definition at line 1089 of file FPTBondOrderStrategy.h.

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 1117 of file FPTBondOrderStrategy.h.

the maximum number of solutions we want do backtrack.

Definition at line 1100 of file FPTBondOrderStrategy.h.

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 1095 of file FPTBondOrderStrategy.h.

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

Definition at line 1122 of file FPTBondOrderStrategy.h.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines