DFSTree.h

Go to the documentation of this file.

#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 */