main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Jan 10 2020 11:38:25 for Gecode by
doxygen
1.8.16
gecode
int
distinct
graph.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, 2003
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 <climits>
35
36
namespace
Gecode
{
namespace
Int {
namespace
Distinct {
37
38
template
<
class
View>
39
forceinline
40
Graph<View>::Graph
(
void
) {}
41
42
template
<
class
View>
43
forceinline
ExecStatus
44
Graph<View>::init
(
Space
& home,
ViewArray<View>
&
x
) {
45
using namespace
ViewValGraph;
46
n_view =
x
.size();
47
view = home.
alloc
<ViewNode<View>*>(n_view);
48
49
// Find value information for construction of view value graph
50
int
min
=
x
[0].min();
51
int
max
=
x
[0].max();
52
for
(
int
i
=1;
i
<n_view;
i
++) {
53
min
=
std::min
(
min
,
x
[
i
].
min
());
54
max
=
std::max
(
max
,
x
[
i
].
max
());
55
}
56
57
unsigned
int
width = static_cast<unsigned int>(
max
-
min
+1);
58
59
// Definitly not enough values
60
if
(width < static_cast<unsigned int>(n_view))
61
return
ES_FAILED
;
62
63
// Initialize view nodes
64
for
(
int
i
=0;
i
<n_view;
i
++)
65
view[
i
] =
new
(home) ViewNode<View>(
x
[
i
]);
66
67
Region
r
;
68
69
if
(static_cast<unsigned int>(n_view)*4 >= width) {
70
// Values are dense: use a mapping
71
ValNode<View>** val2node =
r
.alloc<ValNode<View>* >(width);
72
73
for
(
unsigned
int
i
=0U;
i
<width;
i
++)
74
val2node[
i
]=NULL;
75
76
for
(
int
i
=0;
i
<n_view;
i
++) {
77
Edge<View>** edge_p = view[
i
]->val_edges_ref();
78
for
(
ViewValues<View>
xi(
x
[
i
]); xi(); ++xi) {
79
if
(val2node[xi.val()-
min
] == NULL)
80
val2node[xi.val()-
min
] =
new
(home) ValNode<View>(xi.val());
81
*edge_p =
new
(home) Edge<View>(val2node[xi.val()-
min
],view[
i
]);
82
edge_p = (*edge_p)->next_edge_ref();
83
}
84
*edge_p = NULL;
85
}
86
87
for
(
unsigned
int
i
=width;
i
--; )
88
if
(val2node[
i
] != NULL) {
89
val2node[
i
]->next_val(val);
90
val = val2node[
i
];
91
n_val++;
92
}
93
94
}
else
{
95
// Values are sparse
96
for
(
int
i
=0;
i
<n_view;
i
++)
97
ViewValGraph::Graph<View>::init
(home,view[
i
]);
98
}
99
100
if
(n_val < n_view)
101
return
ES_FAILED
;
102
103
typename
ViewValGraph::Graph<View>::ViewNodeStack
m(
r
,n_view);
104
for
(
int
i
=0;
i
<n_view;
i
++)
105
if
(!match(m,view[
i
]))
106
return
ES_FAILED
;
107
return
ES_OK
;
108
}
109
110
template
<
class
View>
111
forceinline
bool
112
Graph<View>::sync
(
void
) {
113
using namespace
ViewValGraph;
114
Region
r
;
115
// Stack for view nodes to be rematched
116
typename
ViewValGraph::Graph<View>::ViewNodeStack
re(
r
,n_view);
117
// Synchronize nodes
118
for
(
int
i
= n_view;
i
--; ) {
119
ViewNode<View>*
x
= view[
i
];
120
GECODE_ASSUME
(
x
!= NULL);
121
if
(
x
->view().
assigned
()) {
122
x
->edge_fst()->val(
x
)->matching(NULL);
123
for
(Edge<View>* e =
x
->val_edges(); e != NULL; e = e->next_edge())
124
e->unlink();
125
view[
i
] = view[--n_view];
126
}
else
if
(
x
->changed()) {
127
ViewRanges<View>
rx(
x
->view());
128
Edge<View>* m =
x
->edge_fst();
// Matching edge
129
Edge<View>**
p
=
x
->val_edges_ref();
130
Edge<View>* e = *
p
;
131
GECODE_ASSUME
(e != NULL);
132
do
{
133
while
(e->val(
x
)->val() < rx.min()) {
134
// Skip edge
135
e->unlink(); e->mark();
136
e = e->next_edge();
137
}
138
*
p
= e;
139
assert(rx.min() == e->val(
x
)->val());
140
// This edges must be kept
141
for
(
unsigned
int
j=rx.width(); j--; ) {
142
e->free();
143
p
= e->next_edge_ref();
144
e = e->next_edge();
145
}
146
++rx;
147
}
while
(rx());
148
*
p
= NULL;
149
while
(e != NULL) {
150
e->unlink(); e->mark();
151
e = e->next_edge();
152
}
153
if
(m->marked()) {
154
// Matching has been deleted!
155
m->val(
x
)->matching(NULL);
156
re.
push
(
x
);
157
}
158
x
->
update
();
159
}
else
{
160
// Just free edges
161
for
(Edge<View>* e =
x
->val_edges(); e != NULL; e = e->next_edge())
162
e->free();
163
}
164
}
165
166
typename
ViewValGraph::Graph<View>::ViewNodeStack
m(
r
,n_view);
167
while
(!re.
empty
())
168
if
(!match(m,re.
pop
()))
169
return
false
;
170
return
true
;
171
}
172
173
174
template
<
class
View>
175
forceinline
bool
176
Graph<View>::mark
(
void
) {
177
using namespace
ViewValGraph;
178
179
Region
r
;
180
181
int
n_view_visited = 0;
182
{
183
// Marks all edges as used that are on simple paths in the graph
184
// that start from a free (unmatched node) by depth-first-search
185
Support::StaticStack<ValNode<View>
*,
Region
> visit(
r
,n_val);
186
187
// Insert all free nodes: they can be only value nodes as we
188
// have a maximum matching covering all view nodes
189
count
++;
190
{
191
ValNode<View>**
v
= &val;
192
while
(*
v
!= NULL)
193
if
(!(*v)->matching()) {
194
if
((*v)->empty()) {
195
*
v
= (*v)->next_val();
196
n_val--;
197
}
else
{
198
(*v)->min =
count
;
199
visit.
push
(*
v
);
200
v
= (*v)->next_val_ref();
201
}
202
}
else
{
203
v
= (*v)->next_val_ref();
204
}
205
}
206
207
// Invariant: only value nodes are on the stack!
208
while
(!visit.
empty
()) {
209
ValNode<View>*
n
= visit.
pop
();
210
for
(Edge<View>* e =
n
->edge_fst(); e !=
n
->edge_lst(); e=e->next()) {
211
// Get the value node
212
e->use();
213
ViewNode<View>*
x
= e->view(
n
);
214
if
(
x
->min <
count
) {
215
n_view_visited++;
216
x
->min =
count
;
217
assert(
x
->edge_fst()->next() ==
x
->edge_lst());
218
ValNode<View>* m =
x
->edge_fst()->val(
x
);
219
x
->edge_fst()->use();
220
if
(m->min <
count
) {
221
m->min =
count
;
222
visit.
push
(m);
223
}
224
}
225
}
226
}
227
}
228
229
// If all view nodes have been visited, also all edges are used!
230
if
(n_view_visited < n_view) {
231
scc();
232
return
true
;
233
}
else
{
234
return
false
;
235
}
236
}
237
238
template
<
class
View>
239
forceinline
ExecStatus
240
Graph<View>::prune
(
Space
& home,
bool
&
assigned
) {
241
using namespace
ViewValGraph;
242
assigned
=
false
;
243
// Tell constraints and also eliminate nodes and edges
244
for
(
int
i
= n_view;
i
--; ) {
245
ViewNode<View>*
x
= view[
i
];
246
if
(!
x
->edge_fst()->used(
x
)) {
247
GECODE_ME_CHECK
(
x
->view().eq(home,
x
->edge_fst()->val(
x
)->val()));
248
x
->edge_fst()->val(
x
)->matching(NULL);
249
for
(Edge<View>* e =
x
->val_edges(); e != NULL; e = e->next_edge())
250
e->unlink();
251
view[
i
] = view[--n_view];
252
assigned
=
true
;
253
}
else
{
254
IterPruneVal<View> pv(view[
i
]);
255
GECODE_ME_CHECK
(view[
i
]->view().minus_v(home,pv,
false
));
256
}
257
}
258
return
ES_OK
;
259
}
260
261
}}}
262
263
// STATISTICS: int-prop
264
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::Int::ViewValGraph::Graph
View-value graph base class.
Definition:
view-val-graph.hh:294
Gecode::Int::Distinct::Graph::Graph
Graph(void)
Construct graph as not yet initialized.
Definition:
graph.hpp:40
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:49
Gecode::Int::Precede::assigned
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition:
single.hpp:43
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition:
static-stack.hpp:42
Gecode::Int::ViewValues
Value iterator for integer views.
Definition:
view.hpp:94
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::VarImpVar::assigned
bool assigned(void) const
Test whether view is assigned.
Definition:
var.hpp:111
Gecode
Gecode toplevel namespace
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition:
view.hpp:54
Gecode::Int::Distinct::Graph::sync
bool sync(void)
Synchronize graph with new view domains.
Definition:
graph.hpp:112
Gecode::Region
Handle to region.
Definition:
region.hpp:55
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition:
core.hpp:2837
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition:
static-stack.hpp:98
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition:
static-stack.hpp:116
Test::Int::Distinct::v
const int v[7]
Definition:
distinct.cpp:259
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition:
count.cpp:40
Gecode::Int::Distinct::Graph::prune
ExecStatus prune(Space &home, bool &assigned)
Prune unmarked edges, assigned is true if a view got assigned.
Definition:
graph.hpp:240
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition:
static-stack.hpp:137
Gecode::VarImpVar::update
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition:
var.hpp:116
forceinline
#define forceinline
Definition:
config.hpp:185
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition:
macros.hpp:52
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:67
Gecode::ViewArray
View arrays.
Definition:
array.hpp:253
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::ES_FAILED
Execution has resulted in failure.
Definition:
core.hpp:474
Gecode::Int::Distinct::Graph::init
ExecStatus init(Space &home, ViewArray< View > &x)
Initialize graph.
Definition:
graph.hpp:44
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::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::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844
Gecode::Int::Distinct::Graph::mark
bool mark(void)
Mark edges in graph, return true if pruning is at all possible.
Definition:
graph.hpp:176
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition:
macros.hpp:114
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:472