Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
35
36namespace 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
52 void
56 void
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
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.
NodeType t
Type of node.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
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
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 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
Gecode toplevel namespace
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
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56