CommonConnectedSubstructureSearch.hpp

Go to the documentation of this file.

/* 
 * CommonConnectedSubstructureSearch.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_COMMONCONNECTEDSUBSTRUCTURESEARCH_HPP
#define CDPL_CHEM_COMMONCONNECTEDSUBSTRUCTURESEARCH_HPP
 
#include <vector>
#include <deque>
#include <set>
#include <cstddef>
#include <memory>
#include <functional>
 
#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 CommonConnectedSubstructureSearch
        {
 
            typedef std::vector<AtomBondMapping*> ABMappingList;
 
            typedef MatchExpression<MolecularGraph>::SharedPointer       MolGraphMatchExprPtr;
            typedef MatchExpression<Atom, MolecularGraph>::SharedPointer AtomMatchExprPtr;
            typedef MatchExpression<Bond, MolecularGraph>::SharedPointer BondMatchExprPtr;
 
          public:
            typedef std::shared_ptr<CommonConnectedSubstructureSearch> SharedPointer;
 
            typedef boost::indirect_iterator<ABMappingList::iterator, AtomBondMapping> MappingIterator;
 
            typedef boost::indirect_iterator<ABMappingList::const_iterator, const AtomBondMapping> ConstMappingIterator;
 
            typedef std::function<const AtomMatchExprPtr&(const Atom&)>               AtomMatchExpressionFunction;
 
            typedef std::function<const BondMatchExprPtr&(const Bond&)>               BondMatchExpressionFunction;
 
            typedef std::function<const MolGraphMatchExprPtr&(const MolecularGraph&)> MolecularGraphMatchExpressionFunction;
 
            CommonConnectedSubstructureSearch();
 
            CommonConnectedSubstructureSearch(const MolecularGraph& query);
 
            CommonConnectedSubstructureSearch(const CommonConnectedSubstructureSearch&) = delete;
              
            ~CommonConnectedSubstructureSearch();
 
            CommonConnectedSubstructureSearch& operator=(const CommonConnectedSubstructureSearch&) = delete;
 
            void setAtomMatchExpressionFunction(const AtomMatchExpressionFunction& func);
 
            void setBondMatchExpressionFunction(const BondMatchExpressionFunction& func);
 
            void setMolecularGraphMatchExpressionFunction(const MolecularGraphMatchExpressionFunction& func);
 
            void setQuery(const MolecularGraph& query);
 
            bool mappingExists(const MolecularGraph& target);
 
            bool findAllMappings(const MolecularGraph& target);
 
            bool findMaxMappings(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:
            bool init(const MolecularGraph&);
 
            void initMatchExpressions();
 
            bool findEquivAtoms();
            bool findEquivBonds();
 
            bool mapAtoms();
            bool mapAtoms(std::size_t);
            bool mapAtoms(std::size_t, std::size_t);
 
            bool nextTargetAtom(std::size_t, std::size_t&, std::size_t&) const;
 
            bool mappingFound();
 
            bool hasPostMappingMatchExprs() const;
            bool foundMappingMatches(const AtomBondMapping*) const;
 
            bool foundMappingUnique();
            bool mappingAlreadySeen(const AtomBondMapping*) const;
 
            void clearMappings();
 
            void freeAtomBondMappings();
            void freeAtomBondMapping();
 
            AtomBondMapping* createAtomBondMapping();
 
            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 testTargetAtomBit(std::size_t) const;
 
                void setQueryBondBit(std::size_t);
                void setTargetBondBit(std::size_t);
 
                void resetBondMasks();
 
                bool operator<(const ABMappingMask&) const;
                bool operator>(const ABMappingMask&) const;
 
              private:
                Util::BitSet queryAtomMask;
                Util::BitSet targetAtomMask;
                Util::BitSet queryBondMask;
                Util::BitSet targetBondMask;
            };
 
            typedef std::vector<Util::BitSet>                                         BitMatrix;
            typedef std::vector<const Atom*>                                          AtomMappingTable;
            typedef std::vector<std::size_t>                                          AtomIndexList;
            typedef std::vector<std::size_t>                                          BondMappingStack;
            typedef std::deque<std::size_t>                                           AtomQueue;
            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<AtomBondMapping>                                MappingCache;
 
            const MolecularGraph*                 query;
            const MolecularGraph*                 target;
            AtomMatchExpressionFunction           atomMatchExprFunc;
            BondMatchExpressionFunction           bondMatchExprFunc;
            MolecularGraphMatchExpressionFunction molGraphMatchExprFunc;
            BitMatrix                             atomEquivMatrix;
            BitMatrix                             bondEquivMatrix;
            AtomQueue                             termQueryAtoms;
            AtomIndexList                         termTargetAtoms;
            BondMappingStack                      bondMappingStack;
            AtomMappingTable                      queryAtomMapping;
            ABMappingMask                         mappingMask;
            Util::BitSet                          hiddenQueryAtomMask;
            Util::BitSet                          termQueryAtomMask;
            Util::BitSet                          termTargetAtomMask;
            ABMappingList                         foundMappings;
            UniqueMappingList                     uniqueMappings;
            AtomMatchExprTable                    atomMatchExprTable;
            BondMatchExprTable                    bondMatchExprTable;
            MolGraphMatchExprPtr                  molGraphMatchExpr;
            AtomList                              postMappingMatchAtoms;
            BondList                              postMappingMatchBonds;
            MappingCache                          mappingCache;
            bool                                  queryChanged;
            bool                                  initQueryData;
            bool                                  uniqueMatches;
            bool                                  saveMappings;
            bool                                  maxMappingsOnly;
            std::size_t                           numQueryAtoms;
            std::size_t                           numQueryBonds;
            std::size_t                           numTargetAtoms;
            std::size_t                           numTargetBonds;
            std::size_t                           numMappedAtoms;
            std::size_t                           currMaxSubstructureSize;
            std::size_t                           maxBondStackSize;
            std::size_t                           maxNumMappings;
            std::size_t                           minSubstructureSize;
        };
    } // namespace Chem
} // namespace CDPL
 
#endif // CDPL_CHEM_COMMONCONNECTEDSUBSTRUCTURESEARCH_HPP