94b2b13d
Pedro Roque
PHACT source
|
1
2
3
4
|
/*
* at_least.c
*
* Created on: 26/03/2017
|
4d26a735
Pedro Roque
Increased recogni...
|
5
|
* Author: pedro
|
94b2b13d
Pedro Roque
PHACT source
|
6
7
|
*/
|
94b2b13d
Pedro Roque
PHACT source
|
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_least.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__
/*
* Creates a new constraint of the at_least type and return the constraint ID
* #{i | X[i] = k} >= n
* n - minimum 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
|
4d26a735
Pedro Roque
Increased recogni...
|
41
|
* k - Value that should be set in at least n variables of X
|
94b2b13d
Pedro Roque
PHACT source
|
42
43
44
45
46
47
48
|
*/
unsigned int c_at_least(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k) {
unsigned int i;
// set to include in kernel compilation
USE_CS[AT_LEAST] = 1;
USE_NON_CS_REIFI[AT_LEAST] = 1;
|
4d26a735
Pedro Roque
Increased recogni...
|
49
|
REV = 1;
|
94b2b13d
Pedro Roque
PHACT source
|
50
51
52
53
54
55
|
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...
|
56
57
|
int consts[2];
|
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
|
consts[0] = (int)n;
consts[1] = (int)k;
// 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_LEAST;
CS[c_id].check_sol_f = &at_least_check;
CS[c_id].constant_val = 0;
free(c_vs);
return c_id;
}
/*
* Creates a new reified constraint of the at_least type and return the constraint ID
* #{i | X[i] = k} >= n
* n - minimum 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 least n variables of X
|
4d26a735
Pedro Roque
Increased recogni...
|
81
|
* reif_v_id - ID of the reification variable
|
94b2b13d
Pedro Roque
PHACT source
|
82
83
84
85
86
87
|
*/
unsigned int c_at_least_reif(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k, int reif_v_id) {
unsigned int i;
if (VS[reif_v_id].max > 1) {
v_del_gt(&VS[reif_v_id], 1);
|
4d26a735
Pedro Roque
Increased recogni...
|
88
89
90
91
92
93
94
95
|
if (VS[reif_v_id].n_vals == 0) {
fprintf(stderr, "\nError: Constraint AT_LEAST_REIF makes model inconsistent at creation:\n");
exit(-1);
}
}
// set to include in kernel compilation
|
94b2b13d
Pedro Roque
PHACT source
|
96
97
98
99
100
101
102
103
|
USE_CS[AT_LEAST] = 1;
USE_CS_REIFI[AT_LEAST] = 1;
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
|
}
|
94b2b13d
Pedro Roque
PHACT source
|
105
106
107
108
109
110
|
int consts[2];
consts[0] = (int)n;
consts[1] = (int)k;
// creates a new generic constraint
|
4d26a735
Pedro Roque
Increased recogni...
|
111
112
|
unsigned int c_id = c_new(c_vs, n_vs, consts, 2, reif_v_id);
|
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
|
// pointers to this type of constraint functions
CS[c_id].kind = AT_LEAST;
CS[c_id].check_sol_f = &at_least_check;
CS[c_id].constant_val = 0;
free(c_vs);
return c_id;
}
/*
* Return true if the at_least constraint is respected or false if not
* #{i | X[i] = k} >= n
* 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_least_check(constr* c, bool explored) {
var** X = c->c_vs;
var* x;
int n = c->c_consts[0];
|
4d26a735
Pedro Roque
Increased recogni...
|
133
134
135
136
|
int k = c->c_consts[1];
int set = 0;
unsigned int i;
|
94b2b13d
Pedro Roque
PHACT source
|
137
138
139
140
141
|
for (i = 0; i < c->n_c_vs; i++) {
x = X[i];
#if CHECK_SOL_N_VALS
if (x->to_label && x->n_vals != 1) {
|
4d26a735
Pedro Roque
Increased recogni...
|
142
143
144
145
|
if (explored) {
fprintf(stderr, "\nError: Constraint AT_LEAST not respected:\n");
|
94b2b13d
Pedro Roque
PHACT source
|
146
|
for (i = 0; i < c->n_c_vs; i++) {
|
4d26a735
Pedro Roque
Increased recogni...
|
147
148
149
150
151
152
|
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));
}
}
return false;
|
94b2b13d
Pedro Roque
PHACT source
|
153
|
|
4d26a735
Pedro Roque
Increased recogni...
|
154
155
156
157
158
|
} else
#endif
if (x->min == k) {
set++;
}
|
94b2b13d
Pedro Roque
PHACT source
|
159
|
}
|
94b2b13d
Pedro Roque
PHACT source
|
160
161
162
163
164
165
|
// if less than n variables are set to k
if (set < n) {
if (explored) {
fprintf(stderr, "\nError: Constraint AT_LEAST (%d) not respected:\n", c->c_id);
|
4d26a735
Pedro Roque
Increased recogni...
|
166
|
|
94b2b13d
Pedro Roque
PHACT source
|
167
168
|
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),
|
4d26a735
Pedro Roque
Increased recogni...
|
169
170
171
172
173
174
175
176
177
|
b_get_max_val(&c->c_vs[i]->domain_b),
b_cnt_vals(&c->c_vs[i]->domain_b));
}
}
return false;
}
return true;
}
|
94b2b13d
Pedro Roque
PHACT source
|
178
179
180
|
#endif
|
4d26a735
Pedro Roque
Increased recogni...
|
181
|
#if CS_AT_LEAST == 1
|
94b2b13d
Pedro Roque
PHACT source
|
182
183
184
185
186
187
188
189
190
|
/*
* Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_least constraint
* #{i | X[i] = k} >= n
* 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
|
94b2b13d
Pedro Roque
PHACT source
|
191
192
193
194
|
* vs_id_to_prop_ - circular vector with the ids of the variables to propagate
*/
CUDA_FUNC void at_least_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) {
|
94b2b13d
Pedro Roque
PHACT source
|
195
|
|
4d26a735
Pedro Roque
Increased recogni...
|
196
|
int n = c_consts[0];
|
94b2b13d
Pedro Roque
PHACT source
|
197
|
int k = c_consts[1];
|
94b2b13d
Pedro Roque
PHACT source
|
198
199
|
int set = 0;
int possible = 0;
|
4d26a735
Pedro Roque
Increased recogni...
|
200
|
bool contains;
|
94b2b13d
Pedro Roque
PHACT source
|
201
|
int x_id;
|
4d26a735
Pedro Roque
Increased recogni...
|
202
203
|
bool changed = 0;
int i;
|
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
260
261
262
263
|
for (i = 0; i < current_cs->n_c_vs; i++) {
CHECK_TTL(ttl_ctr, 37)
x_id = vs_per_c_idx[i];
// number of variables already set to k
if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
set++;
// number of variables that may be set to k
} else {
cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
if (contains) {
possible++;
}
}
}
// if there are not enough variables to set to k
if (set + possible < n) {
*prop_ok = 0;
return;
}
// if the sum of the variables that contain k are n, assign all of them to k
if (set + possible == n) {
for (i = 0; possible > 0; i++) {
x_id = vs_per_c_idx[i];
CHECK_TTL(ttl_ctr, 38)
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
}
}
#if CS_R_AT_LEAST == 1
/*
* Validate at_least constraint to be normally propagated, when reified
* #{i | X[i] = k} >= n
* 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
* 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_least_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];
|
4d26a735
Pedro Roque
Increased recogni...
|
264
|
int k = c_consts[1];
|
94b2b13d
Pedro Roque
PHACT source
|
265
266
267
268
|
int set = 0;
int possible = 0;
bool contains;
int x_id;
|
4d26a735
Pedro Roque
Increased recogni...
|
269
270
|
int i;
|
94b2b13d
Pedro Roque
PHACT source
|
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
|
for (i = 0; i < current_cs->n_c_vs; i++) {
CHECK_TTL(ttl_ctr, 39)
x_id = vs_per_c_idx[i];
// number of variables already set to k
if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
set++;
// number of variables that may be set to k
} else {
cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
if (contains) {
possible++;
}
}
}
// if there are not enough variables to set to k
if (set + possible < 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
}
// constraint already fixed
if (set >= n) {
|
4d26a735
Pedro Roque
Increased recogni...
|
299
|
cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 0 TTL_CTR_V);
|
94b2b13d
Pedro Roque
PHACT source
|
300
301
302
303
304
305
306
307
308
|
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...
|
309
|
* Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_least opposite constraint
|
94b2b13d
Pedro Roque
PHACT source
|
310
311
312
313
314
315
316
317
318
319
320
|
* #{i | X[i] = k} < n
* 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_least_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) {
|
4d26a735
Pedro Roque
Increased recogni...
|
321
|
int n = c_consts[0];
|
94b2b13d
Pedro Roque
PHACT source
|
322
|
int k = c_consts[1];
|
94b2b13d
Pedro Roque
PHACT source
|
323
324
|
int set = 0;
int possible = 0;
|
4d26a735
Pedro Roque
Increased recogni...
|
325
|
bool contains;
|
94b2b13d
Pedro Roque
PHACT source
|
326
|
int x_id;
|
4d26a735
Pedro Roque
Increased recogni...
|
327
328
|
bool changed = 0;
int i;
|
94b2b13d
Pedro Roque
PHACT source
|
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
381
|
for (i = 0; i < current_cs->n_c_vs; i++) {
CHECK_TTL(ttl_ctr, 206)
x_id = vs_per_c_idx[i];
// if more than n-1 variables are already set to k, return 0
if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
if (++set >= n) {
*prop_ok = 0;
return;
}
// number of variables that may be set to k
} else {
cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
if (contains) {
possible++;
}
}
}
// if all the variables already assigned to k are n-1, remove k from the other variables
if (set == n - 1) {
for (i = 0; possible > 0; i++) {
x_id = vs_per_c_idx[i];
CHECK_TTL(ttl_ctr, 207)
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
}
}
#endif
CUDA_FUNC void at_least_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_LEAST == 0
at_least_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_LEAST == 1
|
4d26a735
Pedro Roque
Increased recogni...
|
382
383
384
385
386
387
388
389
390
391
392
|
if (current_cs->reified == 1) {
if (V_N_VALS(vs_prop_[current_cs->reif_var_id]) > 1) {
at_least_reif(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_ CS_IGNORE_CALL TTL_CTR_V);
} else {
if (V_MIN(vs_prop_[current_cs->reif_var_id]) == 1) {
at_least_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_least_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
|
94b2b13d
Pedro Roque
PHACT source
|
393
394
395
396
397
398
|
*propagated = true;
#endif
}
} else {
at_least_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
|
4d26a735
Pedro Roque
Increased recogni...
|
399
|
*propagated = true;
|
94b2b13d
Pedro Roque
PHACT source
|
400
401
402
403
404
|
#endif
}
#endif
}
#endif
|
4d26a735
Pedro Roque
Increased recogni...
|
|
|
94b2b13d
Pedro Roque
PHACT source
|
|
|