searchStrategy.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN  *
 *   {prenom.nom}_at_lip6.fr                                               *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#ifndef GUM_SEARCHSTRATEGY_H
#define GUM_SEARCHSTRATEGY_H

#include <list>
#include <ostream>
#include <utility>
#include <vector>

#include <agrum/core/math/math.h>
#include <agrum/core/bijection.h>
#include <agrum/core/sequence.h>
#include <agrum/core/set.h>

#include <agrum/graphs/diGraph.h>

#include <agrum/graphs/algorithms/triangulations/partialOrderedTriangulation.h>

#include <agrum/PRM/gspan/edgeGrowth.h>
#include <agrum/PRM/gspan/interfaceGraph.h>
#include <agrum/PRM/gspan/pattern.h>

namespace gum {
  namespace prm {

    template < typename GUM_SCALAR >
    class GSpan;

    namespace gspan {
      template < typename GUM_SCALAR >
      class DFSTree;

      // clang_format off
      // clang_format on
      template < typename GUM_SCALAR >
      class SearchStrategy {
        public:
        // =========================================================================
        // ==========================================================================

        SearchStrategy< GUM_SCALAR >();

        SearchStrategy< GUM_SCALAR >(const SearchStrategy< GUM_SCALAR >& from);

        virtual ~SearchStrategy< GUM_SCALAR >();

        SearchStrategy< GUM_SCALAR >&
           operator=(const SearchStrategy< GUM_SCALAR >& from);

        // =========================================================================
        // ==========================================================================

        void setTree(DFSTree< GUM_SCALAR >* tree);

        virtual bool accept_root(const Pattern* r) = 0;

        virtual bool accept_growth(const Pattern*                  parent,
                                   const Pattern*                  child,
                                   const EdgeGrowth< GUM_SCALAR >& growth) = 0;

        virtual bool operator()(LabelData* i, LabelData* j) = 0;
        virtual bool operator()(Pattern* i, Pattern* j) = 0;

        protected:
        DFSTree< GUM_SCALAR >* _tree;
        double                 _computeCost(const Pattern& p);
      };

      template < typename GUM_SCALAR >
      class FrequenceSearch : public SearchStrategy< GUM_SCALAR > {
        public:
        // =========================================================================
        // ==========================================================================

        explicit FrequenceSearch(Size freq);

        FrequenceSearch(const FrequenceSearch& from);

        virtual ~FrequenceSearch();

        FrequenceSearch& operator=(const FrequenceSearch& from);

        // =========================================================================
        // ==========================================================================

        virtual bool accept_root(const Pattern* r);

        virtual bool accept_growth(const Pattern*                  parent,
                                   const Pattern*                  child,
                                   const EdgeGrowth< GUM_SCALAR >& growth);

        virtual bool operator()(LabelData* i, LabelData* j);
        virtual bool operator()(Pattern* i, Pattern* j);

        private:
        Size __freq;
      };

      template < typename GUM_SCALAR >
      class StrictSearch : public SearchStrategy< GUM_SCALAR > {
        public:
        // =========================================================================
        // ==========================================================================

        explicit StrictSearch(Size freq = 2);

        StrictSearch(const StrictSearch& from);

        virtual ~StrictSearch();

        StrictSearch& operator=(const StrictSearch& from);

        // =========================================================================
        // ==========================================================================

        virtual bool accept_root(const Pattern* r);

        virtual bool accept_growth(const Pattern*                  parent,
                                   const Pattern*                  child,
                                   const EdgeGrowth< GUM_SCALAR >& growth);

        virtual bool operator()(LabelData* i, LabelData* j);
        virtual bool operator()(Pattern* i, Pattern* j);

        private:
        Size   __freq;
        double __inner_cost(const Pattern* p);
        double __outer_cost(const Pattern* p);
        void   __compute_costs(const Pattern* p);
        HashTable< const Pattern*, std::pair< double, double > > __map;
        struct PData {
          UndiGraph graph;
          NodeProperty< Size > mod;
          Bijection< NodeId, std::string > node2attr;
          Bijection< NodeId, const DiscreteVariable* > vars;
          NodeSet inners;
          NodeSet outputs;
        };
        std::string __dot;
        std::string __str(const PRMInstance< GUM_SCALAR >*  i,
                          const PRMAttribute< GUM_SCALAR >* a) const;
        std::string __str(const PRMInstance< GUM_SCALAR >*  i,
                          const PRMAttribute< GUM_SCALAR >& a) const;
        std::string __str(const PRMInstance< GUM_SCALAR >*  i,
                          const PRMSlotChain< GUM_SCALAR >& a) const;
        void        __buildPatternGraph(
                  typename StrictSearch< GUM_SCALAR >::PData&   data,
                  Set< Potential< GUM_SCALAR >* >&              pool,
                  const Sequence< PRMInstance< GUM_SCALAR >* >& match);
        std::pair< Size, Size >
           __elimination_cost(typename StrictSearch< GUM_SCALAR >::PData& data,
                              Set< Potential< GUM_SCALAR >* >&            pool);
      };

      template < typename GUM_SCALAR >
      class TreeWidthSearch : public SearchStrategy< GUM_SCALAR > {
        public:
        // =========================================================================
        // ==========================================================================

        TreeWidthSearch();

        TreeWidthSearch(const TreeWidthSearch& from);

        virtual ~TreeWidthSearch();

        TreeWidthSearch& operator=(const TreeWidthSearch& from);

        // =========================================================================
        // ==========================================================================

        double cost(const Pattern& p);

        virtual bool accept_root(const Pattern* r);

        virtual bool accept_growth(const Pattern*                  parent,
                                   const Pattern*                  child,
                                   const EdgeGrowth< GUM_SCALAR >& growth);

        virtual bool operator()(LabelData* i, LabelData* j);
        virtual bool operator()(Pattern* i, Pattern* j);

        private:
        HashTable< const Pattern*, double > __map;
      };


#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
      extern template class SearchStrategy< double >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
      extern template class FrequenceSearch< double >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
      extern template class StrictSearch< double >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
      extern template class TreeWidthSearch< double >;
#      endif
#    endif
#  endif
#endif


    } /* namespace gspan */
  }   /* namespace prm */
} /* namespace gum */

#include <agrum/PRM/gspan/searchStrategy_tpl.h>

#endif /* GUM_DFS_TREE_H */