SmallestSetOfSmallestRings.hpp

Go to the documentation of this file.

/* 
 * SmallestSetOfSmallestRings.hpp 
 * 
 * Implementation of Balducci's SSSR-finder algorithm 
 * (R. Balducci, R. S. Pearlman, J. Chem. Inf. Comput. Sci. 1994, 34, 822-831)
 *
 * This file is part of the Chemical Data Processing Toolkit
 *
 * Copyright (C) 2003 Thomas Seidel <thomas.seidel@univie.ac.at>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; see the file COPYING. If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
 
#ifndef CDPL_CHEM_SMALLESTSETOFSMALLESTRINGS_HPP
#define CDPL_CHEM_SMALLESTSETOFSMALLESTRINGS_HPP
 
#include <vector>
#include <cstddef>
#include <set>
#include <memory>
 
#include "CDPL/Chem/APIPrefix.hpp"
#include "CDPL/Chem/FragmentList.hpp"
#include "CDPL/Chem/CyclicSubstructure.hpp"
#include "CDPL/Util/BitSet.hpp"
#include "CDPL/Util/ObjectPool.hpp"
 
 
namespace CDPL
{
 
    namespace Chem
    {
 
        class CDPL_CHEM_API SmallestSetOfSmallestRings : public FragmentList
        {
 
          public:
            typedef std::shared_ptr<SmallestSetOfSmallestRings> SharedPointer;
 
            SmallestSetOfSmallestRings();
 
            SmallestSetOfSmallestRings(const MolecularGraph& molgraph);
 
            SmallestSetOfSmallestRings(const SmallestSetOfSmallestRings&) = delete;
 
            SmallestSetOfSmallestRings& operator=(const SmallestSetOfSmallestRings&) = delete;
 
            void perceive(const MolecularGraph& molgraph);
 
          private:
            class PathMessage;
 
            typedef SmallestSetOfSmallestRings        Controller;
            typedef Util::ObjectPool<PathMessage>     MessageCache;
            typedef MessageCache::SharedObjectPointer MessagePtr;
            typedef std::vector<MessagePtr>           MessageList;
 
            void visitComponentAtom(const Atom& atom);
 
            void init();
            void findSSSR();
            void createRingFragments();
 
            Fragment::SharedPointer createRing(const MolecularGraph& molgraph, const MessagePtr& msg);
 
            bool sssrComplete() const;
 
            MessagePtr allocMessage();
            MessagePtr allocMessage(std::size_t, std::size_t, std::size_t, std::size_t);
 
            bool processCollision(const MessagePtr&, const MessagePtr&, std::size_t, bool);
            void processRing(const MessagePtr&);
            void processEvenRings();
 
            const char* getClassName() const
            {
                return "SmallestSetOfSmallestRings";
            }
 
            class TNode
            {
 
              public:
                TNode(std::size_t idx):
                    index(idx) {}
 
                bool send(Controller*);
                bool receive(Controller*);
 
                std::size_t getIndex() const;
                std::size_t getNumNeighbors() const;
 
                void initMessages(Controller* ctrl, std::size_t max_num_atoms, std::size_t max_num_bonds);
 
                static void connect(TNode*, TNode*, std::size_t);
 
              private:
                typedef std::vector<TNode*>      NodeList;
                typedef std::vector<std::size_t> BondIndexList;
 
                NodeList      nbrNodes;
                BondIndexList bondIndices;
                MessageList   receiveBuffer;
                MessageList   sendBuffer;
                std::size_t   index;
            };
 
            class PathMessage
            {
 
              public:
                struct LessCmpFunc
                {
 
                    bool operator()(const MessagePtr&, const MessagePtr&) const;
                };
 
                void init(std::size_t, std::size_t, std::size_t, std::size_t);
 
                void copy(const MessagePtr&);
                bool join(const MessagePtr&, const MessagePtr&);
 
                void addAtom(std::size_t);
                void addBond(std::size_t);
 
                bool containsAtom(std::size_t const);
                bool containsBond(std::size_t const);
 
                std::size_t getFirstAtomIndex() const;
                std::size_t getFirstBondIndex() const;
 
                std::size_t getMaxBondIndex() const;
 
                const Util::BitSet& getAtomMask() const;
                const Util::BitSet& getBondMask() const;
 
                void clearFlags();
 
                void setRemoveFlag();
                void setEdgeCollisionFlag();
 
                bool getRemoveFlag() const;
                bool getEdgeCollisionFlag() const;
 
                PathMessage& operator^=(const PathMessage&);
 
              private:
                Util::BitSet atomPath;
                Util::BitSet bondPath;
                std::size_t  firstAtomIdx;
                std::size_t  firstBondIdx;
                std::size_t  maxBondIdx;
                bool         removeFlag;
                bool         edgeCollFlag;
            };
 
            struct TestMatrixRowCmpFunc
            {
 
                bool operator()(const MessagePtr&, const MessagePtr&) const;
            };
 
            typedef std::vector<TNode>                             NodeArray;
            typedef std::set<MessagePtr, PathMessage::LessCmpFunc> ProcRingSet;
 
            MessageCache       msgCache;
            CyclicSubstructure cyclicSubstruct;
            Fragment           component;
            Util::BitSet       visAtomMask;
            NodeArray          nodes;
            ProcRingSet        procRings;
            MessageList        evenRings;
            MessagePtr         testRing;
            MessagePtr         linDepTestRing;
            MessageList        linDepTestMtx;
            MessageList        sssr;
            std::size_t        sssrSize;
        };
    } // namespace Chem
} // namespace CDPL
 
#endif // CDPL_CHEM_SMALLESTSETOFSMALLESTRINGS_HPP