FPTBondOrderStrategy.h

Go to the documentation of this file.

#ifndef BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H
#define BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H

#ifndef BALL_COMMON_GLOBAL_H
# include <BALL/COMMON/global.h>
#endif

#ifndef BALL_MATHS_COMMON_H
# include <BALL/MATHS/common.h>
#endif

#ifndef BALL_KERNEL_ATOMCONTAINER_H
# include <BALL/KERNEL/atomContainer.h>
#endif

#ifndef BALL_KERNEL_BOND_H
# include <BALL/KERNEL/bond.h>
#endif

#ifndef BALL_DATATYPE_HASHMAP_H
# include <BALL/DATATYPE/hashMap.h>
#endif

#ifndef BALL_DATATYPE_GRAPH_H
# include <BALL/DATATYPE/GRAPH/molecularGraph.h>
#endif

#ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
# include <BALL/DATATYPE/GRAPH/graphAlgorithms.h>
#endif

#ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H
# include <BALL/DATATYPE/GRAPH/treeWidth.h>
#endif

#ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENTSTRATEGY_H
# include <BALL/STRUCTURE/BONDORDERS/bondOrderAssignmentStrategy.h>
#endif

#ifndef BALL_STRUCTURE_BONDORDERS_BONDORDERASSIGNMENT_H
# include <BALL/STRUCTURE/BONDORDERS/bondOrderAssignment.h>
#endif

#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <iterator>
#include <queue>

#include <boost/shared_ptr.hpp>
#include <boost/ref.hpp>

namespace BALL
{
  //TODO: documentation is obsolete!
  class BALL_EXPORT FPTBondOrderStrategy
    : public BondOrderAssignmentStrategy
  {
    public:
      typedef GRAPH::GraphTraits<MolecularGraph>::EdgeType Edge;
      typedef GRAPH::GraphTraits<MolecularGraph>::VertexType VertexType;

      typedef TreeWidth<MolecularGraph>::TreeDecomposition    TreeDecomposition;
      typedef TreeWidth<MolecularGraph>::TreeDecompositionBag TreeDecompositionBag;

      friend class FPTBondOrderAssignment_;

      typedef float Penalty;

      typedef int Valence;

      typedef int BondOrder;

      static const Penalty infinite_penalty;
      static const Valence max_valence;

      struct BALL_EXPORT Option
      {
        static String UPPER_PENALTY_BOUND;
      };

      struct BALL_EXPORT Default
      {
        static Penalty UPPER_PENALTY_BOUND;
      };


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

    protected:
      class DPConfig_
      {
        public:
          DPConfig_();

          DPConfig_(Size atoms, Size bonds);

          DPConfig_(std::vector<Valence> const& v, std::vector<BondOrder> const&  bo);

          DPConfig_& operator=(DPConfig_ const& copy);

          template<typename ValenceIterator, typename BondIterator>
          DPConfig_(ValenceIterator vit, ValenceIterator vend, BondIterator boit, BondIterator boend) 
            : consumed_valences(vit, vend), 
              bond_assignments(boit, boend)
          {
          }

          bool operator < (DPConfig_ const& conf) const;

          bool operator > (DPConfig_ const& conf) const;

          bool operator <= (DPConfig_ const& conf) const;

          bool operator >= (DPConfig_ const& conf) const;

          bool operator == (DPConfig_ const& conf) const;

          int compare(DPConfig_ const& other) const;

          Size numberOfAtoms() const;

          Size numberOfBonds() const;

          std::vector<Valence> consumed_valences;

          std::vector<BondOrder> bond_assignments;

      };

      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_;

      class DPTable_
      {
        protected:
          DPMap_ table;

        public:
          DPTable_();

          DPTable_(DPTable_ const& table);

          typedef DPMap_::iterator iterator;

          typedef DPMap_::const_iterator const_iterator;

          Penalty operator[](DPConfig_ const& config) const;

          bool insert(DPConfig_ const& config, Penalty penalty);

          Size size() const;

          Penalty bestPenalty() const;

          DPConstRow_ bestEntry() const;

          iterator begin();

          iterator end();

          const_iterator begin() const;

          const_iterator end() const;
      };

      class AdditionalBagProperties_
      {
        public:
          AdditionalBagProperties_();

          AdditionalBagProperties_(AdditionalBagProperties_ const& copy);

          AdditionalBagProperties_& operator=(AdditionalBagProperties_ const& copy);

          ~AdditionalBagProperties_();

          std::vector<MolecularGraphTraits::EdgeType> bonds;

          DPTable_ * table;
      };

      class DPBackTracking_;
      class DPBackTrackingCombiner_;

      class FPTBondOrderAssignment_
      {
        public:
          friend class DPBackTracking_;
          friend class DPBackTrackingCombiner_;
          friend class GRAPH::PostOrderFolding<TreeDecomposition, TreeDecompositionBag, DPTable_*, FPTBondOrderAssignment_>;

          FPTBondOrderAssignment_(FPTBondOrderStrategy& parent, boost::shared_ptr<TreeDecomposition>& ntd, 
                                  Penalty upper_bound = infinite_penalty);

          ~FPTBondOrderAssignment_();

          Penalty compute();

        protected:
          FPTBondOrderStrategy* parent_;

          MolecularGraph * molecule_;

          boost::shared_ptr<TreeDecomposition> ntd_;

          vector<AdditionalBagProperties_> properties_;

          Penalty upper_bound_;

          BondOrder max_bond_order_;

          Valence max_valence_;

          DPTable_* operator() (TreeDecompositionBag& bag, 
              std::vector<DPTable_*>::const_iterator begin, std::vector<DPTable_*>::const_iterator end);

          std::vector<MolecularGraphTraits::EdgeType> getBondsInBag(TreeDecompositionBag& bag);

          void computeLeafIntroduceBag(AdditionalBagProperties_& bag_properties);

          void computeIntroduceBag(TreeDecompositionBag& bag, 
                                   DPTable_& child, AdditionalBagProperties_& bag_properties);

          void computeForgetBag(TreeDecompositionBag& bag,
                                DPTable_& child, AdditionalBagProperties_& property);

          void computeJoinBag(TreeDecompositionBag& bag,
              DPTable_& leftChild, DPTable_& rightChild, AdditionalBagProperties_& bag_properties);

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

      };

      class ComputingData_
      {
        public:
          ComputingData_();

          ~ComputingData_();

          vector<FPTBondOrderAssignment_*> bond_assignments;

          MolecularGraph *molecule_graph;

          boost::shared_ptr<TreeWidth<MolecularGraph> > tw;

          vector<Bond const *> bonds;
      };

      class Assignment_
      {
        public:
          Assignment_();

          Assignment_(Size num_bonds);

          Assignment_(Assignment_ const& copy);

          Assignment_(std::vector<BondOrder> const& bonds, Penalty penalty);

          Assignment_& operator=(Assignment_ const& copy);

          BondOrder operator [](Size index) const;

          BondOrder& operator [](Size index);

          void combine(Assignment_ const& other);

          std::vector<BondOrder> const& getBondOrders() const;

          int compare(Assignment_ const& a) const;

          bool operator < (Assignment_ const& a) const;

          bool operator > (Assignment_ const& a) const;

          bool operator <= (Assignment_ const& a) const;

          bool operator >= (Assignment_ const& a) const;

          bool operator == (Assignment_ const& a) const;

          bool isValid(MolecularGraph& molecule, FPTBondOrderStrategy& parent);

          Penalty penalty;

        protected:
          std::vector<BondOrder> bonds_;

      };

      struct DPJoinMapComparator_
      {
        bool operator() (DPConfig_ const* leftp, DPConfig_ const* rightp) const;

        int compare(DPConfig_ const* leftp, DPConfig_ const* rightp) const;
      };

      class EdgeComparator_
      {
        public:
          typedef GRAPH::GraphTraits<MolecularGraph>::EdgeType Edge;

          EdgeComparator_(MolecularGraph* graph)
            : graph_(graph)
          { }

          bool operator() (Edge const& e1, Edge const& e2);

        protected:
          MolecularGraph* graph_;
      };

      class BackTrackingState_
      {
        public:
          BackTrackingState_();

          BackTrackingState_(Size bonds);

          BackTrackingState_(BackTrackingState_ const& other);

          BackTrackingState_& operator=(BackTrackingState_ const& other);

          int compare(BackTrackingState_ const& other) const;

          bool operator < (BackTrackingState_ const&) const;

          bool operator > (BackTrackingState_ const&) const;

          bool operator <= (BackTrackingState_ const&) const;

          bool operator >= (BackTrackingState_ const&) const;

          bool operator == (BackTrackingState_ const&) const;

          Assignment_ assignment;

          DPConfig_ config;

          std::stack<std::pair<DPConfig_, Size> > join_branches;

          Size index;


      };

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

      static bool compareJoinTablePairs_(DPPairIt_ const& left, DPPairIt_ const& right);

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

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

      class DPBackTracking_
      {
        public:
          typedef TreeWidth<MolecularGraph>::TreeDecomposition        TreeDecomposition;
          typedef TreeWidth<MolecularGraph>::TreeDecompositionBag     TreeDecompositionBag;
          typedef TreeWidth<MolecularGraph>::TreeDecompositionContent TreeDecompositionContent;

          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&)
          {
            bags_->push_back(node);
          }

          void inorder(TreeDecompositionBag, TreeDecomposition&)
          {
          }

          void postorder(TreeDecompositionBag, TreeDecomposition&)
          {
          }
          
        protected:

          struct StateComparator_
          {
            bool operator () (BackTrackingState_ const * left, BackTrackingState_ const * right) const;
          };

          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_;

          typedef vector<TreeDecompositionBag> BagVector;

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

      };

