isl_convex_hull.c File Reference

#include "isl_lp.h"
#include "isl_map.h"
#include "isl_map_private.h"
#include "isl_mat.h"
#include "isl_set.h"
#include "isl_seq.h"
#include "isl_equalities.h"
#include "isl_tab.h"

Include dependency graph for isl_convex_hull.c:

Go to the source code of this file.

Classes

struct  max_constraint
struct  sh_data_entry
struct  sh_data
struct  ineq_cmp_data

Functions

static struct isl_basic_set * uset_convex_hull_wrap_bounded (struct isl_set *set)
static void swap_ineq (struct isl_basic_map *bmap, unsigned i, unsigned j)
int isl_basic_map_constraint_is_redundant (struct isl_basic_map **bmap, isl_int *c, isl_int *opt_n, isl_int *opt_d)
int isl_basic_set_constraint_is_redundant (struct isl_basic_set **bset, isl_int *c, isl_int *opt_n, isl_int *opt_d)
struct isl_basic_map * isl_basic_map_convex_hull (struct isl_basic_map *bmap)
struct isl_basic_set * isl_basic_set_convex_hull (struct isl_basic_set *bset)
static int uset_is_bound (struct isl_ctx *ctx, struct isl_set *set, isl_int *c, unsigned len)
static int is_independent_bound (struct isl_ctx *ctx, struct isl_set *set, isl_int *c, struct isl_mat *dirs, int n)
static struct isl_mat * independent_bounds (struct isl_ctx *ctx, struct isl_set *set)
static struct isl_basic_set * isl_basic_set_set_rational (struct isl_basic_set *bset)
static struct isl_set * isl_set_set_rational (struct isl_set *set)
static struct isl_basic_set * isl_basic_set_add_equality (struct isl_ctx *ctx, struct isl_basic_set *bset, isl_int *c)
static struct isl_set * isl_set_add_equality (struct isl_ctx *ctx, struct isl_set *set, isl_int *c)
static struct isl_basic_set * wrap_constraints (struct isl_set *set)
static isl_int * wrap_facet (struct isl_set *set, isl_int *facet, isl_int *ridge)
static struct isl_mat * initial_facet_constraint (struct isl_ctx *ctx, struct isl_set *set, struct isl_mat *bounds)
static struct isl_basic_set * compute_facet (struct isl_set *set, isl_int *c)
static struct isl_basic_set * extend (struct isl_basic_set *hull, struct isl_set *set)
static struct isl_basic_set * convex_hull_1d (struct isl_ctx *ctx, struct isl_set *set)
static struct isl_set * set_project_out (struct isl_ctx *ctx, struct isl_set *set, unsigned n)
static struct isl_basic_set * convex_hull_0d (struct isl_set *set)
static struct isl_basic_set * convex_hull_pair_elim (struct isl_basic_set *bset1, struct isl_basic_set *bset2)
static int isl_basic_set_is_bounded (struct isl_basic_set *bset)
static int isl_set_is_bounded (struct isl_set *set)
static struct isl_basic_set * induced_lineality_space (struct isl_basic_set *bset1, struct isl_basic_set *bset2)
static struct isl_basic_set * uset_convex_hull (struct isl_set *set)
static struct isl_basic_set * modulo_lineality (struct isl_set *set, struct isl_basic_set *lin)
static struct isl_basic_set * valid_direction_lp (struct isl_basic_set *bset1, struct isl_basic_set *bset2)
static struct isl_vec * valid_direction (struct isl_basic_set *bset1, struct isl_basic_set *bset2)
static struct isl_basic_set * homogeneous_map (struct isl_basic_set *bset, struct isl_mat *T)
static struct isl_basic_set * convex_hull_pair_pointed (struct isl_basic_set *bset1, struct isl_basic_set *bset2)
static struct isl_basic_set * convex_hull_pair (struct isl_basic_set *bset1, struct isl_basic_set *bset2)
static struct isl_basic_set * ubasic_set_lineality_space (struct isl_basic_set *bset)
static struct isl_basic_set * uset_combined_lineality_space (struct isl_set *set)
static struct isl_basic_set * uset_convex_hull_unbounded (struct isl_set *set)
static struct isl_basic_set * initial_hull (struct isl_basic_set *hull, struct isl_set *set)
static int max_constraint_equal (const void *entry, const void *val)
static void update_constraint (struct isl_ctx *ctx, struct isl_hash_table *table, isl_int *con, unsigned len, int n, int ineq)
static int has_constraint (struct isl_ctx *ctx, struct isl_hash_table *table, isl_int *con, unsigned len, int n)
static struct isl_basic_set * common_constraints (struct isl_basic_set *hull, struct isl_set *set, int *is_hull)
static struct isl_basic_set * proto_hull (struct isl_set *set, int *is_hull)
static struct isl_basic_set * uset_convex_hull_wrap (struct isl_set *set)
static struct isl_basic_set * modulo_affine_hull (struct isl_ctx *ctx, struct isl_set *set, struct isl_basic_set *affine_hull)
struct isl_basic_map * isl_map_convex_hull (struct isl_map *map)
struct isl_basic_set * isl_set_convex_hull (struct isl_set *set)
static void sh_data_free (struct sh_data *data)
static int has_ineq (const void *entry, const void *val)
static int hash_ineq (struct isl_ctx *ctx, struct isl_hash_table *table, isl_int *ineq, unsigned len)
static int hash_basic_set (struct isl_hash_table *table, struct isl_basic_set *bset)
static struct sh_data * sh_data_alloc (struct isl_set *set, unsigned n_ineq)
static int is_bound (struct sh_data *data, struct isl_set *set, int j, isl_int *ineq)
static struct isl_basic_set * add_bound (struct isl_basic_set *hull, struct sh_data *data, struct isl_set *set, int i, isl_int *ineq)
static struct isl_basic_set * add_bounds (struct isl_basic_set *bset, struct sh_data *data, struct isl_set *set, int i)
static struct isl_basic_set * uset_simple_hull (struct isl_set *set)
struct isl_basic_map * isl_map_simple_hull (struct isl_map *map)
struct isl_basic_set * isl_set_simple_hull (struct isl_set *set)
static struct isl_basic_set * set_bounds (struct isl_set *set, int dim)
struct isl_basic_set * isl_set_bounded_simple_hull (struct isl_set *set)

Function Documentation

static struct isl_basic_set* add_bound ( struct isl_basic_set *  hull,
struct sh_data *  data,
struct isl_set *  set,
int  i,
isl_int *  ineq 
) [static, read]

Definition at line 2138 of file isl_convex_hull.c.

02140 {
02141         uint32_t c_hash;
02142         struct ineq_cmp_data v;
02143         struct isl_hash_table_entry *entry;
02144         int j, k;
02145 
02146         if (!hull)
02147                 return NULL;
02148 
02149         v.len = isl_basic_set_total_dim(hull);
02150         v.p = ineq;
02151         c_hash = isl_seq_hash(ineq + 1, v.len, isl_hash_init());
02152 
02153         entry = isl_hash_table_find(hull->ctx, data->hull_table, c_hash,
02154                                         has_ineq, &v, 0);
02155         if (entry)
02156                 return hull;
02157 
02158         for (j = 0; j < i; ++j) {
02159                 entry = isl_hash_table_find(hull->ctx, data->p[j].table,
02160                                                 c_hash, has_ineq, &v, 0);
02161                 if (entry)
02162                         break;
02163         }
02164         if (j < i)
02165                 return hull;
02166 
02167         k = isl_basic_set_alloc_inequality(hull);
02168         isl_seq_cpy(hull->ineq[k], ineq, 1 + v.len);
02169         if (k < 0)
02170                 goto error;
02171 
02172         for (j = 0; j < i; ++j) {
02173                 int bound;
02174                 bound = is_bound(data, set, j, hull->ineq[k]);
02175                 if (bound < 0)
02176                         goto error;
02177                 if (!bound)
02178                         break;
02179         }
02180         if (j < i) {
02181                 isl_basic_set_free_inequality(hull, 1);
02182                 return hull;
02183         }
02184 
02185         for (j = i + 1; j < set->n; ++j) {
02186                 int bound, neg;
02187                 isl_int *ineq_j;
02188                 entry = isl_hash_table_find(hull->ctx, data->p[j].table,
02189                                                 c_hash, has_ineq, &v, 0);
02190                 if (entry) {
02191                         ineq_j = entry->data;
02192                         neg = isl_seq_is_neg(ineq_j + 1,
02193                                              hull->ineq[k] + 1, v.len);
02194                         if (neg)
02195                                 isl_int_neg(ineq_j[0], ineq_j[0]);
02196                         if (isl_int_gt(ineq_j[0], hull->ineq[k][0]))
02197                                 isl_int_set(hull->ineq[k][0], ineq_j[0]);
02198                         if (neg)
02199                                 isl_int_neg(ineq_j[0], ineq_j[0]);
02200                         continue;
02201                 }
02202                 bound = is_bound(data, set, j, hull->ineq[k]);
02203                 if (bound < 0)
02204                         goto error;
02205                 if (!bound)
02206                         break;
02207         }
02208         if (j < set->n) {
02209                 isl_basic_set_free_inequality(hull, 1);
02210                 return hull;
02211         }
02212 
02213         entry = isl_hash_table_find(hull->ctx, data->hull_table, c_hash,
02214                                         has_ineq, &v, 1);
02215         if (!entry)
02216                 goto error;
02217         entry->data = hull->ineq[k];
02218 
02219         return hull;
02220 error:
02221         isl_basic_set_free(hull);
02222         return NULL;
02223 }

