aGrUM  0.20.3
a C++ library for (probabilistic) graphical models
searchStrategy.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright (c) 2005-2021 by 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 >& operator=(const SearchStrategy< GUM_SCALAR >& from);
90 
91  /// @}
92  // =========================================================================
93  /// @name Search methods.
94  // ==========================================================================
95  /// @{
96 
97  void setTree(DFSTree< GUM_SCALAR >* tree);
98 
99  virtual bool accept_root(const Pattern* r) = 0;
100 
101  virtual bool accept_growth(const Pattern* parent,
102  const Pattern* child,
103  const EdgeGrowth< GUM_SCALAR >& growth)
104  = 0;
105 
106  virtual bool operator()(LabelData* i, LabelData* j) = 0;
107  virtual bool operator()(Pattern* i, Pattern* j) = 0;
108  /// @}
109 
110  protected:
111  DFSTree< GUM_SCALAR >* tree_;
112  double computeCost_(const Pattern& p);
113  };
114 
115  /**
116  * @class FrequenceSearch
117  * @headerfile DFSTree.h <agrum/PRM/gspan/DFSTree.h>
118  *
119  * This is class is an implementation of a simple serach strategy for the
120  *gspan
121  * algorithm: it accept a growth if its frequency is above a user defined
122  *value.
123  */
124  template < typename GUM_SCALAR >
125  class FrequenceSearch: public SearchStrategy< GUM_SCALAR > {
126  public:
127  // =========================================================================
128  /// @name Constructor and destructor.
129  // ==========================================================================
130  /// @{
131 
132  /// Default constructor.
133  explicit FrequenceSearch(Size freq);
134 
135  /// Copy constructor.
136  FrequenceSearch(const FrequenceSearch& from);
137 
138  /// Destructor.
139  virtual ~FrequenceSearch();
140 
141  /// Copy operator.
142  FrequenceSearch& operator=(const FrequenceSearch& from);
143 
144  /// @}
145  // =========================================================================
146  /// @name Search methods.
147  // ==========================================================================
148  /// @{
149 
150  virtual bool accept_root(const Pattern* r);
151 
152  virtual bool accept_growth(const Pattern* parent,
153  const Pattern* child,
154  const EdgeGrowth< GUM_SCALAR >& growth);
155 
156  virtual bool operator()(LabelData* i, LabelData* j);
157  virtual bool operator()(Pattern* i, Pattern* j);
158  /// @}
159 
160  private:
161  Size _freq_;
162  };
163 
164  /**
165  * @class StrictSearch
166  * @headerfile DFSTree.h <agrum/PRM/gspan/DFSTree.h>
167  *
168  * This is class is an implementation of a strict strategy for the GSpan
169  * algorithm. This will force early cuts in the DFSTree and should help
170  * not spending much time searching for new patterns.
171  *
172  * A new growth is accepted if it is at least better than its predecessor.
173  */
174  template < typename GUM_SCALAR >
175  class StrictSearch: public SearchStrategy< GUM_SCALAR > {
176  public:
177  // =========================================================================
178  /// @name Constructor and destructor.
179  // ==========================================================================
180  /// @{
181 
182  /// Default constructor.
183  explicit StrictSearch(Size freq = 2);
184 
185  /// Copy constructor.
186  StrictSearch(const StrictSearch& from);
187 
188  /// Destructor.
189  virtual ~StrictSearch();
190 
191  /// Copy operator.
192  StrictSearch& operator=(const StrictSearch& from);
193 
194  /// @}
195  // =========================================================================
196  /// @name Search methods.
197  // ==========================================================================
198  /// @{
199 
200  virtual bool accept_root(const Pattern* r);
201 
202  virtual bool accept_growth(const Pattern* parent,
203  const Pattern* child,
204  const EdgeGrowth< GUM_SCALAR >& growth);
205 
206  virtual bool operator()(LabelData* i, LabelData* j);
207  virtual bool operator()(Pattern* i, Pattern* j);
208  /// @}
209 
210  private:
211  Size _freq_;
212  double _inner_cost_(const Pattern* p);
213  double _outer_cost_(const Pattern* p);
214  void _compute_costs_(const Pattern* p);
215  HashTable< const Pattern*, std::pair< double, double > > _map_;
216  /// Private structure to represent data about a pattern.
217  struct PData {
218  /// A yet to be triangulated undigraph
219  UndiGraph graph;
220  /// The pattern's variables modalities
221  NodeProperty< Size > mod;
222  /// A bijection to easily keep track between graph and attributes,
223  /// its of
224  /// the
225  /// form instance_name DOT attr_name
226  Bijection< NodeId, std::string > node2attr;
227  /// Bijection between graph's nodes and their corresponding
228  /// DiscreteVariable, for
229  /// inference purpose
230  Bijection< NodeId, const DiscreteVariable* > vars;
231  /// Returns the set of inner nodes
232  NodeSet inners;
233  /// Returns the set of outputs nodes given all the matches of pattern
234  NodeSet outputs;
235  };
236  std::string _dot_;
237  std::string _str_(const PRMInstance< GUM_SCALAR >* i,
238  const PRMAttribute< GUM_SCALAR >* a) const;
239  std::string _str_(const PRMInstance< GUM_SCALAR >* i,
240  const PRMAttribute< GUM_SCALAR >& a) const;
241  std::string _str_(const PRMInstance< GUM_SCALAR >* i,
242  const PRMSlotChain< GUM_SCALAR >& a) const;
243  void _buildPatternGraph_(typename StrictSearch< GUM_SCALAR >::PData& data,
244  Set< Potential< GUM_SCALAR >* >& pool,
245  const Sequence< PRMInstance< GUM_SCALAR >* >& match);
246  std::pair< Size, Size > _elimination_cost_(typename StrictSearch< GUM_SCALAR >::PData& data,
247  Set< Potential< GUM_SCALAR >* >& pool);
248  };
249 
250  /**
251  * @class TreeWidthSearch
252  * @headerfile DFSTree.h <agrum/PRM/gspan/DFSTree.h>
253  *
254  * A growth is accepted if and only if the new growth has a tree width
255  *less
256  *large
257  * or equal than its father.
258  */
259  template < typename GUM_SCALAR >
260  class TreeWidthSearch: public SearchStrategy< GUM_SCALAR > {
261  public:
262  // =========================================================================
263  /// @name Constructor and destructor.
264  // ==========================================================================
265  /// @{
266 
267  /// Default constructor.
268  TreeWidthSearch();
269 
270  /// Copy constructor.
271  TreeWidthSearch(const TreeWidthSearch& from);
272 
273  /// Destructor.
274  virtual ~TreeWidthSearch();
275 
276  /// Copy operator.
277  TreeWidthSearch& operator=(const TreeWidthSearch& from);
278 
279  /// @}
280  // =========================================================================
281  /// @name Search methods.
282  // ==========================================================================
283  /// @{
284 
285  double cost(const Pattern& p);
286 
287  virtual bool accept_root(const Pattern* r);
288 
289  virtual bool accept_growth(const Pattern* parent,
290  const Pattern* child,
291  const EdgeGrowth< GUM_SCALAR >& growth);
292 
293  virtual bool operator()(LabelData* i, LabelData* j);
294  virtual bool operator()(Pattern* i, Pattern* j);
295  /// @}
296 
297  private:
298  HashTable< const Pattern*, double > _map_;
299  };
300 
301 
302 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
303 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
304 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
305 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
306  extern template class SearchStrategy< double >;
307 # endif
308 # endif
309 # endif
310 #endif
311 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
312 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
313 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
314 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
315  extern template class FrequenceSearch< double >;
316 # endif
317 # endif
318 # endif
319 #endif
320 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
321 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
322 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
323 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
324  extern template class StrictSearch< double >;
325 # endif
326 # endif
327 # endif
328 #endif
329 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
330 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
331 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
332 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
333  extern template class TreeWidthSearch< double >;
334 # endif
335 # endif
336 # endif
337 #endif
338 
339 
340  } /* namespace gspan */
341  } /* namespace prm */
342 } /* namespace gum */
343 
344 #include <agrum/PRM/gspan/searchStrategy_tpl.h>
345 
346 #endif /* GUM_DFS_TREE_H */
aGrUM 0.20.3
Mon Jun 7 2021 17:34:01
© PHW&CG&others - 2021
DoXyGeN 1.8.13