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

Inheritance diagram for BALL::FPTBondOrderStrategy:

Classes
class	AdditionalBagProperties_

class	Assignment_

class	BackTrackingState_

class	ComputingData_

struct	Default
	Default option values. More...

class	DPBackTracking_

class	DPBackTrackingCombiner_

class	DPConfig_

struct	DPJoinMapComparator_

class	DPTable_

class	EdgeComparator_

class	FPTBondOrderAssignment_

struct	Option
	Option names. More...

Public Types
typedef GRAPH::GraphTraits < MolecularGraph >::EdgeType	Edge

typedef GRAPH::GraphTraits < MolecularGraph >::VertexType	VertexType

typedef TreeWidth < MolecularGraph > ::TreeDecomposition	TreeDecomposition

typedef TreeWidth < MolecularGraph > ::TreeDecompositionBag	TreeDecompositionBag

typedef float	Penalty

typedef int	Valence

typedef int	BondOrder

Public Member Functions
	FPTBondOrderStrategy (AssignBondOrderProcessor *parent)

virtual	~FPTBondOrderStrategy ()

virtual void	clear ()

virtual void	init ()

virtual bool	readOptions (const Options &options)

virtual void	setDefaultOptions ()

virtual boost::shared_ptr < BondOrderAssignment >	computeNextSolution ()

Public Member Functions inherited from BALL::BondOrderAssignmentStrategy
	BondOrderAssignmentStrategy (AssignBondOrderProcessor *parent)

Static Public Attributes
Constant Definitions
static const Penalty	infinite_penalty

static const Valence	max_valence

Protected Types
typedef std::pair < boost::reference_wrapper < DPConfig_ >, Penalty >	DPRow_

typedef std::pair < boost::reference_wrapper < DPConfig_ const >, Penalty >	DPConstRow_

typedef std::pair< DPConfig_ *, Penalty >	DPPointerRow_

typedef std::map< DPConfig_, Penalty >	DPMap_

typedef std::pair < DPTable_::const_iterator, DPTable_::const_iterator >	DPPairIt_

typedef std::multimap < DPConfig_ const *, Penalty, DPJoinMapComparator_ >	DPJoinMap_

Protected Member Functions
void	initPenaltyData_ ()
	Initialize pointers to penalty data. More...

Penalty	getPenaltyFor_ (MolecularGraphTraits::VertexType vertex, Valence valence) const
	Return penalty value for given vertex and valence. More...

Static Protected Member Functions
static bool	compareJoinTablePairs_ (DPPairIt_ const &left, DPPairIt_ const &right)

static bool	compareTablePointerEntries_ (DPPointerRow_ const &left, DPPointerRow_ const &right)

Protected Attributes
std::vector< int > const *	penalties_

std::vector< Position > const *	block_to_start_idx_

std::vector< Size > const *	block_to_length_

std::vector< int > const *	block_to_start_valence_

std::vector< std::vector< int > > const *	atom_to_block_

boost::shared_ptr< ComputingData_ >	computing_data_

boost::shared_ptr < DPBackTrackingCombiner_ >	combiner_

Friends
class	FPTBondOrderAssignment_

Additional Inherited Members
Public Attributes inherited from BALL::BondOrderAssignmentStrategy
AssignBondOrderProcessor *	abop
	Our parent processor. More...

Detailed Description

FPT algorithm for bond order assignment.

This class implements a fixed parameter tractability approach for the bond order assignment problem that can be used by the AssignBondOrderProcessor .

