MaxCommonBondSubstructureSearch.hpp

Go to the documentation of this file.

/* 
 * MaxCommonBondSubstructureSearch.hpp 
 *
 * 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_MAXCOMMONBONDSUBSTRUCTURESEARCH_HPP
#define CDPL_CHEM_MAXCOMMONBONDSUBSTRUCTURESEARCH_HPP
 
#include <vector>
#include <set>
#include <cstddef>
 
#include <boost/iterator/indirect_iterator.hpp>
 
#include "CDPL/Chem/APIPrefix.hpp"
#include "CDPL/Chem/AtomBondMapping.hpp"
#include "CDPL/Chem/MatchExpression.hpp"
#include "CDPL/Util/BitSet.hpp"
#include "CDPL/Util/ObjectStack.hpp"
 
 
namespace CDPL
{
 
    namespace Chem
    {
 
        class MolecularGraph;
        class Atom;
        class Bond;
 
        class CDPL_CHEM_API MaxCommonBondSubstructureSearch
        {
 
            typedef std::vector<AtomBondMapping*> ABMappingList;
 
          public:
            typedef boost::indirect_iterator<ABMappingList::iterator, AtomBondMapping> MappingIterator;
 
            typedef boost::indirect_iterator<ABMappingList::const_iterator, const AtomBondMapping> ConstMappingIterator;
 
            MaxCommonBondSubstructureSearch();
 
            MaxCommonBondSubstructureSearch(const MolecularGraph& query);
 
            ~MaxCommonBondSubstructureSearch();
 
            void setQuery(const MolecularGraph& query);
 
            bool mappingExists(const MolecularGraph& target);
 
            bool findMappings(const MolecularGraph& target);
 
            std::size_t getNumMappings() const;
 
            AtomBondMapping& getMapping(std::size_t idx);
 
            const AtomBondMapping& getMapping(std::size_t idx) const;
 
            MappingIterator getMappingsBegin();
 
            ConstMappingIterator getMappingsBegin() const;
 
            MappingIterator getMappingsEnd();
 
            ConstMappingIterator getMappingsEnd() const;
 
            MappingIterator begin();
 
            ConstMappingIterator begin() const;
 
            MappingIterator end();
 
            ConstMappingIterator end() const;
 
            void uniqueMappingsOnly(bool unique);
 
            bool uniqueMappingsOnly() const;
 
            void setMaxNumMappings(std::size_t max_num_mappings);
 
            std::size_t getMaxNumMappings() const;
 
            void setMinSubstructureSize(std::size_t min_size);
 
            std::size_t getMinSubstructureSize() const;
 
          private:
            class AGNode;
 
            MaxCommonBondSubstructureSearch(const MaxCommonBondSubstructureSearch&);
 
            MaxCommonBondSubstructureSearch& operator=(const MaxCommonBondSubstructureSearch&);
 
            bool init(const MolecularGraph&);
 
            void initMatchExpressions();
 
            bool findEquivAtoms();
 
            bool atomsCompatible(const Bond&, const Bond&) const;
 
            const Atom* getCommonAtom(const Bond&, const Bond&) const;
 
            bool buildAssocGraph();
 
            bool findAssocGraphCliques(std::size_t);
            bool isLegal(const AGNode*);
 
            void undoAtomMapping(std::size_t);
 
            bool mappingFound();
 
            bool hasPostMappingMatchExprs() const;
            bool foundMappingMatches(const AtomBondMapping*) const;
 
            bool foundMappingUnique(bool);
 
            void clearMappings();
 
            AtomBondMapping* createAtomBondMapping(bool);
            void             freeAtomBondMapping();
 
            void freeAssocGraph();
            void freeAtomBondMappings();
 
            class AGEdge;
 
            AGNode* allocAGNode(const Bond*, const Bond*);
            AGEdge* allocAGEdge(const Atom*, const Atom*);
 
            typedef std::vector<const AGEdge*> AGraphEdgeList;
 
            class AGNode
            {
 
              public:
                void        setQueryBond(const Bond*);
                const Bond* getQueryBond() const;
 
                void        setAssocBond(const Bond*);
                const Bond* getAssocBond() const;
 
                void addEdge(const AGEdge*);
 
                bool          isConnected(const AGNode*) const;
                const AGEdge* findEdge(const AGNode*) const;
 
                void clear();
 
                void setIndex(std::size_t idx);
 
              private:
                std::size_t    index;
                const Bond*    queryBond;
                const Bond*    assocBond;
                Util::BitSet   connNodes;
                AGraphEdgeList atomEdges;
            };
 
            class AGEdge
            {
 
              public:
                void        setQueryAtom(const Atom*);
                const Atom* getQueryAtom() const;
 
                void        setAssocAtom(const Atom*);
                const Atom* getAssocAtom() const;
 
                void setNode1(const AGNode*);
                void setNode2(const AGNode*);
 
                const AGNode* getNode1() const;
                const AGNode* getNode2() const;
 
                const AGNode* getOther(const AGNode*) const;
 
              private:
                const Atom*   queryAtom;
                const Atom*   assocAtom;
                const AGNode* node1;
                const AGNode* node2;
            };
 
            class ABMappingMask
            {
 
              public:
                void initQueryAtomMask(std::size_t);
                void initTargetAtomMask(std::size_t);
 
                void initQueryBondMask(std::size_t);
                void initTargetBondMask(std::size_t);
 
                void setQueryAtomBit(std::size_t);
                void setTargetAtomBit(std::size_t);
 
                void resetQueryAtomBit(std::size_t);
                void resetTargetAtomBit(std::size_t);
 
                bool testQueryAtomBit(std::size_t) const;
                bool testTargetAtomBit(std::size_t) const;
 
                void setQueryBondBit(std::size_t);
                void setTargetBondBit(std::size_t);
 
                void resetQueryAtomBits();
                void resetTargetAtomBits();
 
                void resetBondBits();
 
                bool operator<(const ABMappingMask&) const;
                bool operator>(const ABMappingMask&) const;
 
              private:
                Util::BitSet queryAtomMask;
                Util::BitSet targetAtomMask;
                Util::BitSet queryBondMask;
                Util::BitSet targetBondMask;
            };
 
            typedef MatchExpression<MolecularGraph>::SharedPointer MolGraphMatchExprPtr;
 
            typedef std::vector<Util::BitSet>                                         BitMatrix;
            typedef std::vector<AGNode*>                                              AGraphNodeList;
            typedef std::vector<AGraphNodeList>                                       AGraphNodeMatrix;
            typedef std::set<ABMappingMask>                                           UniqueMappingList;
            typedef std::vector<const Atom*>                                          AtomList;
            typedef std::vector<const Bond*>                                          BondList;
            typedef std::vector<MatchExpression<Atom, MolecularGraph>::SharedPointer> AtomMatchExprTable;
            typedef std::vector<MatchExpression<Bond, MolecularGraph>::SharedPointer> BondMatchExprTable;
            typedef Util::ObjectStack<AGNode>                                         NodeCache;
            typedef Util::ObjectStack<AGEdge>                                         EdgeCache;
            typedef Util::ObjectStack<AtomBondMapping>                                MappingCache;
 
            const MolecularGraph* query;
            const MolecularGraph* target;
            BitMatrix             atomEquivMatrix;
            AGraphNodeMatrix      nodeMatrix;
            ABMappingList         foundMappings;
            UniqueMappingList     uniqueMappings;
            AGraphEdgeList        cliqueEdges;
            AGraphNodeList        cliqueNodes;
            ABMappingMask         mappingMask;
            AtomMatchExprTable    atomMatchExprTable;
            BondMatchExprTable    bondMatchExprTable;
            MolGraphMatchExprPtr  molGraphMatchExpr;
            AtomList              postMappingMatchAtoms;
            BondList              postMappingMatchBonds;
            NodeCache             nodeCache;
            EdgeCache             edgeCache;
            MappingCache          mappingCache;
            bool                  queryChanged;
            bool                  initQueryData;
            bool                  uniqueMatches;
            bool                  saveMappings;
            std::size_t           numQueryAtoms;
            std::size_t           numQueryBonds;
            std::size_t           numTargetAtoms;
            std::size_t           numTargetBonds;
            std::size_t           maxBondSubstructureSize;
            std::size_t           currNumNullNodes;
            std::size_t           minNumNullNodes;
            std::size_t           maxNumMappings;
            std::size_t           minSubstructureSize;
            std::size_t           currNodeIdx;
        };
    } // namespace Chem
} // namespace CDPL
 
#endif // CDPL_CHEM_MAXCOMMONBONDSUBSTRUCTURESEARCH_HPP