Generated on Wed Jan 24 2018 21:22:26 for Gecode by doxygen 1.8.13
lds.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2004, 2016
8  *
9  * Bugfixes provided by:
10  * Stefano Gualandi
11  *
12  * Last modified:
13  * $Date: 2016-09-22 16:19:20 +0200 (Thu, 22 Sep 2016) $ by $Author: schulte $
14  * $Revision: 15169 $
15  *
16  * This file is part of Gecode, the generic constraint
17  * development environment:
18  * http://www.gecode.org
19  *
20  * Permission is hereby granted, free of charge, to any person obtaining
21  * a copy of this software and associated documentation files (the
22  * "Software"), to deal in the Software without restriction, including
23  * without limitation the rights to use, copy, modify, merge, publish,
24  * distribute, sublicense, and/or sell copies of the Software, and to
25  * permit persons to whom the Software is furnished to do so, subject to
26  * the following conditions:
27  *
28  * The above copyright notice and this permission notice shall be
29  * included in all copies or substantial portions of the Software.
30  *
31  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38  *
39  */
40 
42 
43 namespace Gecode { namespace Search { namespace Sequential {
44 
45  /*
46  * The probing engine: computes all solutions with
47  * exact number of discrepancies (solutions with
48  * fewer discrepancies are discarded)
49  *
50  */
51  Space*
52  LDS::next(void) {
53  while (true) {
54  Space* s = e.next(opt);
55  if (s != NULL)
56  return s;
57  if (((s == NULL) && e.stopped()) || (++d > opt.d_l) || e.done())
58  break;
59  if (d == opt.d_l) {
60  if (root != NULL)
61  e.reset(root,d);
62  root = NULL;
63  } else if (root != NULL) {
64  e.reset(root->clone(),d);
65  }
66  }
67  return NULL;
68  }
69 
70  bool
71  LDS::stopped(void) const {
72  return e.stopped();
73  }
74 
76  LDS::statistics(void) const {
77  return e.statistics();
78  }
79 
80  LDS::~LDS(void) {
81  delete root;
82  }
83 
84 }}}
85 
86 // STATISTICS: search-sequential
Search engine statistics
Definition: search.hh:140
Space * root
Root node for problem.
Definition: lds.hh:106
Space * next(const Options &o)
Search for next solution
Definition: lds.hh:205
unsigned int d
Current discrepancy.
Definition: lds.hh:108
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3326
bool stopped(void) const
Check whether engine has been stopped.
Definition: worker.hh:91
Computation spaces.
Definition: core.hpp:1748
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:457
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: lds.cpp:52
void reset(Space *s, unsigned int d)
Reset with space s and discrepancy d.
Definition: lds.hh:179
Statistics statistics(void) const
Return statistics.
Definition: lds.hh:188
Options opt
Search options.
Definition: lds.hh:102
Probe e
The probe engine.
Definition: lds.hh:104
Gecode toplevel namespace
virtual Statistics statistics(void) const
Return statistics.
Definition: lds.cpp:76
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: lds.cpp:71
virtual ~LDS(void)
Destructor.
Definition: lds.cpp:80
bool done(void) const
Test whether probing is done.
Definition: lds.hh:193