94b2b13d
Pedro Roque
PHACT source
|
1
2
3
4
|
/*
* at_most.c
*
* Created on: 26/03/2017
|
4d26a735
Pedro Roque
Increased recogni...
|
5
|
* Author: pedro
|
94b2b13d
Pedro Roque
PHACT source
|
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
*/
#ifndef __OPENCL_VERSION__
#include <stddef.h>
#include <stdio.h>
#include "at_most.h"
#include "../bitmaps.h"
#include "../config.h"
#include "../variables.h"
#endif
#include "../kernels/cl_aux_functions.h"
#if CL_D_TYPE == CL_BITMAP
#include "../kernels/cl_bitmaps.h"
#elif CL_D_TYPE == CL_INTERVAL
#include "../kernels/cl_intervals.h"
#endif
#include "../kernels/cl_constraints.h"
#include "../kernels/cl_variables.h"
#include "../kernels/cl_ttl.h"
#ifndef __OPENCL_VERSION__
|
4d26a735
Pedro Roque
Increased recogni...
|
41
|
unsigned int c_at_most(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k) {
|
94b2b13d
Pedro Roque
PHACT source
|
42
43
44
45
46
47
48
|
unsigned int i;
USE_CS[AT_MOST] = 1;
USE_NON_CS_REIFI[AT_MOST] = 1;
REV = 1;
|
4d26a735
Pedro Roque
Increased recogni...
|
49
|
unsigned int* c_vs = malloc(n_vs * sizeof(unsigned int));
|
94b2b13d
Pedro Roque
PHACT source
|
50
51
52
53
54
55
|
for {
c_vs[i] = X_ids[i];
}
int consts[2];
|
4d26a735
Pedro Roque
Increased recogni...
|
56
57
|
consts[0] = (int)n;
consts[1] = (int)k;
|
94b2b13d
Pedro Roque
PHACT source
|
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
// creates a new generic constraint
unsigned int c_id = c_new(c_vs, n_vs, consts, 2, -1);
// pointers to this type of constraint functions
CS[c_id].kind = AT_MOST;
CS[c_id].check_sol_f = &at_most_check;
CS[c_id].constant_val = 0;
free(c_vs);
return c_id;
}
/*
* Creates a new reified constraint of the at_most type and return the constraint ID
*
* n - maximum number of variables in X that may contain k
* X_ids - vector with the ID of the variables that may contain k
* n_vs - maximum number of variables in X vector
* k - Value that should be set in at most n variables of X
* reif_v_id - ID of the reification variable
*/
|
4d26a735
Pedro Roque
Increased recogni...
|
81
|
unsigned int c_at_most_reif(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k, int reif_v_id) {
|
94b2b13d
Pedro Roque
PHACT source
|
82
83
84
85
86
87
|
unsigned int i;
if (VS[reif_v_id].max > 1) {
v_del_gt(&VS[reif_v_id], 1);
if (VS[reif_v_id].n_vals == 0) {
|
4d26a735
Pedro Roque
Increased recogni...
|
88
89
90
91
92
93
94
95
|
fprintf(stderr, "\nError: Constraint AT_MOST_REIF makes model inconsistent at creation:\n");
exit(-1);
}
}
// set to include in kernel compilation
USE_CS[AT_MOST] = 1;
USE_CS_REIFI[AT_MOST] = 1;
|
94b2b13d
Pedro Roque
PHACT source
|
96
97
98
99
100
101
102
103
|
REV = 1;
unsigned int* c_vs = malloc(n_vs * sizeof(unsigned int));
for (i = 0; i < n_vs; i++) {
c_vs[i] = X_ids[i];
}
|
4d26a735
Pedro Roque
Increased recogni...
|
104
|
int consts[2];
|
94b2b13d
Pedro Roque
PHACT source
|
105
106
107
108
109
110
|
consts[0] = (int)n;
consts[1] = (int)k;
unsigned int c_id = c_new(c_vs, n_vs, consts, 2, reif_v_id);
|
4d26a735
Pedro Roque
Increased recogni...
|
111
112
|
// pointers to this type of constraint functions
CS[c_id].kind = AT_MOST;
|
94b2b13d
Pedro Roque
PHACT source
|
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
CS[c_id].check_sol_f = &at_most_check;
CS[c_id].constant_val = 0;
free(c_vs);
return c_id;
}
/*
* Return true if the at_most constraint is respected or false if not
*
* c - constraint to check if is respected
* explored - if the CSP was already explored, which mean that all the variables must already be singletons
* */
bool at_most_check(constr* c, bool explored) {
var** X = c->c_vs;
var* x;
int n = c->c_consts[0];
int k = c->c_consts[1];
int set = 0;
|
4d26a735
Pedro Roque
Increased recogni...
|
133
134
135
136
|
unsigned int i;
for (i = 0; i < c->n_c_vs; i++) {
x = X[i];
|
94b2b13d
Pedro Roque
PHACT source
|
137
138
139
140
141
|
#if CHECK_SOL_N_VALS
if (x->to_label && x->n_vals != 1) {
if (explored) {
|
4d26a735
Pedro Roque
Increased recogni...
|
142
143
144
145
|
fprintf(stderr, "\nError: Constraint AT_MOST (%d) not respected:\n", c->c_id);
for (i = 0; i < c->n_c_vs; i++) {
fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->c_vs[i]->v_id, b_get_min_val(&c->c_vs[i]->domain_b),
|
94b2b13d
Pedro Roque
PHACT source
|
146
|
b_get_max_val(&c->c_vs[i]->domain_b),
|
4d26a735
Pedro Roque
Increased recogni...
|
147
148
149
150
151
152
|
b_cnt_vals(&c->c_vs[i]->domain_b));
}
}
return false;
} else
|
94b2b13d
Pedro Roque
PHACT source
|
153
|
#endif
|
4d26a735
Pedro Roque
Increased recogni...
|
154
155
|
if (x->min == k) {
|
94b2b13d
Pedro Roque
PHACT source
|
156
|
set++;
|
4d26a735
Pedro Roque
Increased recogni...
|
157
158
|
}
}
|
94b2b13d
Pedro Roque
PHACT source
|
159
160
161
162
163
164
165
|
if (set > n) {
if (explored) {
fprintf(stderr, "\nError: Constraint AT_MOST (%d) not respected:\n", c->c_id);
|
4d26a735
Pedro Roque
Increased recogni...
|
166
|
for {
|
94b2b13d
Pedro Roque
PHACT source
|
167
168
|
fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->c_vs[i]->v_id, b_get_min_val(&c->c_vs[i]->domain_b),
b_get_max_val(&c->c_vs[i]->domain_b), b_cnt_vals(&c->c_vs[i]->domain_b));
|
4d26a735
Pedro Roque
Increased recogni...
|
169
170
171
172
173
174
175
176
177
|
}
}
return false;
}
return true;
}
#endif
|
94b2b13d
Pedro Roque
PHACT source
|
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
/*
* Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_most constraint
*
* prop_ok will be set to 1 if success or to 0 if any domain became empty
* vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
* c_consts - vector with all constrained constants per constraint, per constraint ID order
* vs_prop_ - all CSP variables with current step values
* prop_v_id - variable ID to propagate
* current_cs - constraint that should be propagated for the variable with prop_v_id ID
* vs_id_to_prop_ - circular vector with the ids of the variables to propagate
*/
CUDA_FUNC void at_most_prop(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok CS_IGNORE_FUNC TTL_CTR) {
int n = c_consts[0];
int k = c_consts[1];
|
94b2b13d
Pedro Roque
PHACT source
|
195
|
int set = 0;
|
4d26a735
Pedro Roque
Increased recogni...
|
196
|
int possible = 0;
|
94b2b13d
Pedro Roque
PHACT source
|
197
|
bool contains;
|
94b2b13d
Pedro Roque
PHACT source
|
198
199
|
int x_id;
bool changed = 0;
|
4d26a735
Pedro Roque
Increased recogni...
|
200
|
int i;
|
94b2b13d
Pedro Roque
PHACT source
|
201
|
|
4d26a735
Pedro Roque
Increased recogni...
|
202
203
|
for {
CHECK_TTL
|
94b2b13d
Pedro Roque
PHACT source
|
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
|
x_id = vs_per_c_idx[i];
if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
if (++set > n) {
*prop_ok = 0;
return;
}
} else {
cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
if (contains) {
possible++;
}
}
}
if (set == n) {
for (i = 0; possible > 0; i++) {
x_id = vs_per_c_idx[i];
CHECK_TTL(ttl_ctr, 41)
if (V_N_VALS(vs_prop_[x_id]) > 1) {
cl_v_del_val_m(&changed, &vs_prop_[x_id], k TTL_CTR_V);
if (changed) {
possible--;
v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id);
}
}
}
#if CL_CS_IGNORE
cs_ignore[current_cs->c_id] = 1;
#endif
}
}
#if CS_R_AT_MOST == 1
CUDA_FUNC void at_most_reif( CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
CL_MEMORY unsigned short* vs_id_to_prop_ CS_IGNORE_FUNC TTL_CTR) {
int n = c_consts[0];
int k = c_consts[1];
int set = 0;
int possible = 0;
|
4d26a735
Pedro Roque
Increased recogni...
|
260
|
bool contains;
|
94b2b13d
Pedro Roque
PHACT source
|
261
262
263
264
|
int x_id;
int i;
for (i = 0; i < current_cs->n_c_vs; i++) {
|
4d26a735
Pedro Roque
Increased recogni...
|
265
266
|
CHECK_TTL(ttl_ctr, 42)
x_id = vs_per_c_idx[i];
|
94b2b13d
Pedro Roque
PHACT source
|
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
|
if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
if (++set > n) {
cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 1 TTL_CTR_V);
v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int(current_cs->reif_var_id));
#if CL_CS_IGNORE
cs_ignore[current_cs->c_id] = 1;
#endif
return;
} else {
cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
if (contains) {
possible++;
|
4d26a735
Pedro Roque
Increased recogni...
|
284
|
}
|
94b2b13d
Pedro Roque
PHACT source
|
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
|
}
}
}
if (set + possible <= n) {
cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 0 TTL_CTR_V);
v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int(current_cs->reif_var_id));
#if CL_CS_IGNORE
cs_ignore[current_cs->c_id] = 1;
#endif
}
}
|
4d26a735
Pedro Roque
Increased recogni...
|
304
|
* c_consts - vector with all constrained constants per constraint, per constraint ID order
|
94b2b13d
Pedro Roque
PHACT source
|
305
306
307
308
309
310
311
312
313
314
315
316
317
|
* vs_prop_ - all CSP variables with current step values
* prop_v_id - variable ID to propagate
* current_cs - constraint that should be propagated for the variable with prop_v_id ID
* vs_id_to_prop_ - circular vector with the ids of the variables to propagate
*/
CUDA_FUNC void at_most_prop_opposite(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok CS_IGNORE_FUNC TTL_CTR) {
int n = c_consts[0];
int k = c_consts[1];
int set = 0;
int possible = 0;
bool contains;
|
94b2b13d
Pedro Roque
PHACT source
|
318
319
|
int x_id;
bool changed = 0;
|
4d26a735
Pedro Roque
Increased recogni...
|
320
|
int i;
|
94b2b13d
Pedro Roque
PHACT source
|
321
|
|
4d26a735
Pedro Roque
Increased recogni...
|
322
323
|
for {
CHECK_TTL
|
94b2b13d
Pedro Roque
PHACT source
|
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
|
x_id = vs_per_c_idx[i];
if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
set++;
} else {
cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
if (contains) {
possible++;
}
}
}
if (set + possible <= n) {
*prop_ok = 0;
return;
}
if (set + possible == n + 1) {
for (i = 0; possible > 0; i++) {
x_id = vs_per_c_idx[i];
CHECK_TTL(ttl_ctr, 205)
if (V_N_VALS(vs_prop_[x_id]) > 1) {
cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
if (contains) {
cl_v_del_all_except_val_m(&changed, &vs_prop_[x_id], k TTL_CTR_V);
possible--;
v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id);
}
}
}
#if CL_CS_IGNORE
cs_ignore[current_cs->c_id] = 1;
#endif
}
}
#endif
CUDA_FUNC void at_most_propagate(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok PROPAGATED_FUNC CS_IGNORE_FUNC TTL_CTR) {
#if CS_R_AT_MOST == 0
at_most_prop(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
#if CL_STATS == 1
*propagated = true;
#endif
#elif CS_R_AT_MOST == 1
if (current_cs->reified == 1) {
if (V_N_VALS(vs_prop_[current_cs->reif_var_id]) > 1) {
at_most_reif(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_ CS_IGNORE_CALL TTL_CTR_V);
|
4d26a735
Pedro Roque
Increased recogni...
|
381
382
383
384
385
386
387
388
389
390
391
|
} else {
if (V_MIN(vs_prop_[current_cs->reif_var_id]) == 1) {
at_most_prop(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
} else {
at_most_prop_opposite(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
}
#if CL_STATS == 1
*propagated = true;
#endif
}
|
94b2b13d
Pedro Roque
PHACT source
|
392
393
394
395
396
397
|
} else {
at_most_prop(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
#if CL_STATS == 1
*propagated = true;
#endif
}
|
4d26a735
Pedro Roque
Increased recogni...
|
398
|
#endif
|
94b2b13d
Pedro Roque
PHACT source
|
399
400
401
|
}
#endif
|