/* * array_bool_element.c * * Created on: 07/02/2020 * Author: Pedro */ #ifndef __OPENCL_VERSION__ #include #include #include "array_bool_element.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 array_bool_element type and return the constraint ID * 1 ≤ y <= n ∧ X[y] = z * X_ids - vector with the ID of the boolean variables that may be in the domain of idxs_v_id variable * n_vs - maximum number of variables in X vector * y_id - ID of the boolean variable whose domain are the index of the variables in elements vector * z_id - ID of the boolean variable that should contain all the values in all the vs_id[idxs_v_id] domains */ unsigned int c_array_bool_element(unsigned int *X_ids, unsigned int n_vs, unsigned int y_id, unsigned int z_id) { var *y = &VS[y_id]; unsigned int i; if (y->max > n_vs) { v_del_gt(y, (int) n_vs); if (y->n_vals == 0) { printf("\nConstraint ARRAY_BOOL_ELEMENT makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (y->min == 0) { v_del_val(y, 0); if (y->n_vals == 0) { printf("\nConstraint ARRAY_BOOL_ELEMENT makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } // set to include in kernel compilation USE_CS[ARRAY_BOOL_ELEMENT] = 1; USE_NON_CS_REIFI[ARRAY_BOOL_ELEMENT] = 1; unsigned int *c_vs = malloc((n_vs + 2) * sizeof(unsigned int)); for (i = 0; i < n_vs; i++) { c_vs[i] = X_ids[i]; } c_vs[n_vs] = y_id; c_vs[n_vs + 1] = z_id; // creates a new generic constraint unsigned int c_id = c_new(c_vs, n_vs + 2, NULL, 0, -1); // pointers to this type of constraint functions CS[c_id].kind = ARRAY_BOOL_ELEMENT; CS[c_id].check_sol_f = &array_bool_element_check; CS[c_id].constant_val = 0; free(c_vs); return c_id; } /* * Creates a new reified constraint of the array_bool_element type and return the constraint ID * 1 ≤ y <= n ∧ X[y] = z * X_ids - vector with the ID of the boolean variables that may be in the domain of idxs_v_id variable * n_vs - maximum number of variables in X vector * y_id - ID of the boolean variable whose domain are the index of the variables in elements vector * z_id - ID of the boolean variable that should contain all the values in all the vs_id[idxs_v_id] domains * reif_v_id - ID of the reification variable */ unsigned int c_array_bool_element_reif(unsigned int *X_ids, unsigned int n_vs, unsigned int y_id, unsigned int z_id, int reif_v_id) { var *y = &VS[y_id]; 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) { printf("\nConstraint ARRAY_BOOL_ELEMENT_REIF makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (y->max > n_vs) { v_del_gt(y, (int) n_vs); if (y->n_vals == 0) { printf("\nConstraint ARRAY_BOOL_ELEMENT_REIF makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (y->min == 0) { v_del_val(y, 0); if (y->n_vals == 0) { printf("\nConstraint ARRAY_BOOL_ELEMENT_REIF makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } // set to include in kernel compilation USE_CS[ARRAY_BOOL_ELEMENT] = 1; USE_CS_REIFI[ARRAY_BOOL_ELEMENT] = 1; unsigned int *c_vs = malloc((n_vs + 2) * sizeof(unsigned int)); for (i = 0; i < n_vs; i++) { c_vs[i] = X_ids[i]; } c_vs[n_vs] = y_id; c_vs[n_vs + 1] = z_id; // creates a new generic constraint unsigned int c_id = c_new(c_vs, n_vs + 2, NULL, 0, reif_v_id); // pointers to this type of constraint functions CS[c_id].kind = ARRAY_BOOL_ELEMENT; CS[c_id].check_sol_f = &array_bool_element_check; CS[c_id].constant_val = 0; free(c_vs); return c_id; } /* * Return true if the array_bool_element constraint is respected or false if not * 1 ≤ y <= n ∧ X[y] = z * 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 array_bool_element_check(constr *c, bool explored) { var **X = c->c_vs; var *y = c->c_vs[c->n_c_vs - 2]; var *z = c->c_vs[c->n_c_vs - 1]; unsigned int i; if (!explored) { for (i = 0; i < c->n_c_vs; i++) { if (c->c_vs[i]->n_vals > 1) { return false; } } } if (c->reified && VS[c->reif_v_id].n_vals > 1) { if (explored) { fprintf(stderr, "\nError: Reification variable of constraint ARRAY_BOOL_ELEMENT_REIF (%d) has 2 values.\n", c->c_id); return false; } } if (((!c->reified || (c->reified && VS[c->reif_v_id].min == 1)) && X[y->min - 1]->min != z->min) || (c->reified && VS[c->reif_v_id].min == 0 && X[y->min - 1]->min == z->min)) { if (explored) { if (c->reified) { fprintf(stderr, "\nError: Constraint ARRAY_BOOL_ELEMENT_REIF (%d) not respected:\n", c->c_id); fprintf(stderr, "Reif ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->reif_v_id, b_get_min_val(&VS[c->reif_v_id].domain_b), b_get_max_val(&VS[c->reif_v_id].domain_b), b_cnt_vals(&VS[c->reif_v_id].domain_b)); } else { fprintf(stderr, "\nError: Constraint ARRAY_BOOL_ELEMENT (%d) not respected:\n", c->c_id); } fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", X[y->min - 1]->v_id, b_get_min_val(&X[y->min - 1]->domain_b), b_get_max_val(&X[y->min - 1]->domain_b), b_cnt_vals(&X[y->min - 1]->domain_b)); fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", y->v_id, b_get_min_val(&y->domain_b), b_get_max_val(&y->domain_b), b_cnt_vals(&y->domain_b)); fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", z->v_id, b_get_min_val(&z->domain_b), b_get_max_val(&z->domain_b), b_cnt_vals(&z->domain_b)); } return false; } return true; } #endif #if CS_ARRAY_BOOL_ELEMENT == 1 /* * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID array_bool_element constraint * 1 ≤ y <= n ∧ X[y] = z * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order * vs_prop_ - all CSP variables with current step values * prop_v_id - ID of the variable 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 * prop_ok - will be set to 1 or 0 if the constraint is respected or not */ CUDA_FUNC void array_bool_element_prop( CL_INTS_MEM int *vs_per_c_idx, CL_MEMORY VARS_PROP *vs_prop_, unsigned int prop_v_id, CL_CS_MEM cl_constr *current_cs, CL_MEMORY unsigned short *vs_id_to_prop_, bool *prop_ok CS_IGNORE_FUNC TTL_CTR) { if (current_cs->reified == 1 && current_cs->reif_var_id == prop_v_id) { return; } int y_id = vs_per_c_idx[current_cs->n_c_vs - 2]; // ID of the variable whose domain are the index of the variables in elements vector int z_id = vs_per_c_idx[current_cs->n_c_vs - 1]; // ID of the variable that should contain all the values in all the vars_ids[var_id] domains int x_id, x_id_min, x_id_max; bool contains = 0; int n_contains = 0; bool changed = 0; int i; x_id_min = V_MIN(vs_prop_[y_id]) - 1; // minimum ID of the variable included in vars_ids x_id_max = V_MAX(vs_prop_[y_id]) - 1; // maximum ID of the variable included in vars_ids if (prop_v_id != (unsigned int) y_id && prop_v_id != (unsigned int) z_id) { if (V_N_VALS(vs_prop_[y_id]) > 1) { for (i = x_id_min; i <= x_id_max; i++) { CHECK_TTL(ttl_ctr, 177) x_id = vs_per_c_idx[i]; if ((unsigned int) x_id == prop_v_id) { cl_v_contains_val_m(&contains, &vs_prop_[y_id], i + 1 TTL_CTR_V); if (contains) { if (V_MIN(vs_prop_[x_id]) != V_MIN(vs_prop_[z_id]) && V_MAX(vs_prop_[x_id]) != V_MAX(vs_prop_[z_id])) { cl_v_del_val_m(&changed, &vs_prop_[y_id], i + 1 TTL_CTR_V); if (changed) { if (V_IS_EMPTY(vs_prop_[y_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, y_id); } // y was set singleton if (V_N_VALS(vs_prop_[y_id]) == 1) { x_id = vs_per_c_idx[V_MIN(vs_prop_[y_id]) - 1]; cl_v_intersect_v_m(&changed, &vs_prop_[x_id], &vs_prop_[z_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[x_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } cl_v_intersect_v_m(&changed, &vs_prop_[z_id], &vs_prop_[x_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } } } } break; } } if ((unsigned int) x_id != prop_v_id || !contains) { return; } // y is singleton and its x is to propagate } else if ((unsigned int) vs_per_c_idx[V_MIN(vs_prop_[y_id]) - 1] == prop_v_id) { x_id = vs_per_c_idx[V_MIN(vs_prop_[y_id]) - 1]; cl_v_intersect_v_m(&changed, &vs_prop_[x_id], &vs_prop_[z_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[x_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } cl_v_intersect_v_m(&changed, &vs_prop_[z_id], &vs_prop_[x_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } return; // other x not in y to propagate } else { return; } } if ((prop_v_id == (unsigned int) y_id || prop_v_id == (unsigned int) z_id) && V_N_VALS(vs_prop_[y_id]) == 1) { x_id = vs_per_c_idx[V_MIN(vs_prop_[y_id]) - 1]; cl_v_intersect_v_m(&changed, &vs_prop_[x_id], &vs_prop_[z_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[x_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } cl_v_intersect_v_m(&changed, &vs_prop_[z_id], &vs_prop_[x_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE if (V_N_VALS(vs_prop_[z_id]) == 1) { cs_ignore[current_cs->c_id] = 1; } #endif return; } // if z is singleton and is to propagate, remove from y all the variables that doesn't contain the z value if (prop_v_id == (unsigned int) z_id && V_N_VALS(vs_prop_[z_id]) == 1) { for (i = x_id_min; i <= x_id_max; i++) { CHECK_TTL(ttl_ctr, 55) x_id = vs_per_c_idx[i]; cl_v_contains_val_m(&contains, &vs_prop_[y_id], i + 1 TTL_CTR_V); if (contains) { if (V_MIN(vs_prop_[x_id]) != V_MIN(vs_prop_[z_id]) && V_MAX(vs_prop_[x_id]) != V_MAX(vs_prop_[z_id])) { cl_v_del_val_m(&changed, &vs_prop_[y_id], i + 1 TTL_CTR_V); if (changed) { if (V_IS_EMPTY(vs_prop_[y_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, y_id); } } else { n_contains++; } } } // y was set singleton x_id = vs_per_c_idx[V_MIN(vs_prop_[y_id]) - 1]; if (n_contains == 1 && V_N_VALS(vs_prop_[x_id]) > 1) { cl_v_intersect_v_m(&changed, &vs_prop_[x_id], &vs_prop_[z_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[x_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } cl_v_intersect_v_m(&changed, &vs_prop_[z_id], &vs_prop_[x_id] TTL_CTR_V); if (changed) { // if the intersection between the domains of X[y] and z is empty if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } } } } #if CS_R_ARRAY_BOOL_ELEMENT == 1 /* * Validate array_bool_element constraint to be normally propagated, when reified * 1 ≤ y <= n ∧ X[y] = z * vs_per_c_idx - vector with all constrained variables ID 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 array_bool_element_reif( CL_INTS_MEM int *vs_per_c_idx, 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 y_id = vs_per_c_idx[current_cs->n_c_vs - 2]; // ID of the variable whose domain are the index of the variables in elements vector int z_id = vs_per_c_idx[current_cs->n_c_vs - 1]; // ID of the variable that should contain all the values in all the vars_ids[var_id] domains int x_id; VARS_PROP y; bool contains; bool changed = 0; int i; if (V_N_VALS(vs_prop_[y_id]) == 1) { x_id = vs_per_c_idx[V_MIN(vs_prop_[y_id]) - 1]; if (V_MIN(vs_prop_[x_id]) != V_MIN(vs_prop_[z_id]) && V_MAX(vs_prop_[x_id]) != V_MAX(vs_prop_[z_id])) { 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 if (V_N_VALS(vs_prop_[z_id]) == 1) { cs_ignore[current_cs->c_id] = 1; } #endif return; } // constraint already fixed if (V_N_VALS(vs_prop_[z_id]) == 1) { 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 if (V_N_VALS(vs_prop_[z_id]) == 1) { cs_ignore[current_cs->c_id] = 1; } #endif } } // if z is singleton, remove from y all the variables that doesn't contain the z value if (V_N_VALS(vs_prop_[z_id]) == 1) { int x_id_min = V_MIN(vs_prop_[y_id]) - 1; // minimum ID of the variable included in vars_ids int x_id_max = V_MAX(vs_prop_[y_id]) - 1; // maximum ID of the variable included in vars_ids cl_v_copy_pm(&y, &vs_prop_[y_id] TTL_CTR_V); for (i = x_id_min; i <= x_id_max; i++) { CHECK_TTL(ttl_ctr, 56) x_id = vs_per_c_idx[i]; cl_v_contains_val_m(&contains, &vs_prop_[y_id], i + 1 TTL_CTR_V); if (contains) { cl_v_contains_val_m(&contains, &vs_prop_[x_id], V_MIN(vs_prop_[z_id]) TTL_CTR_V); if (!contains) { cl_v_del_val_n(&changed, &y, i TTL_CTR_V); if (V_IS_EMPTY(y)) { 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)); return; } } } } // constraint already fixed if (V_N_VALS(vs_prop_[y_id]) == 1) { 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 if (V_N_VALS(vs_prop_[z_id]) == 1) { cs_ignore[current_cs->c_id] = 1; } #endif } } } /* * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID array_bool_element opposite constraint * 1 ≤ y <= n ∧ X[y] != z * vs_per_c_idx - vector with all constrained variables ID 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 * prop_ok - will be set to 1 or 0 if the constraint is respected or not */ CUDA_FUNC void array_bool_element_opposite( CL_INTS_MEM int *vs_per_c_idx, 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 y_id = vs_per_c_idx[current_cs->n_c_vs - 2]; // ID of the variable whose domain are the index of the variables in elements vector int z_id = vs_per_c_idx[current_cs->n_c_vs - 1]; // ID of the variable that should contain all the values in all the vars_ids[var_id] domains int x_id; bool changed; if (V_N_VALS(vs_prop_[y_id]) == 1 && V_N_VALS(vs_prop_[z_id]) == 1) { x_id = vs_per_c_idx[V_MIN(vs_prop_[y_id]) - 1]; cl_v_del_val_m(&changed, &vs_prop_[x_id], V_MIN(vs_prop_[z_id]) TTL_CTR_V); if (changed) { // if the removal of z from X[i] makes X[i] empty if (V_IS_EMPTY(vs_prop_[x_id])) { *prop_ok = 0; return; } 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 /* * Decides the propagator to call for this constraint * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order * vs_prop_ - all CSP variables with current step values * prop_v_id - ID of the variable 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 * prop_ok - will be set to 1 or 0 if the constraint is respected or not */ CUDA_FUNC void array_bool_element_propagate( CL_INTS_MEM int *vs_per_c_idx, CL_MEMORY VARS_PROP *vs_prop_, unsigned int prop_v_id, 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_ARRAY_BOOL_ELEMENT == 0 array_bool_element_prop(vs_per_c_idx, vs_prop_, prop_v_id, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); #if CL_STATS == 1 *propagated = true; #endif #elif CS_R_ARRAY_BOOL_ELEMENT == 1 if (current_cs->reified == 1) { if (V_N_VALS(vs_prop_[current_cs->reif_var_id]) > 1) { array_bool_element_reif(vs_per_c_idx, 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) { array_bool_element_prop(vs_per_c_idx, vs_prop_, prop_v_id, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); } else { array_bool_element_opposite(vs_per_c_idx, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); } #if CL_STATS == 1 *propagated = true; #endif } } else { array_bool_element_prop(vs_per_c_idx, vs_prop_, prop_v_id, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); #if CL_STATS == 1 *propagated = true; #endif } #endif } #endif