Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
nogoods.hpp
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
34namespace Gecode { namespace Search {
35
37 NoNGL::NoNGL(void) {}
38
41 : NGL(home) {}
42
45 : NGL(home,ngl) {}
46
47
48
51 : Propagator(Home(home)), root(root0), n(0U) {
52 // Create subscriptions
53 root->subscribe(home,*this); n++;
54 bool notice = root->notice();
55 NGL* l = root->next();
56 while ((l != NULL) && l->leaf()) {
57 l->subscribe(home,*this); n++;
58 notice = notice || l->notice();
59 l = l->next();
60 }
61 if (l != NULL) {
62 l->subscribe(home,*this); n++;
63 }
64 while (!notice && (l != NULL)) {
65 notice = notice || l->notice();
66 l = l->next();
67 }
68 if (notice)
69 home.notice(*this,AP_DISPOSE);
70 }
71
74 : Propagator(home,p), n(p.n) {
75 assert(p.root != NULL);
76 NoNGL s;
77 NGL* c = &s;
78 for (NGL* pc = p.root; pc != NULL; pc = pc->next()) {
79 NGL* n = pc->copy(home);
80 n->leaf(pc->leaf());
81 c->next(n); c=n;
82 }
83 root = s.next();
84 }
85
86
87
88 template<class Path>
90 NoGoodsProp::post(Space& home, const Path& p) {
91 int s = 0;
92 int n = std::min(p.ds.entries(),static_cast<int>(p.ngdl()));
93
94 unsigned long int n_nogood = 0;
95
96 // Eliminate the alternatives which are not no-goods at the end
97 while ((n > s) && (p.ds[n-1].truealt() == 0U))
98 n--;
99
100 // A sentinel element
101 NoNGL nn;
102 // Current no-good literal
103 NGL* c = &nn;
104
105 // Commit no-goods at the beginning
106 while ((s < n) && (p.ds[s].truealt() > 0U))
107 // Try whether this is a rightmost alternative
108 if (p.ds[s].rightmost()) {
109 // No literal needed, directly try to commit
110 home.trycommit(*p.ds[s].choice(),p.ds[s].truealt());
111 s++;
112 } else {
113 // Prune using no-good literals
114 for (unsigned int a=0U; a<p.ds[s].truealt(); a++) {
115 NGL* l = home.ngl(*p.ds[s].choice(),a);
116 // Does the brancher support no-good literals?
117 if (l == NULL)
118 return ES_OK;
119 GECODE_ES_CHECK(l->prune(home));
120 }
121 // Add literal as root if needed and stop
122 if (NGL* l = home.ngl(*p.ds[s].choice(),p.ds[s].truealt())) {
123 c = c->add(l,false);
124 s++; break;
125 }
126 }
127
128 // There are no literals
129 if (home.failed())
130 return ES_FAILED;
131 if (s >= n)
132 return ES_OK;
133
134 // There must be at least two literals
135 assert((n-s > 1) ||
136 ((n-s == 1) && (c != &nn)));
137
138 // Remember the last leaf
139 NGL* ll = NULL;
140
141 // Create literals
142 for (int i=s; i<n; i++) {
143 // Add leaves
144 for (unsigned int a=0U; a<p.ds[i].truealt(); a++) {
145 NGL* l = home.ngl(*p.ds[i].choice(),a);
146 if (l == NULL) {
147 // The brancher does not support no-goods
148 if (ll == NULL)
149 return ES_OK;
150 ll->next(NULL);
151 break;
152 }
153 c = c->add(l,true); ll = c;
154 n_nogood++;
155 }
156 // Check whether to add an additional subtree
157 if (NGL* l = home.ngl(*p.ds[i].choice(),p.ds[i].truealt())) {
158 c = c->add(l,false);
159 } else if (!p.ds[i].rightmost()) {
160 // The brancher does not support no-goods
161 if (ll == NULL)
162 return ES_OK;
163 ll->next(NULL);
164 break;
165 }
166 }
167
168 const_cast<Path&>(p).ng(n_nogood);
169
170 (void) new (home) NoGoodsProp(home,nn.next());
171 return ES_OK;
172 }
173
174}}
175
176// STATISTICS: search-other
Home class for posting propagators
Definition core.hpp:856
No-good literal recorded during search.
Definition core.hpp:1342
bool leaf(void) const
Test whether literal is a leaf.
Definition core.hpp:3796
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
virtual void subscribe(Space &home, Propagator &p)=0
Subscribe propagator p to all views of the no-good literal.
NGL(void)
Constructor for creation.
Definition core.hpp:3819
NGL * next(void) const
Return pointer to next literal.
Definition core.hpp:3800
virtual bool notice(void) const
Whether dispose must always be called (returns false)
Definition core.cpp:897
friend class Space
Definition core.hpp:1068
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
static ExecStatus post(Space &home, const Path &p)
Post propagator for path p.
Definition nogoods.hpp:90
unsigned int n
Number of no-good literals with subscriptions.
Definition nogoods.hh:70
NoGoodsProp(Space &home, NGL *root)
Constructor for creation.
Definition nogoods.hpp:50
NGL * root
Root of no-good literal tree.
Definition nogoods.hh:68
Class for a sentinel no-good literal.
Definition nogoods.hh:42
NoNGL(void)
Constructor for creation.
Definition nogoods.hpp:37
Computation spaces.
Definition core.hpp:1744
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4051
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:4066
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition core.hpp:3241
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition core.cpp:642
Search engines
Gecode toplevel namespace
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
#define forceinline
Definition config.hpp:194