From d2ec7899e1497a9a41e687ca790a0a9342be1191 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 3 Apr 2010 16:32:23 +0200 Subject: [PATCH] drop barvinok_enumerate_pip_with_options --- Makefile.am | 6 +- barvinok/barvinok.h | 4 - barvinok_e.cc | 40 +------ barvinok_enumerate_e.cc | 8 -- doc/Internal.tex | 8 +- piptest.c | 48 -------- piputil.c | 287 ------------------------------------------------ piputil.h | 11 -- 8 files changed, 4 insertions(+), 408 deletions(-) delete mode 100644 piptest.c delete mode 100644 piputil.c delete mode 100644 piputil.h diff --git a/Makefile.am b/Makefile.am index a90fd62..9b0388a 100644 --- a/Makefile.am +++ b/Makefile.am @@ -66,7 +66,7 @@ bin_PROGRAMS = barvinok_count barvinok_enumerate barvinok_enumerate_e \ noinst_PROGRAMS = test testlib randomtest \ remove_redundant_equalities \ barvinok_union polytope_volume test_approx \ - barvinok_summate verify_lexsmaller piptest \ + barvinok_summate verify_lexsmaller \ polyhedron_sample 4coins lexmin @bv_barvinok_bound@ \ @bv_cone_hilbert_basis@ cone_integer_hull \ polytope_lattice_width polytope_minimize \ @@ -156,8 +156,6 @@ libbarvinok_core_la_SOURCES = \ param_polynomial.h \ param_util.c \ param_util.h \ - piputil.h \ - piputil.c \ $(POLYSIGN_CDD) \ $(POLYSIGN_GLPK) \ polysign.c \ @@ -492,7 +490,7 @@ check-enumerate_e: barvinok_enumerate_e$(EXEEXT) @for dir in $(BEE_TESTDIRS); do \ for i in $(top_srcdir)/tests/$$dir/*; do \ if test -f $$i; then \ - for options in '' '--pip' '--pip --omega' '--isl'; do \ + for options in '' '--isl --omega' '--isl'; do \ for spec in 'random' 'bf' 'df'; do \ opt="--specialization=$$spec $$options"; \ echo $$i $$opt; \ diff --git a/barvinok/barvinok.h b/barvinok/barvinok.h index 2055a34..dd257fd 100644 --- a/barvinok/barvinok.h +++ b/barvinok/barvinok.h @@ -33,10 +33,6 @@ evalue* barvinok_enumerate_e_with_options(Polyhedron *P, unsigned exist, unsigned nparam, struct barvinok_options *options); evalue *barvinok_enumerate_isl(Polyhedron *P, unsigned exist, unsigned nparam, struct barvinok_options *options); -evalue *barvinok_enumerate_pip(Polyhedron *P, - unsigned exist, unsigned nparam, unsigned MaxRays); -evalue *barvinok_enumerate_pip_with_options(Polyhedron *P, - unsigned exist, unsigned nparam, struct barvinok_options *options); evalue *barvinok_enumerate_scarf(Polyhedron *P, unsigned exist, unsigned nparam, struct barvinok_options *options); diff --git a/barvinok_e.cc b/barvinok_e.cc index 9292ad1..8f70e2c 100644 --- a/barvinok_e.cc +++ b/barvinok_e.cc @@ -4,7 +4,6 @@ #include #include #include "param_util.h" -#include "piputil.h" #include "reduce_domain.h" #include "config.h" @@ -1126,43 +1125,6 @@ static evalue* enumerate_vd(Polyhedron **PA, return EP; } -evalue* barvinok_enumerate_pip(Polyhedron *P, unsigned exist, unsigned nparam, - unsigned MaxRays) -{ - evalue *E; - barvinok_options *options = barvinok_options_new_with_defaults(); - options->MaxRays = MaxRays; - E = barvinok_enumerate_pip_with_options(P, exist, nparam, options); - barvinok_options_free(options); - return E; -} - -evalue *barvinok_enumerate_pip_with_options(Polyhedron *P, - unsigned exist, unsigned nparam, struct barvinok_options *options) -{ - int nvar = P->Dimension - exist - nparam; - evalue *EP = evalue_zero(); - Polyhedron *Q, *N; - -#ifdef DEBUG_ER - fprintf(stderr, "\nER: PIP\n"); -#endif /* DEBUG_ER */ - - Polyhedron *D = pip_projectout(P, nvar, exist, nparam); - for (Q = D; Q; Q = N) { - N = Q->next; - Q->next = 0; - evalue *E; - exist = Q->Dimension - nvar - nparam; - E = barvinok_enumerate_e_with_options(Q, exist, nparam, options); - Polyhedron_Free(Q); - eadd(E, EP); - evalue_free(E); - } - - return EP; -} - evalue *barvinok_enumerate_isl(Polyhedron *P, unsigned exist, unsigned nparam, struct barvinok_options *options) { @@ -1541,7 +1503,7 @@ next: if (EP) goto out; - EP = barvinok_enumerate_pip_with_options(P, exist, nparam, options); + EP = barvinok_enumerate_isl(P, exist, nparam, options); if (EP) goto out; diff --git a/barvinok_enumerate_e.cc b/barvinok_enumerate_e.cc index 01957c7..657f0fc 100644 --- a/barvinok_enumerate_e.cc +++ b/barvinok_enumerate_e.cc @@ -31,7 +31,6 @@ struct argp_option argp_options[] = { { "isl", 'i', 0, 0 }, { "omega", 'o', 0, 0 }, { "parker", 'P', 0, 0 }, - { "pip", 'p', 0, 0 }, { "series", 's', 0, 0 }, { "series", 's', 0, 0, "compute rational generating function" }, { "explicit", 'e', 0, 0, "convert rgf to psp" }, @@ -45,7 +44,6 @@ struct arguments { int isl; int omega; int parker; - int pip; int scarf; int series; int function; @@ -87,9 +85,6 @@ error_t parse_opt(int key, char *arg, struct argp_state *state) case 'i': arguments->isl = 1; break; - case 'p': - arguments->pip = 1; - break; default: return ARGP_ERR_UNKNOWN; } @@ -167,7 +162,6 @@ int main(int argc, char **argv) arguments.isl = 0; arguments.omega = 0; arguments.parker = 0; - arguments.pip = 0; arguments.scarf = 0; arguments.series = 0; arguments.function = 0; @@ -232,8 +226,6 @@ int main(int argc, char **argv) EP = barvinok_enumerate_scarf(A, exist, nparam, options); else if (arguments.isl && exist > 0) EP = barvinok_enumerate_isl(A, exist, nparam, options); - else if (arguments.pip && exist > 0) - EP = barvinok_enumerate_pip_with_options(A, exist, nparam, options); else EP = barvinok_enumerate_e_with_options(A, exist, nparam, options); reduce_evalue(EP); diff --git a/doc/Internal.tex b/doc/Internal.tex index c82d286..84dce06 100644 --- a/doc/Internal.tex +++ b/doc/Internal.tex @@ -942,9 +942,8 @@ evalue* barvinok_enumerate_with_options(Polyhedron *P, \end{verbatim} For enumerating parametric sets with existentially quantified variables, -we provide three functions: +we provide two functions: \ai[\tt]{barvinok\_enumerate\_e}, -\ai[\tt]{barvinok\_enumerate\_pip} and \ai[\tt]{barvinok\_enumerate\_isl}. \begin{verbatim} @@ -953,11 +952,6 @@ evalue* barvinok_enumerate_e(Polyhedron *P, evalue* barvinok_enumerate_e_with_options(Polyhedron *P, unsigned exist, unsigned nparam, struct barvinok_options *options); -evalue *barvinok_enumerate_pip(Polyhedron *P, - unsigned exist, unsigned nparam, unsigned MaxRays); -evalue* barvinok_enumerate_pip_with_options(Polyhedron *P, - unsigned exist, unsigned nparam, - struct barvinok_options *options); evalue *barvinok_enumerate_isl(Polyhedron *P, unsigned exist, unsigned nparam, struct barvinok_options *options); diff --git a/piptest.c b/piptest.c deleted file mode 100644 index d06f30f..0000000 --- a/piptest.c +++ /dev/null @@ -1,48 +0,0 @@ -#include "piputil.h" -#include -#include - -#define MAXRAYS 0 - -int main(int argc, char **argv) -{ - Polyhedron *A; - Matrix *M; - Polyhedron *D, *P, *N; - const char **param_name; - int exist, nparam, nvar; - char s[128]; - evalue sum; - - M = Matrix_Read(); - A = Constraints2Polyhedron(M, MAXRAYS); - Matrix_Free(M); - - fgets(s, 128, stdin); - while ((*s=='#') || (sscanf(s, "E %d", &exist)<1)) - fgets(s, 128, stdin); - - fgets(s, 128, stdin); - while ((*s=='#') || (sscanf(s, "P %d", &nparam)<1)) - fgets(s, 128, stdin); - - Polyhedron_Print(stdout, P_VALUE_FMT, A); - printf("exist: %d, nparam: %d\n", exist, nparam); - param_name = Read_ParamNames(stdin, nparam); - - nvar = A->Dimension - exist - nparam; - D = pip_projectout(A, nvar, exist, nparam); - - value_init(sum.d); - evalue_set_si(&sum, 0, 1); - for (P = D; P; P = N) { - evalue *EP; - N = P->next; - P->next = 0; - exist = P->Dimension - nvar - nparam; - EP = barvinok_enumerate_e(P, exist, nparam, MAXRAYS); - print_evalue(stderr, EP, (const char **)param_name); - eadd(EP, &sum); - } - print_evalue(stderr, &sum, (const char **)param_name); -} diff --git a/piputil.c b/piputil.c deleted file mode 100644 index b74a315..0000000 --- a/piputil.c +++ /dev/null @@ -1,287 +0,0 @@ -#include /* needed for piplib ! */ -#include -#include -#include "piputil.h" - -#define MAXRAYS POL_NO_DUAL - -static PipMatrix *poly2pip(Polyhedron *P, int pos, int n, int nparam) -{ - PipMatrix * matrix; - int i, j; - unsigned int extra = P->Dimension - pos - n - nparam; - - matrix = pip_matrix_alloc(P->NbConstraints, P->Dimension+2); - for (i = 0; i < P->NbConstraints; ++i) { - value_assign(matrix->p[i][0], P->Constraint[i][0]); - for (j = 0; j < n; ++j) - value_assign(matrix->p[i][1+j], P->Constraint[i][1+pos+j]); - for (j = 0; j < pos; ++j) - value_assign(matrix->p[i][1+n+j], P->Constraint[i][1+j]); - for (j = 0; j < extra; ++j) - value_assign(matrix->p[i][1+n+pos+j], P->Constraint[i][1+n+pos+j]); - for (j = 1+pos+n+extra; j < P->Dimension+2; ++j) - value_assign(matrix->p[i][j], P->Constraint[i][j]); - } - - return matrix; -} - -static int max_new(PipQuast *q, int max, int d, int *maxd) -{ - PipNewparm *p; - - for (p = q->newparm; p; p = p->next) - if (p->rank > max) - max = p->rank; - if (q->condition) { - if (++d > *maxd) - *maxd = d; - max = max_new(q->next_else, max, d, maxd); - max = max_new(q->next_then, max, d, maxd); - } - return max; -} - -/* - * v: total number of variables in original problem - * pos: position of minimized variables - * n: dimension of space in which minimum was taken - * i.e., number of minimized vars in original problem - * e: number of extra existential variables - * d: total dimension - */ -struct scan_data { - Matrix *M; - int v; - int pos; - int n; - int e; - int d; - void (*f)(struct scan_data *data, PipQuast *q, int i); -}; - -static int vectorpos2cpos(struct scan_data *data, int j) -{ - int np = data->d - data->v - data->e; - int l; - - if (j < data->pos) - l = 1+j; - else if (j < data->v - data->n) - l = 1+data->n+j; - else if (j < data->v-data->n+np) - l = 1+data->n+data->e+j; - else - l = 1+data->n+j-np; - - return l; -} - -/* - * returns true if some solution exist in the whole quast q - */ -static int full_quast(PipQuast *q) -{ - return q->condition ? full_quast(q->next_then) && full_quast(q->next_else) - : q->list != NULL; -} - -/* - * i: next row - * - * Dimensions in the resulting domain are: - * v n e (d-v-n-e) - */ -static void scan_quast_r(struct scan_data *data, PipQuast *q, int i) -{ - PipNewparm *p; - int skip; - - /* Skip to a (random) leaf if we are only interested in whether - * a solution exists. - */ - skip = data->n == 0 && full_quast(q); - while (skip && q->condition) - q = q->next_then; - - for (p = q->newparm; !skip && p; p = p->next) { - int j, l; - PipVector *vec = p->vector; - - value_set_si(data->M->p[i][0], 1); - Vector_Set(data->M->p[i]+1, 0, data->d); - - for (j = 0; j < vec->nb_elements-1; ++j) { - l = vectorpos2cpos(data, j); - value_assign(data->M->p[i][l], vec->the_vector[j]); - } - l = vectorpos2cpos(data, p->rank); - value_oppose(data->M->p[i][l], p->deno); - value_assign(data->M->p[i][1+data->d], vec->the_vector[j]); - ++i; - - value_set_si(data->M->p[i][0], 1); - Vector_Set(data->M->p[i]+1, 0, data->d); - - for (j = 0; j < vec->nb_elements-1; ++j) { - l = vectorpos2cpos(data, j); - value_oppose(data->M->p[i][l], vec->the_vector[j]); - } - l = vectorpos2cpos(data, p->rank); - value_assign(data->M->p[i][l], p->deno); - value_oppose(data->M->p[i][1+data->d], vec->the_vector[j]); - value_addto(data->M->p[i][1+data->d], data->M->p[i][1+data->d], p->deno); - value_decrement(data->M->p[i][1+data->d], data->M->p[i][1+data->d]); - ++i; - } - - if (q->condition) { - int j; - value_set_si(data->M->p[i][0], 1); - Vector_Set(data->M->p[i]+1, 0, data->d); - - for (j = 0; j < q->condition->nb_elements-1; ++j) { - int l = vectorpos2cpos(data, j); - value_assign(data->M->p[i][l], q->condition->the_vector[j]); - } - value_assign(data->M->p[i][1+data->d], q->condition->the_vector[j]); - scan_quast_r(data, q->next_then, i+1); - - for (j = 0; j < q->condition->nb_elements-1; ++j) { - int l = vectorpos2cpos(data, j); - value_oppose(data->M->p[i][l], q->condition->the_vector[j]); - } - value_oppose(data->M->p[i][1+data->d], q->condition->the_vector[j]); - value_decrement(data->M->p[i][1+data->d], data->M->p[i][1+data->d]); - scan_quast_r(data, q->next_else, i+1); - - return; - } - - /* if data->n is zero, we are only interested in the domains - * where a solution exists and not in the actual solution - */ - if (q->list && data->n) { - PipList *l; - int j, k; - for (j = 0, l = q->list; l; ++j, l = l->next) { - Vector_Set(data->M->p[i], 0, data->d+1); - value_set_si(data->M->p[i][1+data->pos+j], -1); - - for (k = 0; k < l->vector->nb_elements-1; ++k) { - int ll = vectorpos2cpos(data, k); - value_assign(data->M->p[i][ll], l->vector->the_vector[k]); - } - value_assign(data->M->p[i][1+data->d], l->vector->the_vector[k]); - - ++i; - } - } - data->f(data, q, i); -} - -static void scan_quast(struct scan_data *data, PipQuast *q) -{ - int nparam, nexist, d, i, rows; - - nparam = data->d - data->n; - - d = 0; - nexist = max_new(q, nparam-1, 0, &d) - nparam+1; - rows = 2 * nexist + d + data->n; - - /* nparam now refers to the number of parameters in the original polyhedron */ - nparam -= data->v - data->n; - - data->e = nexist; - data->d = data->v + nexist + nparam; - - data->M = Matrix_Alloc(rows, 1+data->d+1); - - scan_quast_r(data, q, 0); - Matrix_Free(data->M); -} - -struct quast2poly_data { - struct scan_data scan; - Polyhedron* D; -}; - -static void add_quast_base(struct scan_data *data, PipQuast *q, int i) -{ - struct quast2poly_data *qdata = (struct quast2poly_data *)data; - if (q->list) { - Matrix *C; - Polyhedron *P; - C = Matrix_Alloc(i, 1+data->d+1); - Vector_Copy(data->M->p[0], C->p[0], i * (1+data->d+1)); - P = Constraints2Polyhedron(C, MAXRAYS); - Matrix_Free(C); - P->next = qdata->D; - qdata->D = P; - } -} - -/* - * nvar: total number of variables, including the minimized variables, - * but excluding the parameters - * nparam: the number of parameters in the PIP problem, excluding the "big parameter" - * for maximization problems, i.e., the - * total number of variables minus the minimized variables - * pos: position of the first minimized variable - * n: number of minimized variables - */ -static Polyhedron *quast2poly(PipQuast *q, int nvar, int nparam, int pos, int n) -{ - struct quast2poly_data data; - - data.scan.v = nvar; - data.scan.pos = pos; - data.scan.n = n; - data.scan.d = n+nparam; - - data.D = 0; - data.scan.f = add_quast_base; - - scan_quast(&data.scan, q); - - return data.D; -} - -Polyhedron *pip_projectout(Polyhedron *P, int pos, int n, int nparam) -{ - PipOptions *options; - PipMatrix * domain; - unsigned int nvar = P->Dimension - nparam; - PipMatrix *context = pip_matrix_alloc(0, P->Dimension - n + 2); - PipQuast *sol; - Polyhedron *min; - - POL_ENSURE_INEQUALITIES(P); - - domain = poly2pip(P, pos, n, nparam); -#ifdef PIP_DEBUG - pip_matrix_print(stderr, domain); - pip_matrix_print(stderr, context); -#endif - - options = pip_options_init(); - options->Urs_unknowns = -1; - options->Urs_parms = -1; - options->Simplify = 1; - sol = pip_solve(domain, context, -1, options); - -#ifdef PIP_DEBUG - pip_quast_print(stderr, sol, 0); -#endif - - min = quast2poly(sol, nvar - n, P->Dimension - n, 0, 0); - - pip_quast_free(sol); - pip_matrix_free(context); - pip_matrix_free(domain); - pip_options_free(options); - - return min; -} diff --git a/piputil.h b/piputil.h deleted file mode 100644 index 2531ac8..0000000 --- a/piputil.h +++ /dev/null @@ -1,11 +0,0 @@ -#include - -#if defined(__cplusplus) -extern "C" { -#endif - -Polyhedron *pip_projectout(Polyhedron *P, int pos, int n, int nparam); - -#if defined(__cplusplus) -} -#endif -- 2.11.4.GIT