gspan.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_GSPAN_H
#define GUM_GSPAN_H

#include <algorithm>
#include <list>
#include <ostream>
#include <string>
#include <vector>

#include <agrum/core/timer.h>

#include <agrum/BN/inference/variableElimination.h>

#include <agrum/PRM/PRM.h>
#include <agrum/PRM/gspan/DFSTree.h>
#include <agrum/PRM/gspan/interfaceGraph.h>

namespace gum {
  namespace prm {

    template < typename GUM_SCALAR >
    class GSpan {
      public:
      // ========================================================================
      // ========================================================================

      GSpan(const PRM< GUM_SCALAR >&             prm,
            const PRMSystem< GUM_SCALAR >&       sys,
            gspan::SearchStrategy< GUM_SCALAR >* strategy = 0);

      ~GSpan();

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

      Size getMaxDFSDepth() const;

      void setMaxDFSDepth(Size depth);

      gspan::DFSTree< GUM_SCALAR >& tree();

      const gspan::DFSTree< GUM_SCALAR >& tree() const;

      gspan::InterfaceGraph< GUM_SCALAR >& interfaceGraph();

      const gspan::InterfaceGraph< GUM_SCALAR >& interfaceGraph() const;

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

      void discoverPatterns();

      std::vector< gspan::Pattern* >& patterns();

      const std::vector< gspan::Pattern* >& patterns() const;

      typedef Set< Sequence< PRMInstance< GUM_SCALAR >* >* > MatchedInstances;

      MatchedInstances& matches(const gspan::Pattern& p);

      const MatchedInstances& matches(const gspan::Pattern& p) const;

      // /**
      //  * Returns the cumulative sum of all the cliques size created after
      //  lifting
      //  * the patterns.
      //  * @returns the cumulative sum of all the cliques size created after
      //  lifting
      //  *          the patterns.
      //  */
      // double patterns_cost() const;

      // /**
      //  * Returns the cumulative sum of all the cliques size created after
      //  lifting
      //  * the inner attributes.
      //  * @returns the cumulative sum of all the cliques size created after
      //  lifting
      //  *          the inner attributes.
      //  */
      // double sve_cost() const;

      private:
      // ========================================================================
      // ========================================================================

      gspan::InterfaceGraph< GUM_SCALAR >* __graph;

      gspan::DFSTree< GUM_SCALAR > __tree;

      Size __depth_stop;

      std::vector< gspan::Pattern* > __patterns;

      std::vector< gspan::LabelData* > __nodes;

      std::vector< gspan::LabelData* > __edges;

      HashTable< gspan::LabelData*, Idx > __cost;

      HashTable< gspan::Pattern*, MatchedInstances* > __matched_instances;

      Set< PRMInstance< GUM_SCALAR >* > __chosen;

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

      void __sortNodesAndEdges();

      void __subgraph_mining(gspan::InterfaceGraph< GUM_SCALAR >& graph,
                             gspan::Pattern&                      p);

      Size __cost_func(Size interface_size, Size frequency);

      void __sortPatterns();

      bool __isEdgeEligible(typename gspan::EdgeData< GUM_SCALAR >* e);


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

      struct LabelSort {
        LabelSort(GSpan* my_gspan);

        LabelSort(const LabelSort& source);

        ~LabelSort();

        bool operator()(gspan::LabelData* i, gspan::LabelData* j);

        GSpan* gspan;
      };

      struct PatternSort {
        PatternSort(GSpan* my_gspan);

        PatternSort(const PatternSort& source);

        ~PatternSort();

        bool operator()(gspan::Pattern* i, gspan::Pattern* j);

        GSpan* gspan;
      };

    };


#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
    extern template class GSpan< double >;
#endif


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

#include <agrum/PRM/inference/gspan_tpl.h>

#endif /* GUM_GSPAN_H */