From 9aecd59c7d01c7019255427b4d74e49b88a5a95d Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 8 Aug 2009 12:20:56 +0200 Subject: [PATCH 1/1] isl_solve_lp: optionally return solution point The caller may now not be interested in the optimal value anymore, so make returning this optimal value optional. --- include/isl_lp.h | 3 ++- isl_convex_hull.c | 6 ++--- isl_lp.c | 20 ++++++++++++----- isl_lp_no_piplib.c | 3 ++- isl_lp_piplib.c | 66 +++++++++++++++++++++++++++++++++++++++++------------- isl_lp_piplib.h | 3 ++- isl_map.c | 2 +- isl_tab.c | 2 +- 8 files changed, 77 insertions(+), 28 deletions(-) diff --git a/include/isl_lp.h b/include/isl_lp.h index c86b93b..d3f4945 100644 --- a/include/isl_lp.h +++ b/include/isl_lp.h @@ -16,7 +16,8 @@ extern "C" { enum isl_lp_result isl_solve_lp(struct isl_basic_map *bmap, int maximize, isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom); + isl_int *opt_denom, + struct isl_vec **sol); #if defined(__cplusplus) } diff --git a/isl_convex_hull.c b/isl_convex_hull.c index 1980cca..8cf0fce 100644 --- a/isl_convex_hull.c +++ b/isl_convex_hull.c @@ -50,7 +50,7 @@ int isl_basic_map_constraint_is_redundant(struct isl_basic_map **bmap, if (i < total) return 0; - res = isl_solve_lp(*bmap, 0, c, (*bmap)->ctx->one, opt_n, opt_d); + res = isl_solve_lp(*bmap, 0, c, (*bmap)->ctx->one, opt_n, opt_d, NULL); if (res == isl_lp_unbounded) return 0; if (res == isl_lp_error) @@ -129,7 +129,7 @@ static int uset_is_bound(struct isl_set *set, isl_int *c, unsigned len) continue; res = isl_solve_lp((struct isl_basic_map*)set->p[j], - 0, c, set->ctx->one, &opt, &opt_denom); + 0, c, set->ctx->one, &opt, &opt_denom, NULL); if (res == isl_lp_unbounded) break; if (res == isl_lp_error) @@ -482,7 +482,7 @@ static isl_int *wrap_facet(struct isl_set *set, isl_int *facet, isl_int *ridge) isl_int_init(num); isl_int_init(den); res = isl_solve_lp((struct isl_basic_map *)lp, 0, - obj->block.data, set->ctx->one, &num, &den); + obj->block.data, set->ctx->one, &num, &den, NULL); if (res == isl_lp_ok) { isl_int_neg(num, num); isl_seq_combine(facet, num, facet, den, ridge, dim); diff --git a/isl_lp.c b/isl_lp.c index c39e338..4a01370 100644 --- a/isl_lp.c +++ b/isl_lp.c @@ -6,7 +6,8 @@ enum isl_lp_result isl_tab_solve_lp(struct isl_basic_map *bmap, int maximize, isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom) + isl_int *opt_denom, + struct isl_vec **sol) { struct isl_tab *tab; enum isl_lp_result res; @@ -18,6 +19,11 @@ enum isl_lp_result isl_tab_solve_lp(struct isl_basic_map *bmap, int maximize, bmap = isl_basic_map_gauss(bmap, NULL); tab = isl_tab_from_basic_map(bmap); res = isl_tab_min(tab, f, bmap->ctx->one, opt, opt_denom, 0); + if (res == isl_lp_ok && sol) { + *sol = isl_tab_get_sample_value(tab); + if (!*sol) + res = isl_lp_error; + } isl_tab_free(tab); if (maximize) @@ -36,18 +42,22 @@ enum isl_lp_result isl_tab_solve_lp(struct isl_basic_map *bmap, int maximize, * The return value reflects the nature of the result (empty, unbounded, * minmimal or maximal value returned in *opt). */ -enum isl_lp_result isl_solve_lp(struct isl_basic_map *bmap, int maximize, +enum isl_lp_result isl_solve_lp(struct isl_basic_map *bmap, int max, isl_int *f, isl_int d, isl_int *opt, - isl_int *opt_denom) + isl_int *opt_denom, + struct isl_vec **sol) { + if (sol) + *sol = NULL; + if (!bmap) return isl_lp_error; switch (bmap->ctx->lp_solver) { case ISL_LP_PIP: - return isl_pip_solve_lp(bmap, maximize, f, d, opt, opt_denom); + return isl_pip_solve_lp(bmap, max, f, d, opt, opt_denom, sol); case ISL_LP_TAB: - return isl_tab_solve_lp(bmap, maximize, f, d, opt, opt_denom); + return isl_tab_solve_lp(bmap, max, f, d, opt, opt_denom, sol); default: return isl_lp_error; } diff --git a/isl_lp_no_piplib.c b/isl_lp_no_piplib.c index c55fad0..1b6173a 100644 --- a/isl_lp_no_piplib.c +++ b/isl_lp_no_piplib.c @@ -2,7 +2,8 @@ enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize, isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom) + isl_int *opt_denom, + struct isl_vec **sol) { return isl_lp_error; } diff --git a/isl_lp_piplib.c b/isl_lp_piplib.c index b4e9bd9..823081b 100644 --- a/isl_lp_piplib.c +++ b/isl_lp_piplib.c @@ -1,11 +1,54 @@ #include "isl_map.h" +#include "isl_vec.h" #include "isl_lp.h" #include "isl_piplib.h" #include "isl_map_piplib.h" +static void copy_solution(struct isl_vec *vec, int maximize, isl_int *opt, + isl_int *opt_denom, PipQuast *sol) +{ + int i; + PipList *list; + isl_int tmp; + + if (opt) { + if (opt_denom) { + isl_seq_cpy_from_pip(opt, + &sol->list->vector->the_vector[0], 1); + isl_seq_cpy_from_pip(opt_denom, + &sol->list->vector->the_deno[0], 1); + } else if (maximize) + mpz_fdiv_q(*opt, sol->list->vector->the_vector[0], + sol->list->vector->the_deno[0]); + else + mpz_cdiv_q(*opt, sol->list->vector->the_vector[0], + sol->list->vector->the_deno[0]); + } + + if (!vec) + return; + + isl_int_init(tmp); + isl_int_set_si(vec->el[0], 1); + for (i = 0, list = sol->list->next; list; ++i, list = list->next) { + isl_seq_cpy_from_pip(&vec->el[1 + i], + &list->vector->the_deno[0], 1); + isl_int_lcm(vec->el[0], vec->el[0], vec->el[1 + i]); + } + for (i = 0, list = sol->list->next; list; ++i, list = list->next) { + isl_seq_cpy_from_pip(&tmp, &list->vector->the_deno[0], 1); + isl_int_divexact(tmp, vec->el[0], tmp); + isl_seq_cpy_from_pip(&vec->el[1 + i], + &list->vector->the_vector[0], 1); + isl_int_mul(vec->el[1 + i], vec->el[1 + i], tmp); + } + isl_int_clear(tmp); +} + enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize, isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom) + isl_int *opt_denom, + struct isl_vec **vec) { enum isl_lp_result res = isl_lp_ok; PipMatrix *domain = NULL; @@ -32,23 +75,16 @@ enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize, if (!sol) goto error; - if (!sol->list) + if (vec) + *vec = isl_vec_alloc(bmap->ctx, 1 + total); + if (vec && !*vec) + res = isl_lp_error; + else if (!sol->list) res = isl_lp_empty; else if (entier_zero_p(sol->list->vector->the_deno[0])) res = isl_lp_unbounded; - else { - if (opt_denom) { - isl_seq_cpy_from_pip(opt, - &sol->list->vector->the_vector[0], 1); - isl_seq_cpy_from_pip(opt_denom, - &sol->list->vector->the_deno[0], 1); - } else if (maximize) - mpz_fdiv_q(*opt, sol->list->vector->the_vector[0], - sol->list->vector->the_deno[0]); - else - mpz_cdiv_q(*opt, sol->list->vector->the_vector[0], - sol->list->vector->the_deno[0]); - } + else + copy_solution(*vec, maximize, opt, opt_denom, sol); pip_matrix_free(domain); pip_quast_free(sol); return res; diff --git a/isl_lp_piplib.h b/isl_lp_piplib.h index 190606e..2284e0d 100644 --- a/isl_lp_piplib.h +++ b/isl_lp_piplib.h @@ -9,7 +9,8 @@ extern "C" { enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize, isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom); + isl_int *opt_denom, + struct isl_vec **sol); #if defined(__cplusplus) } diff --git a/isl_map.c b/isl_map.c index 2b17f91..0cdc6cd 100644 --- a/isl_map.c +++ b/isl_map.c @@ -4396,7 +4396,7 @@ int isl_basic_set_compare_at(struct isl_basic_set *bset1, goto error; isl_int_init(num); isl_int_init(den); - res = isl_solve_lp(bmap1, 0, obj->block.data, ctx->one, &num, &den); + res = isl_solve_lp(bmap1, 0, obj->block.data, ctx->one, &num, &den, NULL); if (res == isl_lp_empty) cmp = 0; else if (res == isl_lp_ok && isl_int_is_pos(num)) diff --git a/isl_tab.c b/isl_tab.c index ff6ed85..840c940 100644 --- a/isl_tab.c +++ b/isl_tab.c @@ -1935,7 +1935,7 @@ enum isl_lp_result isl_tab_min(struct isl_tab *tab, tab->mat->row[var->index][pos]); } } - if (res == isl_lp_ok) { + if (opt && res == isl_lp_ok) { if (opt_denom) { isl_int_set(*opt, tab->mat->row[var->index][1]); isl_int_set(*opt_denom, tab->mat->row[var->index][0]); -- 2.7.4