main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Jul 27 2020 00:00:00 for Gecode by
doxygen
1.8.18
gecode
search
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
34
namespace
Gecode
{
namespace
Search {
35
36
forceinline
37
NoNGL::NoNGL
(
void
) {}
38
39
forceinline
40
NoNGL::NoNGL
(
Space
& home)
41
:
NGL
(home) {}
42
43
forceinline
44
NoNGL::NoNGL
(
Space
& home,
NoNGL
& ngl)
45
:
NGL
(home,ngl) {}
46
47
48
49
forceinline
50
NoGoodsProp::NoGoodsProp
(
Space
& home,
NGL
* root0)
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
72
forceinline
73
NoGoodsProp::NoGoodsProp
(
Space
& home,
NoGoodsProp
&
p
)
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>
89
forceinline
ExecStatus
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
Gecode::Search::NoGoodsProp
No-good propagator.
Definition:
nogoods.hh:65
Gecode::Int::Arithmetic::ll
long long int ll(int x)
Cast x into a long long int.
Definition:
mult.hpp:53
Gecode::Search::NoNGL
Class for a sentinel no-good literal.
Definition:
nogoods.hh:42
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
Gecode::Search::NoNGL::NoNGL
NoNGL(void)
Constructor for creation.
Definition:
nogoods.hpp:37
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode
Gecode toplevel namespace
Gecode::Propagator
Base-class for propagators.
Definition:
core.hpp:1064
GECODE_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition:
macros.hpp:91
Gecode::NGL::notice
virtual bool notice(void) const
Whether dispose must always be called (returns false)
Definition:
core.cpp:896
Gecode::Home
Home class for posting propagators
Definition:
core.hpp:856
Gecode::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition:
core.hpp:562
Gecode::Space::ngl
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition:
core.cpp:641
Gecode::Space::trycommit
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition:
core.hpp:3237
Gecode::Search::NoGoodsProp::NoGoodsProp
NoGoodsProp(Space &home, NGL *root)
Constructor for creation.
Definition:
nogoods.hpp:50
a
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Gecode::Search::NoGoodsProp::root
NGL * root
Root of no-good literal tree.
Definition:
nogoods.hh:68
Gecode::Space::failed
bool failed(void) const
Check whether space is failed.
Definition:
core.hpp:4044
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::NGL::subscribe
virtual void subscribe(Space &home, Propagator &p)=0
Subscribe propagator p to all views of the no-good literal.
forceinline
#define forceinline
Definition:
config.hpp:185
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Gecode::NGL
No-good literal recorded during search.
Definition:
core.hpp:1340
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::Space::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition:
core.hpp:4059
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition:
core.hpp:474
Gecode::NGL::next
NGL * next(void) const
Return pointer to next literal.
Definition:
core.hpp:3793
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition:
core.hpp:476
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
Gecode::Search::NoGoodsProp::post
static ExecStatus post(Space &home, const Path &p)
Post propagator for path p.
Definition:
nogoods.hpp:90
Gecode::Search::NoGoodsProp::n
unsigned int n
Number of no-good literals with subscriptions.
Definition:
nogoods.hh:70
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:472