1#ifndef BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H
2#define BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H
4#ifndef BALL_COMMON_GLOBAL_H
8#ifndef BALL_MATHS_COMMON_H
12#ifndef BALL_KERNEL_ATOMCONTAINER_H
16#ifndef BALL_KERNEL_BOND_H
20#ifndef BALL_DATATYPE_HASHMAP_H
24#ifndef BALL_DATATYPE_GRAPH_H
28#ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
32#ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H
36#ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENTSTRATEGY_H
40#ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENT_H
52#include <boost/shared_ptr.hpp>
53#include <boost/ref.hpp>
237 DPConfig_(std::vector<Valence>
const& v, std::vector<BondOrder>
const& bo);
247 template<
typename ValenceIterator,
typename BondIterator>
248 DPConfig_(ValenceIterator vit, ValenceIterator vend, BondIterator boit, BondIterator boend)
249 : consumed_valences(vit, vend),
250 bond_assignments(boit, boend)
341 typedef std::map<DPConfig_, Penalty>
DPMap_;
460 std::vector<MolecularGraphTraits::EdgeType>
bonds;
493 Penalty upper_bound = infinite_penalty);
523 boost::shared_ptr<TreeDecomposition>
ntd_;
563 std::vector<DPTable_*>::const_iterator begin, std::vector<DPTable_*>::const_iterator end);
641 std::vector<MolecularGraphTraits::EdgeType>& child_bonds,
Size forgotten_index);
676 boost::shared_ptr<TreeWidth<MolecularGraph> >
tw;
942 typedef std::pair<DPTable_::const_iterator, DPTable_::const_iterator>
DPPairIt_;
958 typedef std::multimap<DPConfig_ const*, Penalty, DPJoinMapComparator_>
DPJoinMap_;
997 std::vector<MolecularGraphTraits::EdgeType>
const& bonds,
Penalty upperbound = infinite_penalty);
1051 bags_->push_back(node);
1091 std::multiset<BackTrackingState_*, StateComparator_>
queue_;
1102 std::vector<MolecularGraphTraits::EdgeType>
const*
bonds_;
1107 boost::shared_ptr<std::vector<TreeDecompositionBag> >
bags_;
1249 Size solution_number,
Penalty upper_bound = infinite_penalty);
1312 std::priority_queue<Assignment_, std::vector<Assignment_>, std::greater<Assignment_> >
priority_queue_;
boost::graph_traits< Graph >::vertex_descriptor VertexType
boost::graph_traits< Graph >::edge_descriptor EdgeType
std::set< OriginalVertexType > TreeDecompositionContent
boost::graph_traits< TreeDecompositionGraph >::vertex_descriptor TreeDecompositionBag
boost::graph_as_tree< TreeDecompositionGraph, TreeDecompositionParentMap > TreeDecomposition
Assignment of bond orders from topology information.
Base class for bond order assignment algorithms.
GRAPH::GraphTraits< MolecularGraph >::VertexType VertexType
static const Penalty infinite_penalty
virtual void setDefaultOptions()
static bool compareTablePointerEntries_(DPPointerRow_ const &left, DPPointerRow_ const &right)
std::multimap< DPConfig_ const *, Penalty, DPJoinMapComparator_ > DPJoinMap_
std::vector< std::vector< int > > const * atom_to_block_
void initPenaltyData_()
Initialize pointers to penalty data.
TreeWidth< MolecularGraph >::TreeDecomposition TreeDecomposition
std::pair< DPTable_::const_iterator, DPTable_::const_iterator > DPPairIt_
GRAPH::GraphTraits< MolecularGraph >::EdgeType Edge
std::vector< int > const * penalties_
std::map< DPConfig_, Penalty > DPMap_
std::vector< int > const * block_to_start_valence_
boost::shared_ptr< DPBackTrackingCombiner_ > combiner_
TreeWidth< MolecularGraph >::TreeDecompositionBag TreeDecompositionBag
std::pair< DPConfig_ *, Penalty > DPPointerRow_
boost::shared_ptr< ComputingData_ > computing_data_
std::pair< boost::reference_wrapper< DPConfig_ >, Penalty > DPRow_
FPTBondOrderStrategy(AssignBondOrderProcessor *parent)
virtual bool readOptions(const Options &options)
static const Valence max_valence
virtual ~FPTBondOrderStrategy()
Penalty getPenaltyFor_(MolecularGraphTraits::VertexType vertex, Valence valence) const
Return penalty value for given vertex and valence.
virtual boost::shared_ptr< BondOrderAssignment > computeNextSolution()
std::pair< boost::reference_wrapper< DPConfig_ const >, Penalty > DPConstRow_
static bool compareJoinTablePairs_(DPPairIt_ const &left, DPPairIt_ const &right)
std::vector< Position > const * block_to_start_idx_
std::vector< Size > const * block_to_length_
static String UPPER_PENALTY_BOUND
static Penalty UPPER_PENALTY_BOUND
Size numberOfAtoms() const
DPConfig_ & operator=(DPConfig_ const ©)
DPConfig_(Size atoms, Size bonds)
std::vector< BondOrder > bond_assignments
Size numberOfBonds() const
DPConfig_(ValenceIterator vit, ValenceIterator vend, BondIterator boit, BondIterator boend)
int compare(DPConfig_ const &other) const
DPConfig_(std::vector< Valence > const &v, std::vector< BondOrder > const &bo)
std::vector< Valence > consumed_valences
bool insert(DPConfig_ const &config, Penalty penalty)
DPConstRow_ bestEntry() const
DPTable_(DPTable_ const &table)
DPMap_::iterator iterator
Penalty bestPenalty() const
const_iterator end() const
const_iterator begin() const
DPMap_::const_iterator const_iterator
Penalty operator[](DPConfig_ const &config) const
std::vector< MolecularGraphTraits::EdgeType > bonds
AdditionalBagProperties_(AdditionalBagProperties_ const ©)
AdditionalBagProperties_()
AdditionalBagProperties_ & operator=(AdditionalBagProperties_ const ©)
~AdditionalBagProperties_()
std::vector< MolecularGraphTraits::EdgeType > getBondsInBag(TreeDecompositionBag &bag)
MolecularGraph * molecule_
~FPTBondOrderAssignment_()
void computeJoinBag(TreeDecompositionBag &bag, DPTable_ &leftChild, DPTable_ &rightChild, AdditionalBagProperties_ &bag_properties)
boost::shared_ptr< TreeDecomposition > ntd_
void computeIntroduceBag(TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &bag_properties)
BondOrder max_bond_order_
FPTBondOrderStrategy * parent_
FPTBondOrderAssignment_(FPTBondOrderStrategy &parent, boost::shared_ptr< TreeDecomposition > &ntd, Penalty upper_bound=infinite_penalty)
void computeRootBag(TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &bag_properties)
Penalty forgetInnerVertexIn(TreeDecompositionBag &bag, DPConstRow_ child_row, DPConfig_ &entry, std::vector< MolecularGraphTraits::EdgeType > &child_bonds, Size forgotten_index)
void computeForgetBag(TreeDecompositionBag &bag, DPTable_ &child, AdditionalBagProperties_ &property)
vector< AdditionalBagProperties_ > properties_
void computeLeafIntroduceBag(AdditionalBagProperties_ &bag_properties)
MolecularGraph * molecule_graph
vector< Bond const * > bonds
boost::shared_ptr< TreeWidth< MolecularGraph > > tw
vector< FPTBondOrderAssignment_ * > bond_assignments
bool isValid(MolecularGraph &molecule, FPTBondOrderStrategy &parent)
Assignment_ & operator=(Assignment_ const ©)
Assignment_(Assignment_ const ©)
void combine(Assignment_ const &other)
std::vector< BondOrder > bonds_
std::vector< BondOrder > const & getBondOrders() const
int compare(Assignment_ const &a) const
Assignment_(Size num_bonds)
Assignment_(std::vector< BondOrder > const &bonds, Penalty penalty)
int compare(DPConfig_ const *leftp, DPConfig_ const *rightp) const
EdgeComparator_(MolecularGraph *graph)
GRAPH::GraphTraits< MolecularGraph >::EdgeType Edge
int compare(BackTrackingState_ const &other) const
BackTrackingState_ & operator=(BackTrackingState_ const &other)
std::stack< std::pair< DPConfig_, Size > > join_branches
BackTrackingState_(BackTrackingState_ const &other)
BackTrackingState_(Size bonds)
std::vector< MolecularGraphTraits::EdgeType > const * bonds_
DPBackTracking_(DPBackTracking_ const ©)
Size num_computed_solutions_
Size bondIndexFor(MolecularGraphTraits::EdgeType bond) const
void extendState(BackTrackingState_ &state, DPConfig_ const &antecessor, Penalty additional_penalty)
void preorder(TreeDecompositionBag node, TreeDecomposition &)
boost::shared_ptr< std::vector< TreeDecompositionBag > > bags_
TreeWidth< MolecularGraph >::TreeDecompositionContent TreeDecompositionContent
bool hasMoreSolutions() const
TreeWidth< MolecularGraph >::TreeDecompositionBag TreeDecompositionBag
BackTrackingState_ * current_state_
std::multiset< BackTrackingState_ *, StateComparator_ > queue_
void remember(BackTrackingState_ &state)
Assignment_ const & getSolution() const
void visitForget(BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &table)
void visitIntroduce(BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &table)
vector< TreeDecompositionBag > BagVector
void inorder(TreeDecompositionBag, TreeDecomposition &)
void visitJoin(BackTrackingState_ &state, TreeDecompositionBag &bag, DPTable_ &leftTable, DPTable_ &rightTable)
void setStateAssignment(BackTrackingState_ &state, TreeDecompositionBag &bag, DPConfig_ &antecessor, MolecularGraphTraits::VertexType forgotten_vertex)
AdditionalBagProperties_ & getProperties(Size order)
DPBackTracking_(FPTBondOrderAssignment_ &bond_assignment, Size max_number_of_solutions, std::vector< MolecularGraphTraits::EdgeType > const &bonds, Penalty upperbound=infinite_penalty)
bool isSolutionNeeded(Penalty penalty)
TreeWidth< MolecularGraph >::TreeDecomposition TreeDecomposition
Assignment_ & getSolution()
FPTBondOrderAssignment_ * bond_assignment_
DPTable_ & getTable(Size order)
void branchState(BackTrackingState_ &state, TreeDecompositionBag const &child, DPConfig_ const &antecessor)
Penalty penaltyOfNextSolution() const
void postorder(TreeDecompositionBag, TreeDecomposition &)
void visitLeaf(BackTrackingState_ &state)
Assignment_ const & getSolution() const
DPBackTrackingCombiner_(DPBackTrackingCombiner_ const ©)
~DPBackTrackingCombiner_()
Assignment_ & getSolution()
void combineEachSolution_(Size mindex)
std::vector< std::vector< Assignment_ > > component_solutions_
std::vector< MolecularGraphTraits::EdgeType > sorted_edges
std::priority_queue< Assignment_, std::vector< Assignment_ >, std::greater< Assignment_ > > priority_queue_
DPBackTrackingCombiner_(std::vector< FPTBondOrderAssignment_ * > &bond_assignments, Size solution_number, Penalty upper_bound=infinite_penalty)
Penalty penaltyOfNextSolution() const
std::pair< Size, Penalty > getNextMinimumBackTracker_() const
std::vector< DPBackTracking_ * > deepCopyOfBacktrackers_() const
std::vector< DPBackTracking_ * > backtrackers_
bool hasMoreSolutions() const
void applyAssignment_(Size backtracker_index, Size solution_index)