It handles the creation of the nice tree decomposition, the bond assignment computing and the backtracking. This class is the only one in the dynamic programming algorithm which expects a molecule. All other classes works with graphs (which doesn't have atoms or bonds, but just vertices and edges). So this class close the gap between the algorithmic bond order problem and it's practical meaning. The most classes of the bond order algorithm doesn't manage their dependencies, so it's important to delete them in the correct order. This class wraps about them and manages the memory of their instances itself. So it's the best to forget, that their are other classes than this: Just use this class if you want to assign bond orders by the dynamic programming algorithm.

The class has a default constructor and can be copied and assigned. It saves it's dynamic programming table and the nice tree decomposition in an extra data structure which is accessed by shared pointers. So you can copy instances of this class without copying all the algorithm data! Nevertheless you have to copy the backtracking combiner and all it's remembered solutions.

After setting the atom container and the penalty map, you have to call the #start method to start the computing. After that, the instance of this class behaves like an Ball iterator (although it doesn't inherited from it and doesn't provide all it's functions). You can iterate about each solution by calling ++, and you can check for further solutions by calling +.

FPTBondOrderStrategy algorithm;
algorithm.setMolecule(someAtomContainer);
algorithm.setPenaltyMap(somePenaltyMap);
algorithm.start();
for (; +algorithm; ++algorithm)
{
 cout << algorithm->penalty;
}

Dereferencing an algorithm instance means: return the result of the last computed solution. The result is an Assignment instance. So it doesn't give information about the concrete bonds, if you don't know their indizes. There are two ways to handle this: You cann call #getBonds to get a vector with pointers to the bonds. The order of the bonds in the vector is the same as the order of the bond values on the assignments. Another way is to call #getBondAssignmentHashMap. This returns a HashMap which maps each bond to it's bond value. This structure is nearly the same as AssignBondOrderProcessor is using, just with the different that the pointers references constant bonds.

An important difference to the AssignBondOrderProcessor is that a bond value of 0 means "single bond", a bond value of 1 means "double bond" and a bond value of 2 "tripple bound". So you have to increase the bond values by 1 if you want to use them in AssignBondOrderProcessor or in the Bond class itself.

Beside the iterator-like functions you can also call the same functions you know from the DPBackTracking and DPBackTrackingCombiner class. But other than DPBackTracking this class computes the best solution after calling #start without the need of calling #nextSolution.

An DPBondAssignmentStrategy instance which hasn't started behaves like an iterator which isn't bound to a container. You can return the instance into this state by calling #reset. Also changing the molecule or penalty map also reset the instance. Calling other methods than #start, #reset, #setMolecule, #getMolecule, #setPenaltyMap, #getPenaltyMap, #setUpperbound, #getUpperbound, #setNumberOfSolutions, #getNumberOfSolutions will throw an InvalidIterator exception if you forget to call #start before.

The DPBondAssignmentStrategy expect that the atom container and the penalty map aren't deleted during the instances' lifetime. If you want do delete one of them, reset the instance and set their atom container and penalty map to NULL.

Definition at line 121 of file FPTBondOrderStrategy.h.

Member Typedef Documentation

typedef int BALL::FPTBondOrderStrategy::BondOrder

The BondOrder type is represented as integer, although it shouldn't exceed a small constant value (typical 3)

Definition at line 148 of file FPTBondOrderStrategy.h.

typedef std::pair<boost::reference_wrapper<DPConfig_ const>, Penalty> BALL::FPTBondOrderStrategy::DPConstRow_

protected

After computing a DPTable, we don't modify it's entries (because we need them for backtracking). So usually we work with const references to the table entries

Definition at line 328 of file FPTBondOrderStrategy.h.

typedef std::multimap<DPConfig_ const*, Penalty, DPJoinMapComparator_> BALL::FPTBondOrderStrategy::DPJoinMap_

protected

A map which remember pointers to DPConfigs of a child of a join-node. It uses a DPJoinMapComparator to find entries with equal bond-values very fast.

Definition at line 958 of file FPTBondOrderStrategy.h.

typedef std::map<DPConfig_, Penalty> BALL::FPTBondOrderStrategy::DPMap_

protected

A map which gives fast access to the penalty of a given DPConfig. Is used to compare the penalty of two DPConfigs or to iterate above all table entries.

Definition at line 341 of file FPTBondOrderStrategy.h.

typedef std::pair<DPTable_::const_iterator, DPTable_::const_iterator> BALL::FPTBondOrderStrategy::DPPairIt_

protected

is used to remember the pair of table entries of the children of a join node without copying their configuration

Definition at line 942 of file FPTBondOrderStrategy.h.

typedef std::pair<DPConfig_*, Penalty> BALL::FPTBondOrderStrategy::DPPointerRow_

protected

Is used to save a reference to a const DPConfig in an object (which isn't possible with references, because they are constant and would prevent it's adding into collections)

Definition at line 335 of file FPTBondOrderStrategy.h.

typedef std::pair<boost::reference_wrapper<DPConfig_>, Penalty> BALL::FPTBondOrderStrategy::DPRow_

protected

A single row in a DPTable, which consists of the DPConfig (valences and bond values) and the penalty, which was computed for the DPConfig and it's ancestors.

Definition at line 322 of file FPTBondOrderStrategy.h.

typedef GRAPH::GraphTraits<MolecularGraph>::EdgeType BALL::FPTBondOrderStrategy::Edge

Definition at line 125 of file FPTBondOrderStrategy.h.

typedef float BALL::FPTBondOrderStrategy::Penalty

Penalties are represented as floats

Definition at line 136 of file FPTBondOrderStrategy.h.

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

Definition at line 128 of file FPTBondOrderStrategy.h.

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

Definition at line 129 of file FPTBondOrderStrategy.h.

typedef int BALL::FPTBondOrderStrategy::Valence

The valence-type for atoms is represented as integer, although it shouldn't exceed a small constant value (typical 8)

Definition at line 142 of file FPTBondOrderStrategy.h.

typedef GRAPH::GraphTraits<MolecularGraph>::VertexType BALL::FPTBondOrderStrategy::VertexType

Definition at line 126 of file FPTBondOrderStrategy.h.

Constructor & Destructor Documentation

BALL::FPTBondOrderStrategy::FPTBondOrderStrategy ( AssignBondOrderProcessor * parent )

virtual BALL::FPTBondOrderStrategy::~FPTBondOrderStrategy ( )

virtual

Destructor. Deletes the backtracking. The nice tree decomposition and the dynamic programming tables are deleted if there are no other FPTBondOrderStrategy instances which access them.

Member Function Documentation

virtual void BALL::FPTBondOrderStrategy::clear ( )

virtual

delete all previous computings and frees the nice tree decomposition and penalty map, if they are not referenced by another FPTBondOrderStrategy. After this method you can not access the solutions. Call #start again to compute the bond order.

Reimplemented from BALL::BondOrderAssignmentStrategy.

static bool BALL::FPTBondOrderStrategy::compareJoinTablePairs_	(	DPPairIt_ const &	left,
		DPPairIt_ const &	right
	)

staticprotected

compare two join-table antecessor pairs by comparing their penalties

static bool BALL::FPTBondOrderStrategy::compareTablePointerEntries_	(	DPPointerRow_ const &	left,
		DPPointerRow_ const &	right
	)

staticprotected

Compare pointers of entries of introduce or forget table antecessors by comparing their penalties

virtual boost::shared_ptr<BondOrderAssignment> BALL::FPTBondOrderStrategy::computeNextSolution ( )

virtual

Backtracks the next best solution. Call #hasNextSolution first to avoid an OutOfRange exception

Exceptions

BALL::Exception::OutOfRange	if there are no more solutions to backtrack
BALL::Exception::InvalidIterator	if #start is not called

Implements BALL::BondOrderAssignmentStrategy.

Penalty BALL::FPTBondOrderStrategy::getPenaltyFor_	(	MolecularGraphTraits::VertexType	vertex,
		Valence	valence
	)		const

protected

Return penalty value for given vertex and valence.

virtual void BALL::FPTBondOrderStrategy::init ( )

virtual

Start the bond assignment computing. Computes the nice tree decomposition and the dynamic programming table. After calling this method, you can access the solutions

Exceptions

BALL::Exception::NullPointer if the atom container or penalty map aren't set

Implements BALL::BondOrderAssignmentStrategy.

void BALL::FPTBondOrderStrategy::initPenaltyData_ ( )

protected

Initialize pointers to penalty data.

virtual bool BALL::FPTBondOrderStrategy::readOptions ( const Options & options )

virtual

Reimplemented from BALL::BondOrderAssignmentStrategy.

virtual void BALL::FPTBondOrderStrategy::setDefaultOptions ( )

virtual

Reimplemented from BALL::BondOrderAssignmentStrategy.

Friends And Related Function Documentation

friend class FPTBondOrderAssignment_

friend

Definition at line 131 of file FPTBondOrderStrategy.h.

Member Data Documentation

std::vector<std::vector<int> > const* BALL::FPTBondOrderStrategy::atom_to_block_

protected

contains the block index for the given atom

Definition at line 1401 of file FPTBondOrderStrategy.h.

std::vector<Size> const* BALL::FPTBondOrderStrategy::block_to_length_

protected

contains for each block_index the number of saved penalties for the atoms in the block

Definition at line 1391 of file FPTBondOrderStrategy.h.

std::vector<Position> const* BALL::FPTBondOrderStrategy::block_to_start_idx_

protected

contains for each block_index the number of saved penalties for the atoms in the block

Definition at line 1386 of file FPTBondOrderStrategy.h.

std::vector<int> const* BALL::FPTBondOrderStrategy::block_to_start_valence_

protected

contains the valence of the first entry of the given block

Definition at line 1396 of file FPTBondOrderStrategy.h.

boost::shared_ptr<DPBackTrackingCombiner_> BALL::FPTBondOrderStrategy::combiner_

protected

The backtracking combiner_

Definition at line 1412 of file FPTBondOrderStrategy.h.

boost::shared_ptr<ComputingData_> BALL::FPTBondOrderStrategy::computing_data_

protected

A shared pointer to the computing data, so that you can copy this instance without copying all the computing data

Definition at line 1407 of file FPTBondOrderStrategy.h.

const Penalty BALL::FPTBondOrderStrategy::infinite_penalty

static

Definition at line 152 of file FPTBondOrderStrategy.h.

const Valence BALL::FPTBondOrderStrategy::max_valence

static

Definition at line 153 of file FPTBondOrderStrategy.h.

std::vector<int> const* BALL::FPTBondOrderStrategy::penalties_

protected

contains for each block-index the position in the penalties_ array where this block starts

Definition at line 1381 of file FPTBondOrderStrategy.h.

Classes

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation