Generated on Fri Aug 31 2012 16:21:37 for Gecode by doxygen 1.8.1.2
brancher-view.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main author:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2008
8  *
9  * Last modified:
10  * $Date: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
11  * $Revision: 12001 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode {
39 
46 
48  public:
50  size_t size(void) const;
52  void archive(Archive& e) const;
53  };
54 
58  template<class _View>
59  class ViewSelBase {
60  public:
62  typedef _View View;
66  ViewSelBase(void);
68  ViewSelBase(Space& home, const VarBranchOptions& vbo);
72  EmptyViewSelChoice choice(const Space& home, Archive& e);
74  void commit(Space& home, const EmptyViewSelChoice& c, unsigned a);
76  void update(Space& home, bool share, ViewSelBase& vs);
78  void dispose(Space& home);
79  };
80 
84  template<class View>
85  class ViewSelNone : public ViewSelBase<View> {
86  public:
88  ViewSelNone(void);
90  ViewSelNone(Space& home, const VarBranchOptions& vbo);
92  ViewSelStatus init(Space& home, View x);
94  ViewSelStatus select(Space& home, View x);
95  };
96 
100  template<class View>
101  class ViewSelDegreeMin : public ViewSelBase<View> {
102  protected:
104  unsigned int degree;
105  public:
107  ViewSelDegreeMin(void);
109  ViewSelDegreeMin(Space& home, const VarBranchOptions& vbo);
111  ViewSelStatus init(Space& home, View x);
113  ViewSelStatus select(Space& home, View x);
114  };
115 
119  template<class View>
120  class ViewSelDegreeMax : public ViewSelBase<View> {
121  protected:
123  unsigned int degree;
124  public:
126  ViewSelDegreeMax(void);
128  ViewSelDegreeMax(Space& home, const VarBranchOptions& vbo);
130  ViewSelStatus init(Space& home, View x);
132  ViewSelStatus select(Space& home, View x);
133  };
134 
138  template<class View>
139  class ViewSelAfcMin : public ViewSelBase<View> {
140  protected:
142  double afc;
143  public:
145  ViewSelAfcMin(void);
147  ViewSelAfcMin(Space& home, const VarBranchOptions& vbo);
149  ViewSelStatus init(Space& home, View x);
151  ViewSelStatus select(Space& home, View x);
152  };
153 
157  template<class View>
158  class ViewSelAfcMax : public ViewSelBase<View> {
159  protected:
161  double afc;
162  public:
164  ViewSelAfcMax(void);
166  ViewSelAfcMax(Space& home, const VarBranchOptions& vbo);
168  ViewSelStatus init(Space& home, View x);
170  ViewSelStatus select(Space& home, View x);
171  };
172 
175  public:
179  ArchivedRandomGenerator(unsigned int seed);
183  void archive(Archive& e) const;
184  };
185 
189  template<class _View>
190  class ViewSelRnd {
191  protected:
195  unsigned int n;
196  public:
198  typedef _View View;
202  ViewSelRnd(void);
204  ViewSelRnd(Space& home, const VarBranchOptions& vbo);
206  ViewSelStatus init(Space& home, _View x);
208  ViewSelStatus select(Space& home, _View x);
210  Choice choice(Space& home);
212  Choice choice(const Space& home, Archive& e);
214  void commit(Space& home, const Choice& c, unsigned a);
216  void update(Space& home, bool share, ViewSelRnd& vs);
218  void dispose(Space& home);
219  };
221 
222  // Empty view selection choice
223  forceinline size_t
225  return sizeof(EmptyViewSelChoice);
226  }
227 
228  forceinline void
229  EmptyViewSelChoice::archive(Archive& e) const { (void)e; }
230 
231  // Selection base class
232  template<class View>
235  template<class View>
238  template<class View>
241  EmptyViewSelChoice c; return c;
242  }
243  template<class View>
246  EmptyViewSelChoice c; return c;
247  }
248  template<class View>
249  forceinline void
251  template<class View>
252  forceinline void
254  template<class View>
255  forceinline void
257 
258 
259  // Select first view
260  template<class View>
263  template<class View>
266  : ViewSelBase<View>(home,vbo) {}
267  template<class View>
270  return VSS_BEST;
271  }
272  template<class View>
275  return VSS_BEST;
276  }
277 
278 
279  // Select variable with smallest degree
280  template<class View>
283  template<class View>
286  const VarBranchOptions& vbo)
287  : ViewSelBase<View>(home,vbo), degree(0U) {}
288  template<class View>
291  degree = x.degree();
292  return (degree == 0) ? VSS_BEST : VSS_BETTER;
293  }
294  template<class View>
297  if (x.degree() < degree) {
298  degree = x.degree();
299  return (degree == 0) ? VSS_BEST : VSS_BETTER;
300  } else if (x.degree() > degree) {
301  return VSS_WORSE;
302  } else {
303  return VSS_TIE;
304  }
305  }
306 
307 
308  // Select variable with largest degree
309  template<class View>
312  template<class View>
315  const VarBranchOptions& vbo)
316  : ViewSelBase<View>(home,vbo), degree(0U) {}
317  template<class View>
320  degree = x.degree();
321  return VSS_BETTER;
322  }
323  template<class View>
326  if (x.degree() > degree) {
327  degree = x.degree();
328  return VSS_BETTER;
329  } else if (x.degree() < degree) {
330  return VSS_WORSE;
331  } else {
332  return VSS_TIE;
333  }
334  }
335 
336 
337  // Select variable with smallest afc
338  template<class View>
341  template<class View>
344  const VarBranchOptions& vbo)
345  : ViewSelBase<View>(home,vbo), afc(0.0) {}
346  template<class View>
349  afc = x.afc();
350  return (afc == 0.0) ? VSS_BEST : VSS_BETTER;
351  }
352  template<class View>
355  if (x.afc() < afc) {
356  afc = x.afc();
357  return (afc == 0.0) ? VSS_BEST : VSS_BETTER;
358  } else if (x.afc() > afc) {
359  return VSS_WORSE;
360  } else {
361  return VSS_TIE;
362  }
363  }
364 
365 
366  // Select variable with largest afc
367  template<class View>
370  template<class View>
373  const VarBranchOptions& vbo)
374  : ViewSelBase<View>(home,vbo), afc(0.0) {}
375  template<class View>
378  afc = x.afc();
379  return VSS_BETTER;
380  }
381  template<class View>
384  double xafc = x.afc();
385  if (xafc > afc) {
386  afc = xafc;
387  return VSS_BETTER;
388  } else if (xafc < afc) {
389  return VSS_WORSE;
390  } else {
391  return VSS_TIE;
392  }
393  }
394 
395 
396  // Archived random generator
401  : Support::RandomGenerator(seed) {}
405  forceinline void
407 
408  // Select variable by random
409  template<class View>
412  template<class View>
415  : r(vbo.seed), n(0) {}
416  template<class View>
419  n=1;
420  return VSS_BETTER;
421  }
422  template<class View>
425  n++;
426  return (r(n) == (n-1)) ? VSS_BETTER : VSS_WORSE;
427  }
428  template<class View>
431  return r;
432  }
433  template<class View>
436  return Choice(e.get());
437  }
438  template<class View>
439  forceinline void
440  ViewSelRnd<View>::commit(Space&, const Choice& c, unsigned int) {
441  r = c;
442  }
443  template<class View>
444  forceinline void
446  r = vs.r;
447  }
448  template<class View>
449  forceinline void
451  }
452 
453 }
454 
455 // STATISTICS: kernel-branch