DFSTree.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_DFS_TREE_H
#define GUM_DFS_TREE_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>

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

namespace gum {
  namespace prm {

    template < typename GUM_SCALAR >
    class GSpan;

    namespace gspan {
      template < typename GUM_SCALAR >
      class SearchStrategy;

      template < typename GUM_SCALAR >
      class DFSTree : private DiGraph {
        public:
        // =========================================================================
        // ==========================================================================

        // DFSTree(InterfaceGraph<GUM_SCALAR>* graph);
        DFSTree(const InterfaceGraph< GUM_SCALAR >& graph,
                SearchStrategy< GUM_SCALAR >*       strategy = 0);

        ~DFSTree();

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

        const InterfaceGraph< GUM_SCALAR >& graph() const;

        struct PatternData {
          explicit PatternData(Pattern* p);
          PatternData(const PatternData& from);
          ~PatternData();
          Pattern* pattern;
          std::list< NodeId > children;
          UndiGraph iso_graph;
          NodeProperty< Sequence< PRMInstance< GUM_SCALAR >* >* > iso_map;
          Set< NodeId > max_indep_set;
          Size cost;
          Size gain;
        };

        std::list< NodeId >& roots();

        const std::list< NodeId >& roots() const;

        Pattern& parent(const Pattern& p);

        const Pattern& parent(const Pattern& p) const;

        std::list< NodeId >& children(const Pattern& p);

        const std::list< NodeId >& children(const Pattern& p) const;

        Pattern& pattern(NodeId id);

        const Pattern& pattern(NodeId id) const;

        void addRoot(LabelData& data);

        Pattern& growPattern(Pattern&                  p,
                             EdgeGrowth< GUM_SCALAR >& edge_growth,
                             Size                      min_freq);

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

        UndiGraph& iso_graph(const Pattern& p);

        Sequence< PRMInstance< GUM_SCALAR >* >& iso_map(const Pattern& p,
                                                        NodeId         node);

        Set< NodeId >& max_indep_set(const Pattern& p);

        double frequency(const Pattern& p) const;

        PatternData& data(const Pattern& p);
        const PatternData& data(const Pattern& p) const;

        SearchStrategy< GUM_SCALAR >& strategy();

        const SearchStrategy< GUM_SCALAR >& strategy() const;

        struct NeighborDegreeSort {
          explicit NeighborDegreeSort(UndiGraph& graph);
          NeighborDegreeSort(const NeighborDegreeSort& source);
          ~NeighborDegreeSort();
          bool operator()(NodeId i, NodeId j);
          UndiGraph& g;
        };


        private:
        const InterfaceGraph< GUM_SCALAR >* __graph;

        std::list< NodeId > __roots;

        Bijection< NodeId, Pattern* > __node_map;

        HashTable< Pattern*, PatternData* > __data;

        SearchStrategy< GUM_SCALAR >* __strategy;

        void __checkGrowth(Pattern&                  p,
                           Pattern*                  child,
                           EdgeGrowth< GUM_SCALAR >& edge_growth);

        void __addChild(Pattern&                  p,
                        Pattern*                  child,
                        EdgeGrowth< GUM_SCALAR >& edge_growth);

        bool __is_new_seq(
           Sequence< PRMInstance< GUM_SCALAR >* >&                  seq,
           NodeProperty< Sequence< PRMInstance< GUM_SCALAR >* >* >& iso_map);

        void __initialiaze_root(Pattern*                             p,
                                Sequence< EdgeData< GUM_SCALAR >* >& seq);

        // Used by __find_sub_pattern.
        bool __test_equality(HashTable< PRMClassElement< GUM_SCALAR >*, Size >& x,
                             HashTable< PRMClassElement< GUM_SCALAR >*, Size >& y);
      };


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


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

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

#endif /* GUM_DFS_TREE_H */