SubstructureSearch.hpp

Go to the documentation of this file.

/* 
 * SubstructureSearch.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_SUBSTRUCTURESEARCH_HPP
#define CDPL_CHEM_SUBSTRUCTURESEARCH_HPP
 
#include <vector>
#include <deque>
#include <set>
#include <cstddef>
#include <unordered_map>
#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 SubstructureSearch
        {
 
            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<SubstructureSearch> 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;
 
            SubstructureSearch();
 
            SubstructureSearch(const MolecularGraph& query);
 
            SubstructureSearch(const SubstructureSearch&) = delete;
              
            ~SubstructureSearch();
 
            SubstructureSearch& operator=(const SubstructureSearch&) = 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 findMappings(const MolecularGraph& target);
 
            void stopSearch();
 
            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 addAtomMappingConstraint(std::size_t query_atom_idx, std::size_t target_atom_idx);
 
            void clearAtomMappingConstraints();
 
            void addBondMappingConstraint(std::size_t query_bond_idx, std::size_t target_bond_idx);
 
            void clearBondMappingConstraints();
 
          private:
            bool init(const MolecularGraph&);
 
            void initMatchExpressions();
 
            bool findEquivAtoms();
            bool findEquivBonds();
 
            bool mapAtoms();
 
            std::size_t nextQueryAtom() const;
            bool        nextTargetAtom(std::size_t, std::size_t&, std::size_t&) const;
 
            bool atomMappingAllowed(std::size_t, std::size_t) const;
            bool checkAtomMappingConstraints(std::size_t, std::size_t) const;
            bool checkBondMappingConstraints(std::size_t, std::size_t) const;
 
            bool mapBonds(std::size_t, std::size_t);
            bool mapAtoms(std::size_t);
            bool mapAtoms(std::size_t, std::size_t);
 
            bool mappingFound();
 
            bool hasPostMappingMatchExprs() const;
            bool foundMappingMatches(const AtomBondMapping*) const;
 
            bool foundMappingUnique();
 
            void freeAtomBondMappings();
            void freeAtomBondMapping();
 
            AtomBondMapping* createAtomBondMapping();
 
            class ABMappingMask
            {
 
              public:
                void initAtomMask(std::size_t);
                void initBondMask(std::size_t);
 
                void setAtomBit(std::size_t);
                void resetAtomBit(std::size_t);
 
                bool testAtomBit(std::size_t) const;
 
                void setBondBit(std::size_t);
                void resetBondMask();
 
                bool operator<(const ABMappingMask&) const;
                bool operator>(const ABMappingMask&) const;
 
              private:
                Util::BitSet atomMask;
                Util::BitSet bondMask;
            };
 
            typedef std::vector<Util::BitSet>                         BitMatrix;
            typedef std::vector<const Atom*>                          AtomMappingTable;
            typedef std::vector<const Bond*>                          BondMappingTable;
            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<AtomMatchExprPtr>                     AtomMatchExprTable;
            typedef std::vector<BondMatchExprPtr>                     BondMatchExprTable;
            typedef std::unordered_multimap<std::size_t, std::size_t> MappingConstraintMap;
            typedef Util::ObjectStack<AtomBondMapping>                MappingCache;
 
            const MolecularGraph*                 query;
            const MolecularGraph*                 target;
            AtomMatchExpressionFunction           atomMatchExprFunc;
            BondMatchExpressionFunction           bondMatchExprFunc;
            MolecularGraphMatchExpressionFunction molGraphMatchExprFunc;
            BitMatrix                             atomEquivMatrix;
            BitMatrix                             bondEquivMatrix;
            MappingConstraintMap                  atomMappingConstrs;
            MappingConstraintMap                  bondMappingConstrs;
            AtomQueue                             termQueryAtoms;
            AtomMappingTable                      queryAtomMapping;
            BondMappingTable                      queryBondMapping;
            Util::BitSet                          queryMappingMask;
            ABMappingMask                         targetMappingMask;
            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                                  exitSearch;
            std::size_t                           numQueryAtoms;
            std::size_t                           numQueryBonds;
            std::size_t                           numTargetAtoms;
            std::size_t                           numTargetBonds;
            std::size_t                           numMappedAtoms;
            std::size_t                           maxNumMappings;
        };
    } // namespace Chem
} // namespace CDPL
 
#endif // CDPL_CHEM_SUBSTRUCTURESEARCH_HPP