aGrUM  0.16.0
searchStrategy.h
Go to the documentation of this file.
1 
30 #ifndef GUM_SEARCHSTRATEGY_H
31 #define GUM_SEARCHSTRATEGY_H
32 
33 #include <list>
34 #include <ostream>
35 #include <utility>
36 #include <vector>
37 
38 #include <agrum/core/math/math.h>
39 #include <agrum/core/bijection.h>
40 #include <agrum/core/sequence.h>
41 #include <agrum/core/set.h>
42 
43 #include <agrum/graphs/diGraph.h>
44 
45 #include <agrum/graphs/algorithms/triangulations/partialOrderedTriangulation.h>
46 
47 #include <agrum/PRM/gspan/edgeGrowth.h>
48 #include <agrum/PRM/gspan/interfaceGraph.h>
49 #include <agrum/PRM/gspan/pattern.h>
50 
51 namespace gum {
52  namespace prm {
53 
54  template < typename GUM_SCALAR >
55  class GSpan;
56 
57  namespace gspan {
58  template < typename GUM_SCALAR >
59  class DFSTree;
60 
61  // clang_format off
71  // clang_format on
72  template < typename GUM_SCALAR >
73  class SearchStrategy {
74  public:
75  // =========================================================================
77  // ==========================================================================
79 
81  SearchStrategy< GUM_SCALAR >();
82 
84  SearchStrategy< GUM_SCALAR >(const SearchStrategy< GUM_SCALAR >& from);
85 
87  virtual ~SearchStrategy< GUM_SCALAR >();
88 
90  SearchStrategy< GUM_SCALAR >&
91  operator=(const SearchStrategy< GUM_SCALAR >& from);
92 
94  // =========================================================================
96  // ==========================================================================
98 
99  void setTree(DFSTree< GUM_SCALAR >* tree);
100 
101  virtual bool accept_root(const Pattern* r) = 0;
102 
103  virtual bool accept_growth(const Pattern* parent,
104  const Pattern* child,
105  const EdgeGrowth< GUM_SCALAR >& growth) = 0;
106 
107  virtual bool operator()(LabelData* i, LabelData* j) = 0;
108  virtual bool operator()(Pattern* i, Pattern* j) = 0;
110 
111  protected:
112  DFSTree< GUM_SCALAR >* _tree;
113  double _computeCost(const Pattern& p);
114  };
115 
125  template < typename GUM_SCALAR >
126  class FrequenceSearch : public SearchStrategy< GUM_SCALAR > {
127  public:
128  // =========================================================================
130  // ==========================================================================
132 
134  explicit FrequenceSearch(Size freq);
135 
137  FrequenceSearch(const FrequenceSearch& from);
138 
140  virtual ~FrequenceSearch();
141 
143  FrequenceSearch& operator=(const FrequenceSearch& from);
144 
146  // =========================================================================
148  // ==========================================================================
150 
151  virtual bool accept_root(const Pattern* r);
152 
153  virtual bool accept_growth(const Pattern* parent,
154  const Pattern* child,
155  const EdgeGrowth< GUM_SCALAR >& growth);
156 
157  virtual bool operator()(LabelData* i, LabelData* j);
158  virtual bool operator()(Pattern* i, Pattern* j);
160 
161  private:
162  Size __freq;
163  };
164 
175  template < typename GUM_SCALAR >
176  class StrictSearch : public SearchStrategy< GUM_SCALAR > {
177  public:
178  // =========================================================================
180  // ==========================================================================
182 
184  explicit StrictSearch(Size freq = 2);
185 
187  StrictSearch(const StrictSearch& from);
188 
190  virtual ~StrictSearch();
191 
193  StrictSearch& operator=(const StrictSearch& from);
194 
196  // =========================================================================
198  // ==========================================================================
200 
201  virtual bool accept_root(const Pattern* r);
202 
203  virtual bool accept_growth(const Pattern* parent,
204  const Pattern* child,
205  const EdgeGrowth< GUM_SCALAR >& growth);
206 
207  virtual bool operator()(LabelData* i, LabelData* j);
208  virtual bool operator()(Pattern* i, Pattern* j);
210 
211  private:
212  Size __freq;
213  double __inner_cost(const Pattern* p);
214  double __outer_cost(const Pattern* p);
215  void __compute_costs(const Pattern* p);
216  HashTable< const Pattern*, std::pair< double, double > > __map;
218  struct PData {
220  UndiGraph graph;
222  NodeProperty< Size > mod;
227  Bijection< NodeId, std::string > node2attr;
231  Bijection< NodeId, const DiscreteVariable* > vars;
233  NodeSet inners;
235  NodeSet outputs;
236  };
237  std::string __dot;
238  std::string __str(const PRMInstance< GUM_SCALAR >* i,
239  const PRMAttribute< GUM_SCALAR >* a) const;
240  std::string __str(const PRMInstance< GUM_SCALAR >* i,
241  const PRMAttribute< GUM_SCALAR >& a) const;
242  std::string __str(const PRMInstance< GUM_SCALAR >* i,
243  const PRMSlotChain< GUM_SCALAR >& a) const;
244  void __buildPatternGraph(
245  typename StrictSearch< GUM_SCALAR >::PData& data,
246  Set< Potential< GUM_SCALAR >* >& pool,
247  const Sequence< PRMInstance< GUM_SCALAR >* >& match);
248  std::pair< Size, Size >
249  __elimination_cost(typename StrictSearch< GUM_SCALAR >::PData& data,
250  Set< Potential< GUM_SCALAR >* >& pool);
251  };
252 
262  template < typename GUM_SCALAR >
263  class TreeWidthSearch : public SearchStrategy< GUM_SCALAR > {
264  public:
265  // =========================================================================
267  // ==========================================================================
269 
271  TreeWidthSearch();
272 
274  TreeWidthSearch(const TreeWidthSearch& from);
275 
277  virtual ~TreeWidthSearch();
278 
280  TreeWidthSearch& operator=(const TreeWidthSearch& from);
281 
283  // =========================================================================
285  // ==========================================================================
287 
288  double cost(const Pattern& p);
289 
290  virtual bool accept_root(const Pattern* r);
291 
292  virtual bool accept_growth(const Pattern* parent,
293  const Pattern* child,
294  const EdgeGrowth< GUM_SCALAR >& growth);
295 
296  virtual bool operator()(LabelData* i, LabelData* j);
297  virtual bool operator()(Pattern* i, Pattern* j);
299 
300  private:
301  HashTable< const Pattern*, double > __map;
302  };
303 
304 
305 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
306 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
307 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
308 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
309  extern template class SearchStrategy< double >;
310 # endif
311 # endif
312 # endif
313 #endif
314 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
315 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
316 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
317 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
318  extern template class FrequenceSearch< double >;
319 # endif
320 # endif
321 # endif
322 #endif
323 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
324 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
325 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
326 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
327  extern template class StrictSearch< double >;
328 # endif
329 # endif
330 # endif
331 #endif
332 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
333 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
334 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
335 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
336  extern template class TreeWidthSearch< double >;
337 # endif
338 # endif
339 # endif
340 #endif
341 
342 
343  } /* namespace gspan */
344  } /* namespace prm */
345 } /* namespace gum */
346 
347 #include <agrum/PRM/gspan/searchStrategy_tpl.h>
348 
349 #endif /* GUM_DFS_TREE_H */
math.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::SearchStrategy::setTree
void setTree(DFSTree< GUM_SCALAR > *tree)
Definition: searchStrategy_tpl.h:233
gum::Potential
aGrUM&#39;s Potential is a multi-dimensional array with tensor operators.
Definition: potential.h:60
gum::prm::gspan::EdgeGrowth
This class is used to define an edge growth of a pattern in this DFSTree.
Definition: edgeGrowth.h:63
diGraph.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::StrictSearch::PData::inners
NodeSet inners
Returns the set of inner nodes.
Definition: searchStrategy.h:233
sequence.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
set.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::LabelData
Inner class to handle data about labels in this interface graph.
Definition: interfaceGraph.h:51
gum::prm::PRMInstance
An PRMInstance is a Bayesian Network fragment defined by a Class and used in a PRMSystem.
Definition: PRMInstance.h:63
gum::Sequence
The generic class for storing (ordered) sequences of objects.
Definition: sequence.h:1022
gum::prm::gspan::StrictSearch::PData::graph
UndiGraph graph
A yet to be triangulated undigraph.
Definition: searchStrategy.h:220
gum::prm::gspan::StrictSearch::PData::vars
Bijection< NodeId, const DiscreteVariable *> vars
Bijection between graph&#39;s nodes and their corresponding DiscreteVariable, for inference purpose...
Definition: searchStrategy.h:231
gum
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Definition: agrum.h:25
gum::HashTable
The class for generic Hash Tables.
Definition: hashTable.h:679
gum::prm::gspan::SearchStrategy::_tree
DFSTree< GUM_SCALAR > * _tree
Definition: searchStrategy.h:112
gum::prm::gspan::SearchStrategy::accept_growth
virtual bool accept_growth(const Pattern *parent, const Pattern *child, const EdgeGrowth< GUM_SCALAR > &growth)=0
gum::prm::gspan::DFSTree
A DFSTree is used by gspan to sort lexicographically patterns discovered in an interface graph...
Definition: DFSTree.h:71
gum::prm::gspan::TreeWidthSearch
A growth is accepted if and only if the new growth has a tree width less large or equal than its fath...
Definition: searchStrategy.h:263
gum::prm::gspan::TreeWidthSearch::__map
HashTable< const Pattern *, double > __map
Definition: searchStrategy.h:301
gum::prm::gspan::StrictSearch::PData::outputs
NodeSet outputs
Returns the set of outputs nodes given all the matches of pattern.
Definition: searchStrategy.h:235
gum::prm::gspan::SearchStrategy::accept_root
virtual bool accept_root(const Pattern *r)=0
gum::prm::gspan::StrictSearch::PData::node2attr
Bijection< NodeId, std::string > node2attr
A bijection to easily keep track between graph and attributes, its of the form instance_name DOT attr...
Definition: searchStrategy.h:227
edgeGrowth.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::StrictSearch::PData::mod
NodeProperty< Size > mod
The pattern&#39;s variables modalities.
Definition: searchStrategy.h:222
gum::prm::PRMSlotChain
A PRMSlotChain represents a sequence of gum::prm::PRMClassElement<GUM_SCALAR> where the n-1 first gum...
Definition: PRMObject.h:221
gum::prm::gspan::StrictSearch::PData
Private structure to represent data about a pattern.
Definition: searchStrategy.h:218
searchStrategy_tpl.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::StrictSearch::__map
HashTable< const Pattern *, std::pair< double, double > > __map
Definition: searchStrategy.h:216
gum::prm::gspan::StrictSearch
This is class is an implementation of a strict strategy for the GSpan algorithm.
Definition: searchStrategy.h:176
partialOrderedTriangulation.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::FrequenceSearch
This is class is an implementation of a simple serach strategy for the gspan algorithm: it accept a g...
Definition: searchStrategy.h:126
gum::prm::gspan::SearchStrategy::_computeCost
double _computeCost(const Pattern &p)
Definition: searchStrategy_tpl.h:36
gum::UndiGraph
Base class for undirected graphs.
Definition: undiGraph.h:109
interfaceGraph.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::PRMAttribute
PRMAttribute is a member of a Class in a PRM.
Definition: PRMAttribute.h:61
gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
pattern.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::SearchStrategy::operator()
virtual bool operator()(LabelData *i, LabelData *j)=0
gum::prm::gspan::Pattern
This contains all the information we want for a node in a DFSTree.
Definition: pattern.h:73
gum::prm::gspan::SearchStrategy
This is an abstract class used to tune search strategies in the gspan algorithm.
Definition: DFSTree.h:61
bijection.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::prm::gspan::SearchStrategy::operator=
SearchStrategy< GUM_SCALAR > & operator=(const SearchStrategy< GUM_SCALAR > &from)
Copy operator.
Definition: searchStrategy_tpl.h:226
aGrUM 0.16.0
Tue Aug 27 2019 12:07:07
© CG&PHW&others - LIP6 2005-2007-2012
DoXyGeN 1.8.13