main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
gecode
int
sorted
narrowing.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5
*
6
* Copyright:
7
* Patrick Pekczynski, 2004
8
*
9
* Last modified:
10
* $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11
* $Revision: 13068 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
namespace
Gecode
{
namespace
Int {
namespace
Sorted {
39
56
template
<
class
View>
57
inline
void
58
computesccs
(
Space
& home,
ViewArray<View>
&
x
,
ViewArray<View>
&
y
,
59
int
phi[],
SccComponent
sinfo[],
int
scclist[]) {
60
61
// number of sccs is bounded by xs (number of x-nodes)
62
int
xs =
x
.size();
63
Region
r
(home);
64
Support::StaticStack<int,Region>
cs(
r
,xs);
65
66
//select an y node from the graph
67
for
(
int
j = 0; j < xs; j++) {
68
int
yjmin =
y
[j].min();
// the processed min
69
while
(!cs.
empty
() &&
x
[phi[sinfo[cs.
top
()].
rightmost
]].max() < yjmin) {
70
// the topmost scc cannot "reach" y_j or a node to the right of it
71
cs.
pop
();
72
}
73
74
// a component has the form C(y-Node, matching x-Node)
75
// C is a minimal scc in the oriented intersection graph
76
// we only store y_j-Node, since \phi(j) gives the matching X-node
77
int
i
= phi[j];
78
int
ximin =
x
[
i
].min();
79
while
(!cs.
empty
() && ximin <=
y
[sinfo[cs.
top
()].
rightmost
].max()) {
80
// y_j can "reach" cs.top() ,
81
// i.e. component c can reach component cs.top()
82
// merge c and cs.top() into new component
83
int
top = cs.
top
();
84
// connecting
85
sinfo[sinfo[j].
leftmost
].
left
= top;
86
sinfo[top].
right
= sinfo[j].
leftmost
;
87
// moving leftmost
88
sinfo[j].
leftmost
= sinfo[top].
leftmost
;
89
// moving rightmost
90
sinfo[sinfo[top].
leftmost
].
rightmost
= j;
91
cs.
pop
();
92
}
93
cs.
push
(j);
94
}
95
cs.
reset
();
96
97
98
// now we mark all components with the respective scc-number
99
// labeling is bound by O(k) which is bound by O(n)
100
101
for
(
int
i
= 0;
i
< xs;
i
++) {
102
if
(sinfo[
i
].left ==
i
) {
// only label variables in sccs
103
int
scc = sinfo[
i
].
rightmost
;
104
int
z
=
i
;
105
//bound by the size of the largest scc = k
106
while
(sinfo[
z
].right !=
z
) {
107
sinfo[
z
].
rightmost
= scc;
108
scclist[phi[
z
]] = scc;
109
z
= sinfo[
z
].
right
;
110
}
111
sinfo[
z
].
rightmost
= scc;
112
scclist[phi[
z
]] = scc;
113
}
114
}
115
}
116
132
template
<
class
View,
bool
Perm>
133
inline
bool
134
narrow_domx
(
Space
& home,
135
ViewArray<View>
&
x
,
136
ViewArray<View>
&
y
,
137
ViewArray<View>
&
z
,
138
int
tau[],
139
int
[],
140
int
scclist[],
141
SccComponent
sinfo[],
142
bool
& nofix) {
143
144
int
xs =
x
.size();
145
146
// For every x node
147
for
(
int
i
= 0;
i
< xs;
i
++) {
148
149
int
xmin =
x
[
i
].min();
150
/*
151
* take the scc-list for the current x node
152
* start from the leftmost reachable y node of the scc
153
* and check which Y node in the scc is
154
* really the rightmost node intersecting x, i.e.
155
* search for the greatest lower bound of x
156
*/
157
int
start = sinfo[scclist[
i
]].
leftmost
;
158
while
(
y
[start].
max
() < xmin) {
159
start = sinfo[start].
right
;
160
}
161
162
if
(Perm) {
163
// start is the leftmost-position for x_i
164
// that denotes the lower bound on p_i
165
166
ModEvent
me_plb =
z
[
i
].gq(home, start);
167
if
(
me_failed
(me_plb)) {
168
return
false
;
169
}
170
nofix |= (
me_modified
(me_plb) && start !=
z
[
i
].min());
171
}
172
173
ModEvent
me_lb =
x
[
i
].gq(home,
y
[start].
min
());
174
if
(
me_failed
(me_lb)) {
175
return
false
;
176
}
177
nofix |= (
me_modified
(me_lb) &&
178
y
[start].min() !=
x
[
i
].min());
179
180
int
ptau = tau[xs - 1 -
i
];
181
int
xmax =
x
[ptau].max();
182
/*
183
* take the scc-list for the current x node
184
* start from the rightmost reachable node and check which
185
* y node in the scc is
186
* really the rightmost node intersecting x, i.e.
187
* search for the smallest upper bound of x
188
*/
189
start = sinfo[scclist[ptau]].
rightmost
;
190
while
(
y
[start].
min
() > xmax) {
191
start = sinfo[start].
left
;
192
}
193
194
if
(Perm) {
195
//start is the rightmost-position for x_i
196
//that denotes the upper bound on p_i
197
ModEvent
me_pub =
z
[ptau].lq(home, start);
198
if
(
me_failed
(me_pub)) {
199
return
false
;
200
}
201
nofix |= (
me_modified
(me_pub) && start !=
z
[ptau].max());
202
}
203
204
ModEvent
me_ub =
x
[ptau].lq(home,
y
[start].
max
());
205
if
(
me_failed
(me_ub)) {
206
return
false
;
207
}
208
nofix |= (
me_modified
(me_ub) &&
209
y
[start].max() !=
x
[ptau].max());
210
}
211
return
true
;
212
}
213
224
template
<
class
View>
225
inline
bool
226
narrow_domy
(
Space
& home,
227
ViewArray<View>
&
x
,
ViewArray<View>
&
y
,
228
int
phi[],
int
phiprime[],
bool
& nofix) {
229
for
(
int
i
=
x
.size();
i
--; ) {
230
ModEvent
me_lb =
y
[
i
].gq(home,
x
[phiprime[
i
]].
min
());
231
if
(
me_failed
(me_lb)) {
232
return
false
;
233
}
234
nofix |= (
me_modified
(me_lb) &&
235
x
[phiprime[
i
]].min() !=
y
[
i
].min());
236
237
ModEvent
me_ub =
y
[
i
].lq(home,
x
[phi[
i
]].
max
());
238
if
(
me_failed
(me_ub)) {
239
return
false
;
240
}
241
nofix |= (
me_modified
(me_ub) &&
242
x
[phi[
i
]].max() !=
y
[
i
].max());
243
}
244
return
true
;
245
}
246
247
}}}
248
249
// STATISTICS: int-prop
250
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:784
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:784
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition:
modevent.hpp:58
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:53
Gecode::z
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition:
set.hh:784
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition:
static-stack.hpp:46
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Int::Sorted::SccComponent::right
int right
Direct right neighbour of an y-node in a scc.
Definition:
sortsup.hpp:64
Gecode
Gecode toplevel namespace
Gecode::Int::Sorted::narrow_domy
bool narrow_domy(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
Narrowing the domains of the y views.
Definition:
narrowing.hpp:226
Gecode::Support::StaticStack::reset
void reset(void)
Reset stack (pop all elements)
Definition:
static-stack.hpp:114
Gecode::Int::Sorted::narrow_domx
bool narrow_domx(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, int tau[], int[], int scclist[], SccComponent sinfo[], bool &nofix)
Narrowing the domains of the x variables.
Definition:
narrowing.hpp:134
Gecode::Region
Handle to region.
Definition:
region.hpp:61
Gecode::Int::Sorted::computesccs
void computesccs(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
Definition:
narrowing.hpp:58
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition:
static-stack.hpp:102
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition:
static-stack.hpp:120
Gecode::Support::StaticStack::top
T & top(void) const
Return element on top of stack.
Definition:
static-stack.hpp:127
Gecode::Int::Sorted::SccComponent::rightmost
int rightmost
Rightmost reachable y-node in a scc.
Definition:
sortsup.hpp:66
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition:
core.hpp:142
Gecode::Int::Sorted::SccComponent
Representation of a strongly connected component.
Definition:
sortsup.hpp:57
Gecode::Int::Sorted::SccComponent::leftmost
int leftmost
Leftmost y-node in a scc.
Definition:
sortsup.hpp:60
Gecode::Int::Sorted::SccComponent::left
int left
Direct left neighbour of an y-node in a scc.
Definition:
sortsup.hpp:62
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition:
static-stack.hpp:141
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:71
Gecode::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition:
modevent.hpp:63
Gecode::ViewArray
View arrays.
Definition:
array.hpp:234