Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
nogoods.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, 2013
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/search/nogoods.hh>
35 
36 namespace Gecode { namespace Search {
37 
39  forceinline NGL*
40  disposenext(NGL* ngl, Space& home, Propagator& p, bool c) {
41  NGL* n = ngl->next();
42  if (c)
43  ngl->cancel(home,p);
44  home.rfree(ngl,ngl->dispose(home));
45  return n;
46  }
47 
48  void
51  }
52  void
55  }
56  void
59  }
61  NoNGL::status(const Space&) const {
63  return NGL::NONE;
64  }
68  return ES_OK;
69  }
70  NGL*
73  return NULL;
74  }
75 
76  Actor*
78  return new (home) NoGoodsProp(home,*this);
79  }
80 
81  PropCost
82  NoGoodsProp::cost(const Space&, const ModEventDelta&) const {
84  }
85 
86  void
88  root->reschedule(home,*this);
89  NGL* l = root->next();
90  while ((l != NULL) && l->leaf()) {
91  l->reschedule(home,*this);
92  l = l->next();
93  }
94  if (l != NULL)
95  l->reschedule(home,*this);
96  }
97 
98 
101  restart:
102  // Start with checking the first literal
103  switch (root->status(home)) {
104  case NGL::FAILED:
105  // All no-goods are dead, let dispose() clean up
106  return home.ES_SUBSUMED(*this);
107  case NGL::SUBSUMED:
108  {
109  NGL* l = disposenext(root,home,*this,true); n--;
110  // Prune leaf-literals
111  while ((l != NULL) && l->leaf()) {
112  l->cancel(home,*this); n--;
113  GECODE_ES_CHECK(l->prune(home));
114  l = disposenext(l,home,*this,false);
115  }
116  root = l;
117  // Is there anything left?
118  if (l == NULL)
119  return home.ES_SUBSUMED(*this);
120  // Skip literal that already has a subscription
121  l = l->next();
122  // Create subscriptions for leafs
123  while ((l != NULL) && l->leaf()) {
124  l->subscribe(home,*this); n++;
125  l = l->next();
126  }
127  // Create subscription for possible non-leaf literal
128  if (l != NULL) {
129  l->subscribe(home,*this); n++;
130  }
131  goto restart;
132  }
133  case NGL::NONE:
134  break;
135  default: GECODE_NEVER;
136  }
137 
138  {
139  NGL* p = root;
140  NGL* l = p->next();
141 
142  // Check the leaves
143  while ((l != NULL) && l->leaf()) {
144  switch (l->status(home)) {
145  case NGL::SUBSUMED:
146  l = disposenext(l,home,*this,true); n--;
147  p->next(l);
148  GECODE_ES_CHECK(root->prune(home));
149  if (root->status(home) == NGL::FAILED)
150  return home.ES_SUBSUMED(*this);
151  break;
152  case NGL::FAILED:
153  l = disposenext(l,home,*this,true); n--;
154  p->next(l);
155  break;
156  case NGL::NONE:
157  p = l; l = l->next();
158  break;
159  default: GECODE_NEVER;
160  }
161  }
162 
163  // Check the next subtree
164  if (l != NULL) {
165  switch (l->status(home)) {
166  case NGL::FAILED:
167  (void) disposenext(l,home,*this,true); n--;
168  // Prune entire subtree
169  p->next(NULL);
170  break;
171  case NGL::SUBSUMED:
172  {
173  // Unlink node
174  l = disposenext(l,home,*this,true); n--;
175  p->next(l);
176  // Create subscriptions
177  while ((l != NULL) && l->leaf()) {
178  l->subscribe(home,*this); n++;
179  l = l->next();
180  }
181  if (l != NULL) {
182  l->subscribe(home,*this); n++;
183  }
184  }
185  break;
186  case NGL::NONE:
187  break;
188  default: GECODE_NEVER;
189  }
190  }
191  }
192  return ES_NOFIX;
193  }
194 
195  size_t
197  if (home.failed()) {
198  // This will be executed when one ngl returned true for notice()
199  NGL* l = root;
200  while (l != NULL) {
201  NGL* t = l->next();
202  (void) l->dispose(home);
203  l = t;
204  }
205  } else if (root != NULL) {
206  // This will be executed for subsumption
207  NGL* l = disposenext(root,home,*this,true);
208  while ((l != NULL) && l->leaf())
209  l = disposenext(l,home,*this,true);
210  if (l != NULL)
211  l = disposenext(l,home,*this,true);
212  while (l != NULL)
213  l = disposenext(l,home,*this,false);
214  }
215  home.ignore(*this,AP_DISPOSE,true);
216  (void) Propagator::dispose(home);
217  return sizeof(*this);
218  }
219 
220 }}
221 
222 // STATISTICS: search-other
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Base-class for both propagators and branchers.
Definition: core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
No-good literal recorded during search.
Definition: core.hpp:1340
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
virtual void cancel(Space &home, Propagator &p)=0
Cancel propagator p from all views of the no-good literal.
virtual NGL::Status status(const Space &home) const =0
Test the status of the no-good literal.
Status
The status of a no-good literal.
Definition: core.hpp:1346
@ SUBSUMED
The literal is subsumed.
Definition: core.hpp:1348
@ FAILED
The literal is failed.
Definition: core.hpp:1347
@ NONE
The literal is neither failed nor subsumed.
Definition: core.hpp:1349
virtual void reschedule(Space &home, Propagator &p)=0
Schedule propagator p for all views of the no-good literal.
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3793
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3821
Propagation cost.
Definition: core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4796
@ LO
Cheap.
Definition: core.hpp:513
Base-class for propagators.
Definition: core.hpp:1064
unsigned int n
Number of no-good literals with subscriptions.
Definition: nogoods.hh:70
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: nogoods.cpp:196
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nogoods.cpp:100
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition: nogoods.cpp:77
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Const function (defined as low unary)
Definition: nogoods.cpp:82
NoGoodsProp(Space &home, NGL *root)
Constructor for creation.
Definition: nogoods.hpp:50
virtual void reschedule(Space &home)
Schedule function.
Definition: nogoods.cpp:87
NGL * root
Root of no-good literal tree.
Definition: nogoods.hh:68
virtual NGL::Status status(const Space &home) const
Test the status of the no-good literal.
Definition: nogoods.cpp:61
virtual ExecStatus prune(Space &home)
Propagate the negation of the no-good literal.
Definition: nogoods.cpp:66
virtual NGL * copy(Space &home)
Create copy.
Definition: nogoods.cpp:71
virtual void cancel(Space &home, Propagator &p)
Cancel propagator p from all views of the no-good literal.
Definition: nogoods.cpp:53
virtual void reschedule(Space &home, Propagator &p)
Schedule propagator p for all views of the no-good literal.
Definition: nogoods.cpp:57
virtual void subscribe(Space &home, Propagator &p)
Subscribe propagator p to all views of the no-good literal.
Definition: nogoods.cpp:49
Computation spaces.
Definition: core.hpp:1742
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2803
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4044
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
NGL * disposenext(NGL *ngl, Space &home, Propagator &p, bool c)
Help function to cancel and dispose a no-good literal.
Definition: nogoods.cpp:40
#define forceinline
Definition: config.hpp:185
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56