aGrUM  0.20.2
a C++ library for (probabilistic) graphical models
searchStrategy.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
4  * info_at_agrum_dot_org
5  *
6  * This library is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this library. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief Headers of the SearchStrategy class and child
25  *
26  * @author Lionel TORTI and Pierre-Henri WUILLEMIN(@LIP6)
27  */
28 
29 #ifndef GUM_SEARCHSTRATEGY_H
30 #define GUM_SEARCHSTRATEGY_H
31 
32 #include <list>
33 #include <ostream>
34 #include <utility>
35 #include <vector>
36 
37 #include <agrum/tools/core/math/math_utils.h>
38 #include <agrum/tools/core/bijection.h>
39 #include <agrum/tools/core/sequence.h>
40 #include <agrum/tools/core/set.h>
41 
42 #include <agrum/tools/graphs/diGraph.h>
43 
44 #include <agrum/tools/graphs/algorithms/triangulations/partialOrderedTriangulation.h>
45 
46 #include <agrum/PRM/gspan/edgeGrowth.h>
47 #include <agrum/PRM/gspan/interfaceGraph.h>
48 #include <agrum/PRM/gspan/pattern.h>
49 
50 namespace gum {
51  namespace prm {
52 
53  template < typename GUM_SCALAR >
54  class GSpan;
55 
56  namespace gspan {
57  template < typename GUM_SCALAR >
58  class DFSTree;
59 
60  // clang_format off
61  /**
62  * @class SearchStrategy
63  * @headerfile searchStrategy.h <agrum/PRM/gspan/searchStrategy.h>
64  *
65  * This is an abstract class used to tune search strategies in the gspan
66  * algorithm. Since GSpan uses a DFS to expand the search tree, this class
67  * works as a stack regarding adding and removing informations about the
68  * growths.
69  */
70  // clang_format on
71  template < typename GUM_SCALAR >
72  class SearchStrategy {
73  public:
74  // =========================================================================
75  /// @name Constructor and destructor.
76  // ==========================================================================
77  /// @{
78 
79  /// Default constructor.
80  SearchStrategy< GUM_SCALAR >();
81 
82  /// Copy constructor.
83  SearchStrategy< GUM_SCALAR >(const SearchStrategy< GUM_SCALAR >& from);
84 
85  /// Destructor.
86  virtual ~SearchStrategy< GUM_SCALAR >();
87 
88  /// Copy operator.
89  SearchStrategy< GUM_SCALAR >&
90  operator=(const SearchStrategy< GUM_SCALAR >& from);
91 
92  /// @}
93  // =========================================================================
94  /// @name Search methods.
95  // ==========================================================================
96  /// @{
97 
98  void setTree(DFSTree< GUM_SCALAR >* tree);
99 
100  virtual bool accept_root(const Pattern* r) = 0;
101 
102  virtual bool accept_growth(const Pattern* parent,
103  const Pattern* child,
104  const EdgeGrowth< GUM_SCALAR >& growth)
105  = 0;
106 
107  virtual bool operator()(LabelData* i, LabelData* j) = 0;
108  virtual bool operator()(Pattern* i, Pattern* j) = 0;
109  /// @}
110 
111  protected:
112  DFSTree< GUM_SCALAR >* tree_;
113  double computeCost_(const Pattern& p);
114  };
115 
116  /**
117  * @class FrequenceSearch
118  * @headerfile DFSTree.h <agrum/PRM/gspan/DFSTree.h>
119  *
120  * This is class is an implementation of a simple serach strategy for the
121  *gspan
122  * algorithm: it accept a growth if its frequency is above a user defined
123  *value.
124  */
125  template < typename GUM_SCALAR >
126  class FrequenceSearch: public SearchStrategy< GUM_SCALAR > {
127  public:
128  // =========================================================================
129  /// @name Constructor and destructor.
130  // ==========================================================================
131  /// @{
132 
133  /// Default constructor.
134  explicit FrequenceSearch(Size freq);
135 
136  /// Copy constructor.
137  FrequenceSearch(const FrequenceSearch& from);
138 
139  /// Destructor.
140  virtual ~FrequenceSearch();
141 
142  /// Copy operator.
143  FrequenceSearch& operator=(const FrequenceSearch& from);
144 
145  /// @}
146  // =========================================================================
147  /// @name Search methods.
148  // ==========================================================================
149  /// @{
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);
159  /// @}
160 
161  private:
162  Size freq__;
163  };
164 
165  /**
166  * @class StrictSearch
167  * @headerfile DFSTree.h <agrum/PRM/gspan/DFSTree.h>
168  *
169  * This is class is an implementation of a strict strategy for the GSpan
170  * algorithm. This will force early cuts in the DFSTree and should help
171  * not spending much time searching for new patterns.
172  *
173  * A new growth is accepted if it is at least better than its predecessor.
174  */
175  template < typename GUM_SCALAR >
176  class StrictSearch: public SearchStrategy< GUM_SCALAR > {
177  public:
178  // =========================================================================
179  /// @name Constructor and destructor.
180  // ==========================================================================
181  /// @{
182 
183  /// Default constructor.
184  explicit StrictSearch(Size freq = 2);
185 
186  /// Copy constructor.
187  StrictSearch(const StrictSearch& from);
188 
189  /// Destructor.
190  virtual ~StrictSearch();
191 
192  /// Copy operator.
193  StrictSearch& operator=(const StrictSearch& from);
194 
195  /// @}
196  // =========================================================================
197  /// @name Search methods.
198  // ==========================================================================
199  /// @{
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);
209  /// @}
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__;
217  /// Private structure to represent data about a pattern.
218  struct PData {
219  /// A yet to be triangulated undigraph
220  UndiGraph graph;
221  /// The pattern's variables modalities
222  NodeProperty< Size > mod;
223  /// A bijection to easily keep track between graph and attributes,
224  /// its of
225  /// the
226  /// form instance_name DOT attr_name
227  Bijection< NodeId, std::string > node2attr;
228  /// Bijection between graph's nodes and their corresponding
229  /// DiscreteVariable, for
230  /// inference purpose
231  Bijection< NodeId, const DiscreteVariable* > vars;
232  /// Returns the set of inner nodes
233  NodeSet inners;
234  /// Returns the set of outputs nodes given all the matches of pattern
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 
253  /**
254  * @class TreeWidthSearch
255  * @headerfile DFSTree.h <agrum/PRM/gspan/DFSTree.h>
256  *
257  * A growth is accepted if and only if the new growth has a tree width
258  *less
259  *large
260  * or equal than its father.
261  */
262  template < typename GUM_SCALAR >
263  class TreeWidthSearch: public SearchStrategy< GUM_SCALAR > {
264  public:
265  // =========================================================================
266  /// @name Constructor and destructor.
267  // ==========================================================================
268  /// @{
269 
270  /// Default constructor.
271  TreeWidthSearch();
272 
273  /// Copy constructor.
274  TreeWidthSearch(const TreeWidthSearch& from);
275 
276  /// Destructor.
277  virtual ~TreeWidthSearch();
278 
279  /// Copy operator.
280  TreeWidthSearch& operator=(const TreeWidthSearch& from);
281 
282  /// @}
283  // =========================================================================
284  /// @name Search methods.
285  // ==========================================================================
286  /// @{
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);
298  /// @}
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 */
aGrUM 0.20.2
Sun May 2 2021 12:35:55
© PHW&CG&others - 2021
DoXyGeN 1.8.13