      class DPBackTrackingCombiner_
      {
        public:
          DPBackTrackingCombiner_(std::vector<FPTBondOrderAssignment_*>& bond_assignments,
                                  Size solution_number, Penalty upper_bound = infinite_penalty);

          DPBackTrackingCombiner_(DPBackTrackingCombiner_ const& copy);

          ~DPBackTrackingCombiner_();

          void clear();

          DPBackTrackingCombiner_& operator = (DPBackTrackingCombiner_ const& copy);

          bool hasMoreSolutions() const;

          void nextSolution();

          Assignment_& getSolution();

          Assignment_ const& getSolution() const;

          Penalty penaltyOfNextSolution() const;

          std::vector<MolecularGraphTraits::EdgeType> sorted_edges;

        protected:
          std::vector<DPBackTracking_*> backtrackers_;

          std::priority_queue<Assignment_, std::vector<Assignment_>, std::greater<Assignment_> > priority_queue_;

          std::vector<std::vector<Assignment_> > component_solutions_;

          Assignment_ assignment_;

          Size solution_number_;

          Penalty optimum_;

          Penalty upper_bound_;

          std::pair<Size, Penalty> getNextMinimumBackTracker_() const;

          void applyAssignment_(Size backtracker_index, Size solution_index);

          void initialize_();

          void combineEachSolution_(Size mindex);

          std::vector<DPBackTracking_*> deepCopyOfBacktrackers_() const;

      };


      void initPenaltyData_();

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

      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_;
  };
}
#endif // BALL_STRUCTURE_BONDORDERS_FPTBONDORDERSTRATEGY_H