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

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

protected

Definition at line 1125 of file FPTBondOrderStrategy.h.

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

Definition at line 982 of file FPTBondOrderStrategy.h.

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

Definition at line 983 of file FPTBondOrderStrategy.h.

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

Definition at line 984 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

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

BALL::FPTBondOrderStrategy::DPBackTracking_::DPBackTracking_

(

DPBackTracking_ const &

copy

)

Copy constructor

BALL::FPTBondOrderStrategy::DPBackTracking_::~DPBackTracking_

(

)

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

Member Function Documentation

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.

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

void BALL::FPTBondOrderStrategy::DPBackTracking_::clear

(

)

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

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

protected

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

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

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

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

protected

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

bool BALL::FPTBondOrderStrategy::DPBackTracking_::hasMoreSolutions

(

)

const

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

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

inline

Definition at line 1054 of file FPTBondOrderStrategy.h.

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

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

DPBackTracking_& BALL::FPTBondOrderStrategy::DPBackTracking_::operator=

(

DPBackTracking_ const &

copy

)

Assignment operator

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.

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

inline

Definition at line 1058 of file FPTBondOrderStrategy.h.

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

inline

Definition at line 1049 of file FPTBondOrderStrategy.h.

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

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

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

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

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

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

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.

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.

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.

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.

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.

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.

Size BALL::FPTBondOrderStrategy::DPBackTracking_::num_computed_solutions_

protected

The number of solutions produced so far.

Definition at line 1118 of file FPTBondOrderStrategy.h.

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.

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.