Here is the call graph for this function:

static struct isl_basic_set* add_bounds ( struct isl_basic_set *  bset,
struct sh_data *  data,
struct isl_set *  set,
int  i 
) [static, read]

Definition at line 2229 of file isl_convex_hull.c.

02231 {
02232         int j, k;
02233         unsigned dim = isl_basic_set_total_dim(bset);
02234 
02235         for (j = 0; j < set->p[i]->n_eq; ++j) {
02236                 for (k = 0; k < 2; ++k) {
02237                         isl_seq_neg(set->p[i]->eq[j], set->p[i]->eq[j], 1+dim);
02238                         add_bound(bset, data, set, i, set->p[i]->eq[j]);
02239                 }
02240         }
02241         for (j = 0; j < set->p[i]->n_ineq; ++j)
02242                 add_bound(bset, data, set, i, set->p[i]->ineq[j]);
02243         return bset;
02244 }

Here is the call graph for this function:

static struct isl_basic_set* common_constraints ( struct isl_basic_set *  hull,
struct isl_set *  set,
int *  is_hull 
) [static, read]

Definition at line 1638 of file isl_convex_hull.c.

01640 {
01641         int i, j, s, n;
01642         int min_constraints;
01643         int best;
01644         struct max_constraint *constraints = NULL;
01645         struct isl_hash_table *table = NULL;
01646         unsigned total;
01647 
01648         *is_hull = 0;
01649 
01650         for (i = 0; i < set->n; ++i)
01651                 if (set->p[i]->n_eq == 0)
01652                         break;
01653         if (i >= set->n)
01654                 return hull;
01655         min_constraints = set->p[i]->n_ineq;
01656         best = i;
01657         for (i = best + 1; i < set->n; ++i) {
01658                 if (set->p[i]->n_eq != 0)
01659                         continue;
01660                 if (set->p[i]->n_ineq >= min_constraints)
01661                         continue;
01662                 min_constraints = set->p[i]->n_ineq;
01663                 best = i;
01664         }
01665         constraints = isl_calloc_array(hull->ctx, struct max_constraint,
01666                                         min_constraints);
01667         if (!constraints)
01668                 return hull;
01669         table = isl_alloc_type(hull->ctx, struct isl_hash_table);
01670         if (isl_hash_table_init(hull->ctx, table, min_constraints))
01671                 goto error;
01672 
01673         total = isl_dim_total(set->dim);
01674         for (i = 0; i < set->p[best]->n_ineq; ++i) {
01675                 constraints[i].c = isl_mat_sub_alloc(hull->ctx,
01676                         set->p[best]->ineq + i, 0, 1, 0, 1 + total);
01677                 if (!constraints[i].c)
01678                         goto error;
01679                 constraints[i].ineq = 1;
01680         }
01681         for (i = 0; i < min_constraints; ++i) {
01682                 struct isl_hash_table_entry *entry;
01683                 uint32_t c_hash;
01684                 c_hash = isl_seq_hash(constraints[i].c->row[0] + 1, total,
01685                                         isl_hash_init());
01686                 entry = isl_hash_table_find(hull->ctx, table, c_hash,
01687                         max_constraint_equal, constraints[i].c->row[0] + 1, 1);
01688                 if (!entry)
01689                         goto error;
01690                 isl_assert(hull->ctx, !entry->data, goto error);
01691                 entry->data = &constraints[i];
01692         }
01693 
01694         n = 0;
01695         for (s = 0; s < set->n; ++s) {
01696                 if (s == best)
01697                         continue;
01698 
01699                 for (i = 0; i < set->p[s]->n_eq; ++i) {
01700                         isl_int *eq = set->p[s]->eq[i];
01701                         for (j = 0; j < 2; ++j) {
01702                                 isl_seq_neg(eq, eq, 1 + total);
01703                                 update_constraint(hull->ctx, table,
01704                                                             eq, total, n, 0);
01705                         }
01706                 }
01707                 for (i = 0; i < set->p[s]->n_ineq; ++i) {
01708                         isl_int *ineq = set->p[s]->ineq[i];
01709                         update_constraint(hull->ctx, table, ineq, total, n,
01710                                 set->p[s]->n_eq == 0);
01711                 }
01712                 ++n;
01713         }
01714 
01715         for (i = 0; i < min_constraints; ++i) {
01716                 if (constraints[i].count < n)
01717                         continue;
01718                 if (!constraints[i].ineq)
01719                         continue;
01720                 j = isl_basic_set_alloc_inequality(hull);
01721                 if (j < 0)
01722                         goto error;
01723                 isl_seq_cpy(hull->ineq[j], constraints[i].c->row[0], 1 + total);
01724         }
01725 
01726         for (s = 0; s < set->n; ++s) {
01727                 if (set->p[s]->n_eq)
01728                         continue;
01729                 if (set->p[s]->n_ineq != hull->n_ineq)
01730                         continue;
01731                 for (i = 0; i < set->p[s]->n_ineq; ++i) {
01732                         isl_int *ineq = set->p[s]->ineq[i];
01733                         if (!has_constraint(hull->ctx, table, ineq, total, n))
01734                                 break;
01735                 }
01736                 if (i == set->p[s]->n_ineq)
01737                         *is_hull = 1;
01738         }
01739 
01740         isl_hash_table_clear(table);
01741         for (i = 0; i < min_constraints; ++i)
01742                 isl_mat_free(hull->ctx, constraints[i].c);
01743         free(constraints);
01744         free(table);
01745         return hull;
01746 error:
01747         isl_hash_table_clear(table);
01748         free(table);
01749         if (constraints)
01750                 for (i = 0; i < min_constraints; ++i)
01751                         isl_mat_free(hull->ctx, constraints[i].c);
01752         free(constraints);
01753         return hull;
01754 }

Here is the call graph for this function:

static struct isl_basic_set* compute_facet ( struct isl_set *  set,
isl_int *  c 
) [static, read]

Definition at line 619 of file isl_convex_hull.c.

00620 {
00621         struct isl_mat *m, *U, *Q;
00622         struct isl_basic_set *facet = NULL;
00623         struct isl_ctx *ctx;
00624         unsigned dim;
00625 
00626         ctx = set->ctx;
00627         set = isl_set_copy(set);
00628         dim = isl_set_n_dim(set);
00629         m = isl_mat_alloc(set->ctx, 2, 1 + dim);
00630         if (!m)
00631                 goto error;
00632         isl_int_set_si(m->row[0][0], 1);
00633         isl_seq_clr(m->row[0]+1, dim);
00634         isl_seq_cpy(m->row[1], c, 1+dim);
00635         U = isl_mat_right_inverse(set->ctx, m);
00636         Q = isl_mat_right_inverse(set->ctx, isl_mat_copy(set->ctx, U));
00637         U = isl_mat_drop_cols(set->ctx, U, 1, 1);
00638         Q = isl_mat_drop_rows(set->ctx, Q, 1, 1);
00639         set = isl_set_preimage(set, U);
00640         facet = uset_convex_hull_wrap_bounded(set);
00641         facet = isl_basic_set_preimage(facet, Q);
00642         isl_assert(ctx, facet->n_eq == 0, goto error);
00643         return facet;
00644 error:
00645         isl_basic_set_free(facet);
00646         isl_set_free(set);
00647         return NULL;
00648 }

Here is the call graph for this function:

static struct isl_basic_set* convex_hull_0d ( struct isl_set *  set  )  [static, read]

Definition at line 858 of file isl_convex_hull.c.

00859 {
00860         struct isl_basic_set *convex_hull;
00861 
00862         if (!set)
00863                 return NULL;
00864 
00865         if (isl_set_is_empty(set))
00866                 convex_hull = isl_basic_set_empty(isl_dim_copy(set->dim));
00867         else
00868                 convex_hull = isl_basic_set_universe(isl_dim_copy(set->dim));
00869         isl_set_free(set);
00870         return convex_hull;
00871 }

Here is the call graph for this function:

static struct isl_basic_set* convex_hull_1d ( struct isl_ctx *  ctx,
struct isl_set *  set 
) [static, read]

Definition at line 730 of file isl_convex_hull.c.

00732 {
00733         struct isl_mat *c = NULL;
00734         isl_int *lower = NULL;
00735         isl_int *upper = NULL;
00736         int i, j, k;
00737         isl_int a, b;
00738         struct isl_basic_set *hull;
00739 
00740         for (i = 0; i < set->n; ++i) {
00741                 set->p[i] = isl_basic_set_simplify(set->p[i]);
00742                 if (!set->p[i])
00743                         goto error;
00744         }
00745         set = isl_set_remove_empty_parts(set);
00746         if (!set)
00747                 goto error;
00748         isl_assert(ctx, set->n > 0, goto error);
00749         c = isl_mat_alloc(ctx, 2, 2);
00750         if (!c)
00751                 goto error;
00752 
00753         if (set->p[0]->n_eq > 0) {
00754                 isl_assert(ctx, set->p[0]->n_eq == 1, goto error);
00755                 lower = c->row[0];
00756                 upper = c->row[1];
00757                 if (isl_int_is_pos(set->p[0]->eq[0][1])) {
00758                         isl_seq_cpy(lower, set->p[0]->eq[0], 2);
00759                         isl_seq_neg(upper, set->p[0]->eq[0], 2);
00760                 } else {
00761                         isl_seq_neg(lower, set->p[0]->eq[0], 2);
00762                         isl_seq_cpy(upper, set->p[0]->eq[0], 2);
00763                 }
00764         } else {
00765                 for (j = 0; j < set->p[0]->n_ineq; ++j) {
00766                         if (isl_int_is_pos(set->p[0]->ineq[j][1])) {
00767                                 lower = c->row[0];
00768                                 isl_seq_cpy(lower, set->p[0]->ineq[j], 2);
00769                         } else {
00770                                 upper = c->row[1];
00771                                 isl_seq_cpy(upper, set->p[0]->ineq[j], 2);
00772                         }
00773                 }
00774         }
00775 
00776         isl_int_init(a);
00777         isl_int_init(b);
00778         for (i = 0; i < set->n; ++i) {
00779                 struct isl_basic_set *bset = set->p[i];
00780                 int has_lower = 0;
00781                 int has_upper = 0;
00782 
00783                 for (j = 0; j < bset->n_eq; ++j) {
00784                         has_lower = 1;
00785                         has_upper = 1;
00786                         if (lower) {
00787                                 isl_int_mul(a, lower[0], bset->eq[j][1]);
00788                                 isl_int_mul(b, lower[1], bset->eq[j][0]);
00789                                 if (isl_int_lt(a, b) && isl_int_is_pos(bset->eq[j][1]))
00790                                         isl_seq_cpy(lower, bset->eq[j], 2);
00791                                 if (isl_int_gt(a, b) && isl_int_is_neg(bset->eq[j][1]))
00792                                         isl_seq_neg(lower, bset->eq[j], 2);
00793                         }
00794                         if (upper) {
00795                                 isl_int_mul(a, upper[0], bset->eq[j][1]);
00796                                 isl_int_mul(b, upper[1], bset->eq[j][0]);
00797                                 if (isl_int_lt(a, b) && isl_int_is_pos(bset->eq[j][1]))
00798                                         isl_seq_neg(upper, bset->eq[j], 2);
00799                                 if (isl_int_gt(a, b) && isl_int_is_neg(bset->eq[j][1]))
00800                                         isl_seq_cpy(upper, bset->eq[j], 2);
00801                         }
00802                 }
00803                 for (j = 0; j < bset->n_ineq; ++j) {
00804                         if (isl_int_is_pos(bset->ineq[j][1]))
00805                                 has_lower = 1;
00806                         if (isl_int_is_neg(bset->ineq[j][1]))
00807                                 has_upper = 1;
00808                         if (lower && isl_int_is_pos(bset->ineq[j][1])) {
00809                                 isl_int_mul(a, lower[0], bset->ineq[j][1]);
00810                                 isl_int_mul(b, lower[1], bset->ineq[j][0]);
00811                                 if (isl_int_lt(a, b))
00812                                         isl_seq_cpy(lower, bset->ineq[j], 2);
00813                         }
00814                         if (upper && isl_int_is_neg(bset->ineq[j][1])) {
00815                                 isl_int_mul(a, upper[0], bset->ineq[j][1]);
00816                                 isl_int_mul(b, upper[1], bset->ineq[j][0]);
00817                                 if (isl_int_gt(a, b))
00818                                         isl_seq_cpy(upper, bset->ineq[j], 2);
00819                         }
00820                 }
00821                 if (!has_lower)
00822                         lower = NULL;
00823                 if (!has_upper)
00824                         upper = NULL;
00825         }
00826         isl_int_clear(a);
00827         isl_int_clear(b);
00828 
00829         hull = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
00830         hull = isl_basic_set_set_rational(hull);
00831         if (!hull)
00832                 goto error;
00833         if (lower) {
00834                 k = isl_basic_set_alloc_inequality(hull);
00835                 isl_seq_cpy(hull->ineq[k], lower, 2);
00836         }
00837         if (upper) {
00838                 k = isl_basic_set_alloc_inequality(hull);
00839                 isl_seq_cpy(hull->ineq[k], upper, 2);
00840         }
00841         hull = isl_basic_set_finalize(hull);
00842         isl_set_free(set);
00843         isl_mat_free(ctx, c);
00844         return hull;
00845 error:
00846         isl_set_free(set);
00847         isl_mat_free(ctx, c);
00848         return NULL;
00849 }

Here is the call graph for this function:

static struct isl_basic_set* convex_hull_pair ( struct isl_basic_set *  bset1,
struct isl_basic_set *  bset2 
) [static, read]

Definition at line 1371 of file isl_convex_hull.c.

01373 {
01374         struct isl_basic_set *lin;
01375 
01376         if (isl_basic_set_is_bounded(bset1) || isl_basic_set_is_bounded(bset2))
01377                 return convex_hull_pair_pointed(bset1, bset2);
01378 
01379         lin = induced_lineality_space(isl_basic_set_copy(bset1),
01380                                       isl_basic_set_copy(bset2));
01381         if (!lin)
01382                 goto error;
01383         if (isl_basic_set_is_universe(lin)) {
01384                 isl_basic_set_free(bset1);
01385                 isl_basic_set_free(bset2);
01386                 return lin;
01387         }
01388         if (lin->n_eq < isl_basic_set_total_dim(lin)) {
01389                 struct isl_set *set;
01390                 set = isl_set_alloc_dim(isl_basic_set_get_dim(bset1), 2, 0);
01391                 set = isl_set_add(set, bset1);
01392                 set = isl_set_add(set, bset2);
01393                 return modulo_lineality(set, lin);
01394         }
01395         isl_basic_set_free(lin);
01396 
01397         return convex_hull_pair_pointed(bset1, bset2);
01398 error:
01399         isl_basic_set_free(bset1);
01400         isl_basic_set_free(bset2);
01401         return NULL;
01402 }

Here is the call graph for this function:

static struct isl_basic_set* convex_hull_pair_elim ( struct isl_basic_set *  bset1,
struct isl_basic_set *  bset2 
) [static, read]

Definition at line 882 of file isl_convex_hull.c.

00884 {
00885         int i, j, k;
00886         struct isl_basic_set *bset[2];
00887         struct isl_basic_set *hull = NULL;
00888         unsigned dim;
00889 
00890         if (!bset1 || !bset2)
00891                 goto error;
00892 
00893         dim = isl_basic_set_n_dim(bset1);
00894         hull = isl_basic_set_alloc(bset1->ctx, 0, 2 + 3 * dim, 0,
00895                                 1 + dim + bset1->n_eq + bset2->n_eq,
00896                                 2 + bset1->n_ineq + bset2->n_ineq);
00897         bset[0] = bset1;
00898         bset[1] = bset2;
00899         for (i = 0; i < 2; ++i) {
00900                 for (j = 0; j < bset[i]->n_eq; ++j) {
00901                         k = isl_basic_set_alloc_equality(hull);
00902                         if (k < 0)
00903                                 goto error;
00904                         isl_seq_clr(hull->eq[k], (i+1) * (1+dim));
00905                         isl_seq_clr(hull->eq[k]+(i+2)*(1+dim), (1-i)*(1+dim));
00906                         isl_seq_cpy(hull->eq[k]+(i+1)*(1+dim), bset[i]->eq[j],
00907                                         1+dim);
00908                 }
00909                 for (j = 0; j < bset[i]->n_ineq; ++j) {
00910                         k = isl_basic_set_alloc_inequality(hull);
00911                         if (k < 0)
00912                                 goto error;
00913                         isl_seq_clr(hull->ineq[k], (i+1) * (1+dim));
00914                         isl_seq_clr(hull->ineq[k]+(i+2)*(1+dim), (1-i)*(1+dim));
00915                         isl_seq_cpy(hull->ineq[k]+(i+1)*(1+dim),
00916                                         bset[i]->ineq[j], 1+dim);
00917                 }
00918                 k = isl_basic_set_alloc_inequality(hull);
00919                 if (k < 0)
00920                         goto error;
00921                 isl_seq_clr(hull->ineq[k], 1+2+3*dim);
00922                 isl_int_set_si(hull->ineq[k][(i+1)*(1+dim)], 1);
00923         }
00924         for (j = 0; j < 1+dim; ++j) {
00925                 k = isl_basic_set_alloc_equality(hull);
00926                 if (k < 0)
00927                         goto error;
00928                 isl_seq_clr(hull->eq[k], 1+2+3*dim);
00929                 isl_int_set_si(hull->eq[k][j], -1);
00930                 isl_int_set_si(hull->eq[k][1+dim+j], 1);
00931                 isl_int_set_si(hull->eq[k][2*(1+dim)+j], 1);
00932         }
00933         hull = isl_basic_set_set_rational(hull);
00934         hull = isl_basic_set_remove_dims(hull, dim, 2*(1+dim));
00935         hull = isl_basic_set_convex_hull(hull);
00936         isl_basic_set_free(bset1);
00937         isl_basic_set_free(bset2);
00938         return hull;
00939 error:
00940         isl_basic_set_free(bset1);
00941         isl_basic_set_free(bset2);
00942         isl_basic_set_free(hull);
00943         return NULL;
00944 }

Here is the call graph for this function:

static struct isl_basic_set* convex_hull_pair_pointed ( struct isl_basic_set *  bset1,
struct isl_basic_set *  bset2 
) [static, read]

Definition at line 1323 of file isl_convex_hull.c.

01325 {
01326         struct isl_ctx *ctx = NULL;
01327         struct isl_vec *dir = NULL;
01328         struct isl_mat *T = NULL;
01329         struct isl_mat *T2 = NULL;
01330         struct isl_basic_set *hull;
01331         struct isl_set *set;
01332 
01333         if (!bset1 || !bset2)
01334                 goto error;
01335         ctx = bset1->ctx;
01336         dir = valid_direction(isl_basic_set_copy(bset1),
01337                                 isl_basic_set_copy(bset2));
01338         if (!dir)
01339                 goto error;
01340         T = isl_mat_alloc(bset1->ctx, dir->size, dir->size);
01341         if (!T)
01342                 goto error;
01343         isl_seq_cpy(T->row[0], dir->block.data, dir->size);
01344         T = isl_mat_unimodular_complete(ctx, T, 1);
01345         T2 = isl_mat_right_inverse(ctx, isl_mat_copy(ctx, T));
01346 
01347         bset1 = homogeneous_map(bset1, isl_mat_copy(ctx, T2));
01348         bset2 = homogeneous_map(bset2, T2);
01349         set = isl_set_alloc_dim(isl_basic_set_get_dim(bset1), 2, 0);
01350         set = isl_set_add(set, bset1);
01351         set = isl_set_add(set, bset2);
01352         hull = uset_convex_hull(set);
01353         hull = isl_basic_set_preimage(hull, T);
01354          
01355         isl_vec_free(ctx, dir);
01356 
01357         return hull;
01358 error:
01359         isl_vec_free(ctx, dir);
01360         isl_basic_set_free(bset1);
01361         isl_basic_set_free(bset2);
01362         return NULL;
01363 }

Here is the call graph for this function:

static struct isl_basic_set* extend ( struct isl_basic_set *  hull,
struct isl_set *  set 
) [static, read]

Definition at line 671 of file isl_convex_hull.c.

00673 {
00674         int i, j, f;
00675         int k;
00676         struct isl_basic_set *facet = NULL;
00677         struct isl_basic_set *hull_facet = NULL;
00678         unsigned total;
00679         unsigned dim;
00680 
00681         isl_assert(set->ctx, set->n > 0, goto error);
00682 
00683         dim = isl_set_n_dim(set);
00684 
00685         for (i = 0; i < hull->n_ineq; ++i) {
00686                 facet = compute_facet(set, hull->ineq[i]);
00687                 facet = isl_basic_set_add_equality(facet->ctx, facet, hull->ineq[i]);
00688                 facet = isl_basic_set_gauss(facet, NULL);
00689                 facet = isl_basic_set_normalize_constraints(facet);
00690                 hull_facet = isl_basic_set_copy(hull);
00691                 hull_facet = isl_basic_set_add_equality(hull_facet->ctx, hull_facet, hull->ineq[i]);
00692                 hull_facet = isl_basic_set_gauss(hull_facet, NULL);
00693                 hull_facet = isl_basic_set_normalize_constraints(hull_facet);
00694                 if (!facet)
00695                         goto error;
00696                 hull = isl_basic_set_cow(hull);
00697                 hull = isl_basic_set_extend_dim(hull,
00698                         isl_dim_copy(hull->dim), 0, 0, facet->n_ineq);
00699                 for (j = 0; j < facet->n_ineq; ++j) {
00700                         for (f = 0; f < hull_facet->n_ineq; ++f)
00701                                 if (isl_seq_eq(facet->ineq[j],
00702                                                 hull_facet->ineq[f], 1 + dim))
00703                                         break;
00704                         if (f < hull_facet->n_ineq)
00705                                 continue;
00706                         k = isl_basic_set_alloc_inequality(hull);
00707                         if (k < 0)
00708                                 goto error;
00709                         isl_seq_cpy(hull->ineq[k], hull->ineq[i], 1+dim);
00710                         if (!wrap_facet(set, hull->ineq[k], facet->ineq[j]))
00711                                 goto error;
00712                 }
00713                 isl_basic_set_free(hull_facet);
00714                 isl_basic_set_free(facet);
00715         }
00716         hull = isl_basic_set_simplify(hull);
00717         hull = isl_basic_set_finalize(hull);
00718         return hull;
00719 error:
00720         isl_basic_set_free(hull_facet);
00721         isl_basic_set_free(facet);
00722         isl_basic_set_free(hull);
00723         return NULL;
00724 }

Here is the call graph for this function:

static int has_constraint ( struct isl_ctx *  ctx,
struct isl_hash_table *  table,
isl_int *  con,
unsigned  len,
int  n 
) [static]

Definition at line 1610 of file isl_convex_hull.c.

01612 {
01613         struct isl_hash_table_entry *entry;
01614         struct max_constraint *c;
01615         uint32_t c_hash;
01616 
01617         c_hash = isl_seq_hash(con + 1, len, isl_hash_init());
01618         entry = isl_hash_table_find(ctx, table, c_hash, max_constraint_equal,
01619                         con + 1, 0);
01620         if (!entry)
01621                 return 0;
01622         c = entry->data;
01623         if (c->count < n)
01624                 return 0;
01625         return isl_int_eq(c->c->row[0][0], con[0]);
01626 }

Here is the call graph for this function:

static int has_ineq ( const void *  entry,
const void *  val 
) [static]

Definition at line 2010 of file isl_convex_hull.c.

02011 {
02012         isl_int *row = (isl_int *)entry;
02013         struct ineq_cmp_data *v = (struct ineq_cmp_data *)val;
02014 
02015         return isl_seq_eq(row + 1, v->p + 1, v->len) ||
02016                isl_seq_is_neg(row + 1, v->p + 1, v->len);
02017 }

Here is the call graph for this function:

static int hash_basic_set ( struct isl_hash_table *  table,
struct isl_basic_set *  bset 
) [static]

Definition at line 2040 of file isl_convex_hull.c.

02042 {
02043         int i, j;
02044         unsigned dim = isl_basic_set_total_dim(bset);
02045 
02046         for (i = 0; i < bset->n_eq; ++i) {
02047                 for (j = 0; j < 2; ++j) {
02048                         isl_seq_neg(bset->eq[i], bset->eq[i], 1 + dim);
02049                         if (hash_ineq(bset->ctx, table, bset->eq[i], dim) < 0)
02050                                 return -1;
02051                 }
02052         }
02053         for (i = 0; i < bset->n_ineq; ++i) {
02054                 if (hash_ineq(bset->ctx, table, bset->ineq[i], dim) < 0)
02055                         return -1;
02056         }
02057         return 0;
02058 }

Here is the call graph for this function:

static int hash_ineq ( struct isl_ctx *  ctx,
struct isl_hash_table *  table,
isl_int *  ineq,
unsigned  len 
) [static]

Definition at line 2019 of file isl_convex_hull.c.

02021 {
02022         uint32_t c_hash;
02023         struct ineq_cmp_data v;
02024         struct isl_hash_table_entry *entry;
02025 
02026         v.len = len;
02027         v.p = ineq;
02028         c_hash = isl_seq_hash(ineq + 1, len, isl_hash_init());
02029         entry = isl_hash_table_find(ctx, table, c_hash, has_ineq, &v, 1);
02030         if (!entry)
02031                 return - 1;
02032         entry->data = ineq;
02033         return 0;
02034 }

Here is the call graph for this function:

static struct isl_basic_set* homogeneous_map ( struct isl_basic_set *  bset,
struct isl_mat *  T 
) [static, read]

Definition at line 1241 of file isl_convex_hull.c.

01243 {
01244         struct isl_ctx *ctx = NULL;
01245         int k;
01246 
01247         if (!bset)
01248                 goto error;
01249         ctx = bset->ctx;
01250         bset = isl_basic_set_extend_constraints(bset, 0, 1);
01251         k = isl_basic_set_alloc_inequality(bset);
01252         if (k < 0)
01253                 goto error;
01254         isl_seq_clr(bset->ineq[k] + 1, isl_basic_set_total_dim(bset));
01255         isl_int_set_si(bset->ineq[k][0], 1);
01256         bset = isl_basic_set_preimage(bset, T);
01257         return bset;
01258 error:
01259         isl_mat_free(ctx, T);
01260         isl_basic_set_free(bset);
01261         return NULL;
01262 }

Here is the call graph for this function:

static struct isl_mat* independent_bounds ( struct isl_ctx *  ctx,
struct isl_set *  set 
) [static, read]

Definition at line 210 of file isl_convex_hull.c.

00212 {
00213         int i, j, n;
00214         struct isl_mat *dirs = NULL;
00215         unsigned dim = isl_set_n_dim(set);
00216 
00217         dirs = isl_mat_alloc(ctx, dim, 1+dim);
00218         if (!dirs)
00219                 goto error;
00220 
00221         n = 0;
00222         for (i = 0; n < dim && i < set->n; ++i) {
00223                 int f;
00224                 struct isl_basic_set *bset = set->p[i];
00225 
00226                 for (j = 0; n < dim && j < bset->n_eq; ++j) {
00227                         f = is_independent_bound(ctx, set, bset->eq[j],
00228                                                 dirs, n);
00229                         if (f < 0)
00230                                 goto error;
00231                         if (f)
00232                                 ++n;
00233                 }
00234                 for (j = 0; n < dim && j < bset->n_ineq; ++j) {
00235                         f = is_independent_bound(ctx, set, bset->ineq[j],
00236                                                 dirs, n);
00237                         if (f < 0)
00238                                 goto error;
00239                         if (f)
00240                                 ++n;
00241                 }
00242         }
00243         dirs->n_row = n;
00244         return dirs;
00245 error:
00246         isl_mat_free(ctx, dirs);
00247         return NULL;
00248 }

Here is the call graph for this function:

static struct isl_basic_set* induced_lineality_space ( struct isl_basic_set *  bset1,
struct isl_basic_set *  bset2 
) [static, read]

Definition at line 975 of file isl_convex_hull.c.

00977 {
00978         int i, k;
00979         struct isl_basic_set *lin = NULL;
00980         unsigned dim;
00981 
00982         if (!bset1 || !bset2)
00983                 goto error;
00984 
00985         dim = isl_basic_set_total_dim(bset1);
00986         lin = isl_basic_set_alloc_dim(isl_basic_set_get_dim(bset1), 0,
00987                                         bset1->n_eq + bset2->n_eq,
00988                                         bset1->n_ineq + bset2->n_ineq);
00989         lin = isl_basic_set_set_rational(lin);
00990         if (!lin)
00991                 goto error;
00992         for (i = 0; i < bset1->n_eq; ++i) {
00993                 k = isl_basic_set_alloc_equality(lin);
00994                 if (k < 0)
00995                         goto error;
00996                 isl_int_set_si(lin->eq[k][0], 0);
00997                 isl_seq_cpy(lin->eq[k] + 1, bset1->eq[i] + 1, dim);
00998         }
00999         for (i = 0; i < bset1->n_ineq; ++i) {
01000                 k = isl_basic_set_alloc_inequality(lin);
01001                 if (k < 0)
01002                         goto error;
01003                 isl_int_set_si(lin->ineq[k][0], 0);
01004                 isl_seq_cpy(lin->ineq[k] + 1, bset1->ineq[i] + 1, dim);
01005         }
01006         for (i = 0; i < bset2->n_eq; ++i) {
01007                 k = isl_basic_set_alloc_equality(lin);
01008                 if (k < 0)
01009                         goto error;
01010                 isl_int_set_si(lin->eq[k][0], 0);
01011                 isl_seq_neg(lin->eq[k] + 1, bset2->eq[i] + 1, dim);
01012         }
01013         for (i = 0; i < bset2->n_ineq; ++i) {
01014                 k = isl_basic_set_alloc_inequality(lin);
01015                 if (k < 0)
01016                         goto error;
01017                 isl_int_set_si(lin->ineq[k][0], 0);
01018                 isl_seq_neg(lin->ineq[k] + 1, bset2->ineq[i] + 1, dim);
01019         }
01020 
01021         isl_basic_set_free(bset1);
01022         isl_basic_set_free(bset2);
01023         return isl_basic_set_affine_hull(lin);
01024 error:
01025         isl_basic_set_free(lin);
01026         isl_basic_set_free(bset1);
01027         isl_basic_set_free(bset2);
01028         return NULL;
01029 }

Here is the call graph for this function:

static struct isl_mat* initial_facet_constraint ( struct isl_ctx *  ctx,
struct isl_set *  set,
struct isl_mat *  bounds 
) [static, read]

Definition at line 523 of file isl_convex_hull.c.

00525 {
00526         struct isl_set *slice = NULL;
00527         struct isl_basic_set *face = NULL;
00528         struct isl_mat *m, *U, *Q;
00529         int i;
00530         unsigned dim = isl_set_n_dim(set);
00531 
00532         isl_assert(ctx, set->n > 0, goto error);
00533         isl_assert(ctx, bounds->n_row == dim, goto error);
00534 
00535         while (bounds->n_row > 1) {
00536                 slice = isl_set_copy(set);
00537                 slice = isl_set_add_equality(ctx, slice, bounds->row[0]);
00538                 face = isl_set_affine_hull(slice);
00539                 if (!face)
00540                         goto error;
00541                 if (face->n_eq == 1) {
00542                         isl_basic_set_free(face);
00543                         break;
00544                 }
00545                 m = isl_mat_alloc(ctx, 1 + face->n_eq, 1 + dim);
00546                 if (!m)
00547                         goto error;
00548                 isl_int_set_si(m->row[0][0], 1);
00549                 isl_seq_clr(m->row[0]+1, dim);
00550                 for (i = 0; i < face->n_eq; ++i)
00551                         isl_seq_cpy(m->row[1 + i], face->eq[i], 1 + dim);
00552                 U = isl_mat_right_inverse(ctx, m);
00553                 Q = isl_mat_right_inverse(ctx, isl_mat_copy(ctx, U));
00554                 U = isl_mat_drop_cols(ctx, U, 1 + face->n_eq,
00555                                                 dim - face->n_eq);
00556                 Q = isl_mat_drop_rows(ctx, Q, 1 + face->n_eq,
00557                                                 dim - face->n_eq);
00558                 U = isl_mat_drop_cols(ctx, U, 0, 1);
00559                 Q = isl_mat_drop_rows(ctx, Q, 0, 1);
00560                 bounds = isl_mat_product(ctx, bounds, U);
00561                 bounds = isl_mat_product(ctx, bounds, Q);
00562                 while (isl_seq_first_non_zero(bounds->row[bounds->n_row-1],
00563                                               bounds->n_col) == -1) {
00564                         bounds->n_row--;
00565                         isl_assert(ctx, bounds->n_row > 1, goto error);
00566                 }
00567                 if (!wrap_facet(set, bounds->row[0],
00568                                           bounds->row[bounds->n_row-1]))
00569                         goto error;
00570                 isl_basic_set_free(face);
00571                 bounds->n_row--;
00572         }
00573         return bounds;
00574 error:
00575         isl_basic_set_free(face);
00576         isl_mat_free(ctx, bounds);
00577         return NULL;
00578 }

Here is the call graph for this function:

static struct isl_basic_set* initial_hull ( struct isl_basic_set *  hull,
struct isl_set *  set 
) [static, read]

Definition at line 1532 of file isl_convex_hull.c.

01534 {
01535         struct isl_mat *bounds = NULL;
01536         unsigned dim;
01537         int k;
01538 
01539         if (!hull)
01540                 goto error;
01541         bounds = independent_bounds(set->ctx, set);
01542         if (!bounds)
01543                 goto error;
01544         isl_assert(set->ctx, bounds->n_row == isl_set_n_dim(set), goto error);
01545         bounds = initial_facet_constraint(set->ctx, set, bounds);
01546         if (!bounds)
01547                 goto error;
01548         k = isl_basic_set_alloc_inequality(hull);
01549         if (k < 0)
01550                 goto error;
01551         dim = isl_set_n_dim(set);
01552         isl_assert(set->ctx, 1 + dim == bounds->n_col, goto error);
01553         isl_seq_cpy(hull->ineq[k], bounds->row[0], bounds->n_col);
01554         isl_mat_free(set->ctx, bounds);
01555 
01556         return hull;
01557 error:
01558         isl_basic_set_free(hull);
01559         isl_mat_free(set->ctx, bounds);
01560         return NULL;
01561 }

Here is the call graph for this function:

static int is_bound ( struct sh_data *  data,
struct isl_set *  set,
int  j,
isl_int *  ineq 
) [static]

Definition at line 2096 of file isl_convex_hull.c.

02098 {
02099         enum isl_lp_result res;
02100         isl_int opt;
02101 
02102         if (!data->p[j].tab) {
02103                 data->p[j].tab = isl_tab_from_basic_set(set->p[j]);
02104                 if (!data->p[j].tab)
02105                         return -1;
02106         }
02107 
02108         isl_int_init(opt);
02109 
02110         res = isl_tab_min(data->ctx, data->p[j].tab, ineq, data->ctx->one,
02111                                 &opt, NULL);
02112         if (res == isl_lp_ok && isl_int_is_neg(opt))
02113                 isl_int_sub(ineq[0], ineq[0], opt);
02114 
02115         isl_int_clear(opt);
02116 
02117         return res == isl_lp_ok ? 1 :
02118                res == isl_lp_unbounded ? 0 : -1;
02119 }

Here is the call graph for this function:

static int is_independent_bound ( struct isl_ctx *  ctx,
struct isl_set *  set,
isl_int *  c,
struct isl_mat *  dirs,
int  n 
) [static]

Definition at line 166 of file isl_convex_hull.c.

00169 {
00170         int is_bound;
00171         int i = 0;
00172 
00173         isl_seq_cpy(dirs->row[n]+1, c+1, dirs->n_col-1);
00174         if (n != 0) {
00175                 int pos = isl_seq_first_non_zero(dirs->row[n]+1, dirs->n_col-1);
00176                 if (pos < 0)
00177                         return 0;
00178                 for (i = 0; i < n; ++i) {
00179                         int pos_i;
00180                         pos_i = isl_seq_first_non_zero(dirs->row[i]+1, dirs->n_col-1);
00181                         if (pos_i < pos)
00182                                 continue;
00183                         if (pos_i > pos)
00184                                 break;
00185                         isl_seq_elim(dirs->row[n]+1, dirs->row[i]+1, pos,
00186                                         dirs->n_col-1, NULL);
00187                         pos = isl_seq_first_non_zero(dirs->row[n]+1, dirs->n_col-1);
00188                         if (pos < 0)
00189                                 return 0;
00190                 }
00191         }
00192 
00193         is_bound = uset_is_bound(ctx, set, dirs->row[n], dirs->n_col);
00194         if (is_bound != 1)
00195                 return is_bound;
00196         if (i < n) {
00197                 int k;
00198                 isl_int *t = dirs->row[n];
00199                 for (k = n; k > i; --k)
00200                         dirs->row[k] = dirs->row[k-1];
00201                 dirs->row[i] = t;
00202         }
00203         return 1;
00204 }

Here is the call graph for this function:

int isl_basic_map_constraint_is_redundant ( struct isl_basic_map **  bmap,
isl_int *  c,
isl_int *  opt_n,
isl_int *  opt_d 
)

Definition at line 28 of file isl_convex_hull.c.

00030 {
00031         enum isl_lp_result res;
00032         unsigned total;
00033         int i, j;
00034 
00035         if (!bmap)
00036                 return -1;
00037 
00038         total = isl_basic_map_total_dim(*bmap);
00039         for (i = 0; i < total; ++i) {
00040                 int sign;
00041                 if (isl_int_is_zero(c[1+i]))
00042                         continue;
00043                 sign = isl_int_sgn(c[1+i]);
00044                 for (j = 0; j < (*bmap)->n_ineq; ++j)
00045                         if (sign == isl_int_sgn((*bmap)->ineq[j][1+i]))
00046                                 break;
00047                 if (j == (*bmap)->n_ineq)
00048                         break;
00049         }
00050         if (i < total)
00051                 return 0;
00052 
00053         res = isl_solve_lp(*bmap, 0, c, (*bmap)->ctx->one, opt_n, opt_d);
00054         if (res == isl_lp_unbounded)
00055                 return 0;
00056         if (res == isl_lp_error)
00057                 return -1;
00058         if (res == isl_lp_empty) {
00059                 *bmap = isl_basic_map_set_to_empty(*bmap);
00060                 return 0;
00061         }
00062         return !isl_int_is_neg(*opt_n);
00063 }

Here is the call graph for this function:

struct isl_basic_map* isl_basic_map_convex_hull ( struct isl_basic_map *  bmap  )  [read]

Definition at line 80 of file isl_convex_hull.c.

00081 {
00082         struct isl_tab *tab;
00083 
00084         if (!bmap)
00085                 return NULL;
00086 
00087         bmap = isl_basic_map_gauss(bmap, NULL);
00088         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
00089                 return bmap;
00090         if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NO_REDUNDANT))
00091                 return bmap;
00092         if (bmap->n_ineq <= 1)
00093                 return bmap;
00094 
00095         tab = isl_tab_from_basic_map(bmap);
00096         tab = isl_tab_detect_equalities(bmap->ctx, tab);
00097         tab = isl_tab_detect_redundant(bmap->ctx, tab);
00098         bmap = isl_basic_map_update_from_tab(bmap, tab);
00099         isl_tab_free(bmap->ctx, tab);
00100         ISL_F_SET(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
00101         ISL_F_SET(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
00102         return bmap;
00103 }

Here is the call graph for this function:

static struct isl_basic_set* isl_basic_set_add_equality ( struct isl_ctx *  ctx,
struct isl_basic_set *  bset,
isl_int *  c 
) [static, read]

Definition at line 286 of file isl_convex_hull.c.

00288 {
00289         int i;
00290         unsigned total;
00291         unsigned dim;
00292 
00293         if (ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY))
00294                 return bset;
00295 
00296         isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error);
00297         isl_assert(ctx, bset->n_div == 0, goto error);
00298         dim = isl_basic_set_n_dim(bset);
00299         bset = isl_basic_set_cow(bset);
00300         bset = isl_basic_set_extend(bset, 0, dim, 0, 1, 0);
00301         i = isl_basic_set_alloc_equality(bset);
00302         if (i < 0)
00303                 goto error;
00304         isl_seq_cpy(bset->eq[i], c, 1 + dim);
00305         return bset;
00306 error:
00307         isl_basic_set_free(bset);
00308         return NULL;
00309 }

Here is the call graph for this function:

int isl_basic_set_constraint_is_redundant ( struct isl_basic_set **  bset,
isl_int *  c,
isl_int *  opt_n,
isl_int *  opt_d 
)

Definition at line 65 of file isl_convex_hull.c.

00067 {
00068         return isl_basic_map_constraint_is_redundant(
00069                         (struct isl_basic_map **)bset, c, opt_n, opt_d);
00070 }

Here is the call graph for this function:

struct isl_basic_set* isl_basic_set_convex_hull ( struct isl_basic_set *  bset  )  [read]

Definition at line 105 of file isl_convex_hull.c.

00106 {
00107         return (struct isl_basic_set *)
00108                 isl_basic_map_convex_hull((struct isl_basic_map *)bset);
00109 }

Here is the call graph for this function:

static int isl_basic_set_is_bounded ( struct isl_basic_set *  bset  )  [static]

Definition at line 946 of file isl_convex_hull.c.

00947 {
00948         struct isl_tab *tab;
00949         int bounded;
00950 
00951         tab = isl_tab_from_recession_cone((struct isl_basic_map *)bset);
00952         bounded = isl_tab_cone_is_bounded(bset->ctx, tab);
00953         isl_tab_free(bset->ctx, tab);
00954         return bounded;
00955 }

Here is the call graph for this function:

static struct isl_basic_set* isl_basic_set_set_rational ( struct isl_basic_set *  bset  )  [static, read]

Definition at line 250 of file isl_convex_hull.c.

00252 {
00253         if (!bset)
00254                 return NULL;
00255 
00256         if (ISL_F_ISSET(bset, ISL_BASIC_MAP_RATIONAL))
00257                 return bset;
00258 
00259         bset = isl_basic_set_cow(bset);
00260         if (!bset)
00261                 return NULL;
00262 
00263         ISL_F_SET(bset, ISL_BASIC_MAP_RATIONAL);
00264 
00265         return isl_basic_set_finalize(bset);
00266 }

Here is the call graph for this function:

struct isl_basic_map* isl_map_convex_hull ( struct isl_map *  map  )  [read]

Definition at line 1916 of file isl_convex_hull.c.

01917 {
01918         struct isl_basic_set *bset;
01919         struct isl_basic_map *model = NULL;
01920         struct isl_basic_set *affine_hull = NULL;
01921         struct isl_basic_map *convex_hull = NULL;
01922         struct isl_set *set = NULL;
01923         struct isl_ctx *ctx;
01924 
01925         if (!map)
01926                 goto error;
01927 
01928         ctx = map->ctx;
01929         if (map->n == 0) {
01930                 convex_hull = isl_basic_map_empty_like_map(map);
01931                 isl_map_free(map);
01932                 return convex_hull;
01933         }
01934 
01935         map = isl_map_detect_equalities(map);
01936         map = isl_map_align_divs(map);
01937         model = isl_basic_map_copy(map->p[0]);
01938         set = isl_map_underlying_set(map);
01939         if (!set)
01940                 goto error;
01941 
01942         affine_hull = isl_set_affine_hull(isl_set_copy(set));
01943         if (!affine_hull)
01944                 goto error;
01945         if (affine_hull->n_eq != 0)
01946                 bset = modulo_affine_hull(ctx, set, affine_hull);
01947         else {
01948                 isl_basic_set_free(affine_hull);
01949                 bset = uset_convex_hull(set);
01950         }
01951 
01952         convex_hull = isl_basic_map_overlying_set(bset, model);
01953 
01954         ISL_F_SET(convex_hull, ISL_BASIC_MAP_NO_IMPLICIT);
01955         ISL_F_SET(convex_hull, ISL_BASIC_MAP_ALL_EQUALITIES);
01956         ISL_F_CLR(convex_hull, ISL_BASIC_MAP_RATIONAL);
01957         return convex_hull;
01958 error:
01959         isl_set_free(set);
01960         isl_basic_map_free(model);
01961         return NULL;
01962 }

Here is the call graph for this function:

struct isl_basic_map* isl_map_simple_hull ( struct isl_map *  map  )  [read]

Definition at line 2291 of file isl_convex_hull.c.

02292 {
02293         struct isl_set *set = NULL;
02294         struct isl_basic_map *model = NULL;
02295         struct isl_basic_map *hull;
02296         struct isl_basic_map *affine_hull;
02297         struct isl_basic_set *bset = NULL;
02298 
02299         if (!map)
02300                 return NULL;
02301         if (map->n == 0) {
02302                 hull = isl_basic_map_empty_like_map(map);
02303                 isl_map_free(map);
02304                 return hull;
02305         }
02306         if (map->n == 1) {
02307                 hull = isl_basic_map_copy(map->p[0]);
02308                 isl_map_free(map);
02309                 return hull;
02310         }
02311 
02312         map = isl_map_detect_equalities(map);
02313         affine_hull = isl_map_affine_hull(isl_map_copy(map));
02314         map = isl_map_align_divs(map);
02315         model = isl_basic_map_copy(map->p[0]);
02316 
02317         set = isl_map_underlying_set(map);
02318 
02319         bset = uset_simple_hull(set);
02320 
02321         hull = isl_basic_map_overlying_set(bset, model);
02322 
02323         hull = isl_basic_map_intersect(hull, affine_hull);
02324         hull = isl_basic_map_convex_hull(hull);
02325         ISL_F_SET(hull, ISL_BASIC_MAP_NO_IMPLICIT);
02326         ISL_F_SET(hull, ISL_BASIC_MAP_ALL_EQUALITIES);
02327 
02328         return hull;
02329 }

Here is the call graph for this function:

static struct isl_set* isl_set_add_equality ( struct isl_ctx *  ctx,
struct isl_set *  set,
isl_int *  c 
) [static, read]

Definition at line 311 of file isl_convex_hull.c.

00313 {
00314         int i;
00315 
00316         set = isl_set_cow(set);
00317         if (!set)
00318                 return NULL;
00319         for (i = 0; i < set->n; ++i) {
00320                 set->p[i] = isl_basic_set_add_equality(ctx, set->p[i], c);
00321                 if (!set->p[i])
00322                         goto error;
00323         }
00324         return set;
00325 error:
00326         isl_set_free(set);
00327         return NULL;
00328 }

Here is the call graph for this function:

struct isl_basic_set* isl_set_bounded_simple_hull ( struct isl_set *  set  )  [read]

Definition at line 2352 of file isl_convex_hull.c.

02353 {
02354         int i, j;
02355         struct isl_basic_set *hull;
02356         unsigned nparam, left;
02357         int removed_divs = 0;
02358 
02359         hull = isl_set_simple_hull(isl_set_copy(set));
02360         if (!hull)
02361                 goto error;
02362 
02363         nparam = isl_basic_set_dim(hull, isl_dim_param);
02364         for (i = 0; i < isl_basic_set_dim(hull, isl_dim_set); ++i) {
02365                 int lower = 0, upper = 0;
02366                 struct isl_basic_set *bounds;
02367 
02368                 left = isl_basic_set_total_dim(hull) - nparam - i - 1;
02369                 for (j = 0; j < hull->n_eq; ++j) {
02370                         if (isl_int_is_zero(hull->eq[j][1 + nparam + i]))
02371                                 continue;
02372                         if (isl_seq_first_non_zero(hull->eq[j]+1+nparam+i+1,
02373                                                     left) == -1)
02374                                 break;
02375                 }
02376                 if (j < hull->n_eq)
02377                         continue;
02378 
02379                 for (j = 0; j < hull->n_ineq; ++j) {
02380                         if (isl_int_is_zero(hull->ineq[j][1 + nparam + i]))
02381                                 continue;
02382                         if (isl_seq_first_non_zero(hull->ineq[j]+1+nparam+i+1,
02383                                                     left) != -1 ||
02384                             isl_seq_first_non_zero(hull->ineq[j]+1+nparam,
02385                                                     i) != -1)
02386                                 continue;
02387                         if (isl_int_is_pos(hull->ineq[j][1 + nparam + i]))
02388                                 lower = 1;
02389                         else
02390                                 upper = 1;
02391                         if (lower && upper)
02392                                 break;
02393                 }
02394 
02395                 if (lower && upper)
02396                         continue;
02397 
02398                 if (!removed_divs) {
02399                         set = isl_set_remove_divs(set);
02400                         if (!set)
02401                                 goto error;
02402                         removed_divs = 1;
02403                 }
02404                 bounds = set_bounds(set, i);
02405                 hull = isl_basic_set_intersect(hull, bounds);
02406                 if (!hull)
02407                         goto error;
02408         }
02409 
02410         isl_set_free(set);
02411         return hull;
02412 error:
02413         isl_set_free(set);
02414         return NULL;
02415 }

Here is the call graph for this function:

struct isl_basic_set* isl_set_convex_hull ( struct isl_set *  set  )  [read]

Definition at line 1964 of file isl_convex_hull.c.

01965 {
01966         return (struct isl_basic_set *)
01967                 isl_map_convex_hull((struct isl_map *)set);
01968 }

Here is the call graph for this function:

static int isl_set_is_bounded ( struct isl_set *  set  )  [static]

Definition at line 957 of file isl_convex_hull.c.

00958 {
00959         int i;
00960 
00961         for (i = 0; i < set->n; ++i) {
00962                 int bounded = isl_basic_set_is_bounded(set->p[i]);
00963                 if (!bounded || bounded < 0)
00964                         return bounded;
00965         }
00966         return 1;
00967 }

Here is the call graph for this function:

static struct isl_set* isl_set_set_rational ( struct isl_set *  set  )  [static, read]

Definition at line 268 of file isl_convex_hull.c.

00269 {
00270         int i;
00271 
00272         set = isl_set_cow(set);
00273         if (!set)
00274                 return NULL;
00275         for (i = 0; i < set->n; ++i) {
00276                 set->p[i] = isl_basic_set_set_rational(set->p[i]);
00277                 if (!set->p[i])
00278                         goto error;
00279         }
00280         return set;
00281 error:
00282         isl_set_free(set);
00283         return NULL;
00284 }

Here is the call graph for this function:

struct isl_basic_set* isl_set_simple_hull ( struct isl_set *  set  )  [read]

Definition at line 2331 of file isl_convex_hull.c.

02332 {
02333         return (struct isl_basic_set *)
02334                 isl_map_simple_hull((struct isl_map *)set);
02335 }

Here is the call graph for this function:

static int max_constraint_equal ( const void *  entry,
const void *  val 
) [static]

Definition at line 1569 of file isl_convex_hull.c.

01570 {
01571         struct max_constraint *a = (struct max_constraint *)entry;
01572         isl_int *b = (isl_int *)val;
01573 
01574         return isl_seq_eq(a->c->row[0] + 1, b, a->c->n_col - 1);
01575 }

Here is the call graph for this function:

static struct isl_basic_set* modulo_affine_hull ( struct isl_ctx *  ctx,
struct isl_set *  set,
struct isl_basic_set *  affine_hull 
) [static, read]

Definition at line 1887 of file isl_convex_hull.c.

01889 {
01890         struct isl_mat *T;
01891         struct isl_mat *T2;
01892         struct isl_basic_set *dummy;
01893         struct isl_basic_set *convex_hull;
01894 
01895         dummy = isl_basic_set_remove_equalities(
01896                         isl_basic_set_copy(affine_hull), &T, &T2);
01897         if (!dummy)
01898                 goto error;
01899         isl_basic_set_free(dummy);
01900         set = isl_set_preimage(set, T);
01901         convex_hull = uset_convex_hull(set);
01902         convex_hull = isl_basic_set_preimage(convex_hull, T2);
01903         convex_hull = isl_basic_set_intersect(convex_hull, affine_hull);
01904         return convex_hull;
01905 error:
01906         isl_basic_set_free(affine_hull);
01907         isl_set_free(set);
01908         return NULL;
01909 }

Here is the call graph for this function:

static struct isl_basic_set* modulo_lineality ( struct isl_set *  set,
struct isl_basic_set *  lin 
) [static, read]

Definition at line 1053 of file isl_convex_hull.c.

01055 {
01056         unsigned total = isl_basic_set_total_dim(lin);
01057         unsigned lin_dim;
01058         struct isl_basic_set *hull;
01059         struct isl_mat *M, *U, *Q;
01060 
01061         if (!set || !lin)
01062                 goto error;
01063         lin_dim = total - lin->n_eq;
01064         M = isl_mat_sub_alloc(set->ctx, lin->eq, 0, lin->n_eq, 1, total);
01065         M = isl_mat_left_hermite(set->ctx, M, 0, &U, &Q);
01066         if (!M)
01067                 goto error;
01068         isl_mat_free(set->ctx, M);
01069         isl_basic_set_free(lin);
01070 
01071         isl_mat_drop_rows(set->ctx, Q, Q->n_row - lin_dim, lin_dim);
01072 
01073         U = isl_mat_lin_to_aff(set->ctx, U);
01074         Q = isl_mat_lin_to_aff(set->ctx, Q);
01075 
01076         set = isl_set_preimage(set, U);
01077         set = isl_set_remove_dims(set, total - lin_dim, lin_dim);
01078         hull = uset_convex_hull(set);
01079         hull = isl_basic_set_preimage(hull, Q);
01080 
01081         return hull;
01082 error:
01083         isl_basic_set_free(lin);
01084         isl_set_free(set);
01085         return NULL;
01086 }

Here is the call graph for this function:

static struct isl_basic_set* proto_hull ( struct isl_set *  set,
int *  is_hull 
) [static, read]

Definition at line 1760 of file isl_convex_hull.c.

01761 {
01762         struct isl_basic_set *hull;
01763         unsigned n_ineq;
01764         int i;
01765 
01766         n_ineq = 1;
01767         for (i = 0; i < set->n; ++i) {
01768                 n_ineq += set->p[i]->n_eq;
01769                 n_ineq += set->p[i]->n_ineq;
01770         }
01771         hull = isl_basic_set_alloc_dim(isl_dim_copy(set->dim), 0, 0, n_ineq);
01772         hull = isl_basic_set_set_rational(hull);
01773         if (!hull)
01774                 return NULL;
01775         return common_constraints(hull, set, is_hull);
01776 }

Here is the call graph for this function:

static struct isl_basic_set* set_bounds ( struct isl_set *  set,
int  dim 
) [static, read]

Definition at line 2339 of file isl_convex_hull.c.

02340 {
02341         unsigned set_dim = isl_set_dim(set, isl_dim_set);
02342         set = isl_set_copy(set);
02343         set = isl_set_eliminate_dims(set, dim + 1, set_dim - (dim + 1));
02344         set = isl_set_eliminate_dims(set, 0, dim);
02345         return isl_set_convex_hull(set);
02346 }

Here is the call graph for this function:

static struct isl_set* set_project_out ( struct isl_ctx *  ctx,
struct isl_set *  set,
unsigned  n 
) [static, read]

Definition at line 852 of file isl_convex_hull.c.

00854 {
00855         return isl_set_remove_dims(set, isl_set_n_dim(set) - n, n);
00856 }

Here is the call graph for this function:

static struct sh_data* sh_data_alloc ( struct isl_set *  set,
unsigned  n_ineq