ringPerceptionProcessor.h

Go to the documentation of this file.

// -*- Mode: C++; tab-width: 2; -*-
// vi: set ts=2:
//
// $Id: ringPerceptionProcessor.h,v 1.17.4.2 2007/04/03 13:29:45 bertsch Exp $
//

#ifndef BALL_QSAR_RINGPERCEPTIONPROCESSOR_H
#define BALL_QSAR_RINGPERCEPTIONPROCESSOR_H

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

#ifndef BALL_STRUCTURE_MOLECULARGRAPH_H
  #include <BALL/STRUCTURE/molecularGraph.h>
#endif

#ifndef BALL_DATATYPE_OPTIONS_H
  #include <BALL/DATATYPE/options.h>
#endif

#include <stack>
#include <vector>

namespace BALL
{
  class BALL_EXPORT RingPerceptionProcessor
    : public UnaryProcessor<AtomContainer>
  {
    public:


      struct Option
      {
        static const char* ALGORITHM_NAME;
      };

      struct Default
      {
        static const char* ALGORITHM_NAME;
      };


      BALL_CREATE(RingPerceptionProcessor)
  
      
      RingPerceptionProcessor();

      RingPerceptionProcessor(const RingPerceptionProcessor& rp);

      virtual ~RingPerceptionProcessor();



      RingPerceptionProcessor& operator = (const RingPerceptionProcessor& rp);



      Size calculateSSSR(vector<vector<Atom*> >& sssr, AtomContainer& ac);

      const vector<vector<Atom*> >& getAllSmallRings() const;
      
      Processor::Result operator () (AtomContainer& ac);
  
      Size findAllBCC(std::vector<MolecularGraph*>& bcc, MolecularGraph& graph);

      /*_ Options for the ring perception
      */
      Options options;                  

      void setDefaultOptions();

    protected:
  
      /*_ @name Accessors
      */
      /*_ Implementation of the Figueras algorithm. This algorithm has some build
          in bugs, and should not be used any more. Hence as default the provable
          correct Balducci/Pearlman algorithm is used.
      */
      Size FiguerasAlgorithm_(vector<vector<Atom*> >& sssr, AtomContainer& ac);

      /*_ Method that return the smallest ring which atom n participates
          @param atom from which the search is started
          @param ring set in which the found ring is stored (if any)
      */
      Size getRing_(Atom* n, HashSet<Atom*>& ring_set);

      /*_ A bond, which when deleted leads to the smallest ring
          is deleted. 
          @param ring_set atoms to test
          @param ac the atom container the algorithm works on
      */
      void checkEdges_(HashSet<Atom*>& ring_set, AtomContainer& ac);
  
      /*_ Method that finds all biconnected components, the algorithm is freely 
          adapted from a standard bcc algorithm.
      */
      Size findAllBCC_(std::vector<MolecularGraph*>& bcc, MolecularGraph& graph);
  
      /*_ recursive function that finds bccs
      */
      void DFSBCC_( std::vector<MolecularGraph*>& bccs, Size dfbi, 
                    HashMap<NodeItem<Index, Index>*, Size> DFBIndex, 
                    NodeItem<Index, Index>* v);
                                    
      HashSet<NodeItem<Index, Index>* > visited_;
      HashSet<EdgeItem<Index, Index>* > visited_bonds_;
      HashMap<NodeItem<Index, Index>* , Size> P_;
      HashMap<NodeItem<Index, Index>*, NodeItem<Index, Index>* > parents_;
      std::stack<EdgeItem<Index, Index>* > BCC_;
  
  
      // Balducci and Pearlman algorithm
      struct PathMessage_;
      
      /*_ The tnode structure described in the paper
      */
      struct TNode_
      {
        void recieve();
        
        void send();
  
        std::vector<PathMessage_> recieve_buffer;
  
        std::vector<PathMessage_> send_buffer;
      };
    
      /*_ The pathMsg structure described in the paper
      */
      struct PathMessage_
      {
        void push(EdgeItem<Index, Index>* bond, TNode_* node);
    
        // path of the message
        BitVector beep;
        
        TNode_* nfirst;
      
        // pointer to the last node of the messages' path
        TNode_* nlast;

        EdgeItem<Index, Index>* efirst;
      };

      static HashMap<TNode_*, NodeItem<Index, Index>* > tnode_to_atom_;
      static HashMap<NodeItem<Index, Index>* , TNode_*> atom_to_tnode_;
      
      static HashMap<EdgeItem<Index, Index>*, Size> bond_to_index_;
      static HashMap<Size, EdgeItem<Index, Index>*> index_to_bond_;
      
      static std::vector<BitVector> rings_;
      
      static std::vector<BitVector> matrix_;
      
      static std::vector<BitVector> forwarded_rings_;
      
      static std::vector<BitVector> tested_beers_;

      static std::vector<std::vector<Atom*> > all_small_rings_;

      static std::vector<BitVector> all_small_beers_;
      
      /*_ function that gets a binary edge-encoded ring as a BitVector
          and adds it to the ringset if its linearly independend
      */
      static void BalducciPearlmanRingSelector_(BitVector bit_vector);
  
      /*_ Implementation of the Balducci/Pearlman algorithm 
      */
      Size BalducciPearlmanAlgorithm_(std::vector<std::vector<Atom*> >& sssr, MolecularGraph& graph);
  };
} // namespace BALL

#endif // BALL_QSAR_RINGPERCEPTIONPROCESSOR_H

---