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 | Static Protected Member Functions | Protected Attributes | Friends
BALL::FPTBondOrderStrategy Class Reference

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

Inheritance diagram for BALL::FPTBondOrderStrategy:
BALL::BondOrderAssignmentStrategy

List of all members.

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 ()

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.
Penalty getPenaltyFor_ (MolecularGraphTraits::VertexType vertex, Valence valence) const
 Return penalty value for given vertex and valence.

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_
Penalty upper_bound_
 upper bound on the penalty values for which we compute solutions
boost::shared_ptr< ComputingData_computing_data_
boost::shared_ptr
< DPBackTrackingCombiner_
combiner_

Friends

class FPTBondOrderAssignment_

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


Member Typedef Documentation

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

Definition at line 152 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 332 of file FPTBondOrderStrategy.h.

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

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

Definition at line 946 of file FPTBondOrderStrategy.h.

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

Definition at line 129 of file FPTBondOrderStrategy.h.

Penalties are represented as floats

Definition at line 140 of file FPTBondOrderStrategy.h.

Definition at line 132 of file FPTBondOrderStrategy.h.

Definition at line 133 of file FPTBondOrderStrategy.h.

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

Definition at line 146 of file FPTBondOrderStrategy.h.

Definition at line 130 of file FPTBondOrderStrategy.h.


Constructor & Destructor Documentation

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 
) [static, protected]

compare two join-table antecessor pairs by comparing their penalties

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

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::OutOfRangeif there are no more solutions to backtrack
BALL::Exception::InvalidIteratorif #start is not called

Implements BALL::BondOrderAssignmentStrategy.

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::NullPointerif the atom container or penalty map aren't set

Implements BALL::BondOrderAssignmentStrategy.

Initialize pointers to penalty data.

virtual bool BALL::FPTBondOrderStrategy::readOptions ( const Options options) [virtual]

Reimplemented from BALL::BondOrderAssignmentStrategy.

Reimplemented from BALL::BondOrderAssignmentStrategy.


Friends And Related Function Documentation

friend class FPTBondOrderAssignment_ [friend]

Definition at line 135 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 1408 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 1398 of file FPTBondOrderStrategy.h.

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

Definition at line 1393 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 1403 of file FPTBondOrderStrategy.h.

The backtracking combiner_

Definition at line 1422 of file FPTBondOrderStrategy.h.

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

Definition at line 1417 of file FPTBondOrderStrategy.h.

Definition at line 156 of file FPTBondOrderStrategy.h.

Definition at line 157 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 1388 of file FPTBondOrderStrategy.h.

upper bound on the penalty values for which we compute solutions

Definition at line 1411 of file FPTBondOrderStrategy.h.

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