barvinok_enumerate_e.cc

   1 #include <unistd.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 #include <barvinok/util.h>
   5 #include <barvinok/barvinok.h>
   6 #include "argp.h"
   7 #include "error.h"
   8 #include "config.h"
   9 #ifdef HAVE_OMEGA
  10 #include "omega/convert.h"
  11 #endif
  12 #include "verify.h"
  13 #include "verif_ehrhart.h"
  14
  15 /* The input of this example program is a polytope in combined
  16  * data and parameter space followed by two lines indicating
  17  * the number of existential variables and parameters respectively.
  18  * The first lines starts with "E ", followed by a number.
  19  * The second lines starts with "P ", followed by a number.
  20  * These two lines are (optionally) followed by the names of the parameters.
  21  * The polytope is in PolyLib notation.
  22  */
  23
  24 struct argp_option argp_options[] = {
  25     { "omega",              'o',    0,      0 },
  26     { "pip",                'p',    0,      0 },
  27     { "series",             's',    0,      0 },
  28     { "scarf",              'S',    0,      0 },
  29     { "convert",            'c',    0,      0 },
  30     { "floor",              'f',    0,      0 },
  31     { "range-reduction",    'R',    0,      0 },
  32     { 0 }
  33 };
  34
  35 struct arguments {
  36     struct verify_options    verify;
  37     int range;
  38     int convert;
  39     int omega;
  40     int pip;
  41     int scarf;
  42     int series;
  43     int floor;
  44 };
  45
  46 error_t parse_opt(int key, char *arg, struct argp_state *state)
  47 {
  48     struct arguments *arguments = (struct arguments *)(state->input);
  49
  50     switch (key) {
  51     case ARGP_KEY_INIT:
  52         state->child_inputs[0] = arguments->verify.barvinok;
  53         state->child_inputs[1] = &arguments->verify;
  54         break;
  55     case 's':
  56         arguments->series = 1;
  57         break;
  58     case 'S':
  59         arguments->scarf = 1;
  60         break;
  61     case 'o':
  62 #ifdef HAVE_OMEGA
  63         arguments->omega = 1;
  64 #else
  65         error(0, 0, "--omega option not supported");
  66 #endif
  67         break;
  68     case 'p':
  69 #ifdef HAVE_PIPLIB
  70         arguments->pip = 1;
  71 #else
  72         error(0, 0, "--pip option not supported");
  73 #endif
  74         break;
  75     case 'f':
  76         arguments->floor = 1;
  77         break;
  78     case 'c':
  79         arguments->convert = 1;
  80         break;
  81     case 'R':
  82         arguments->range = 1;
  83         break;
  84     default:
  85         return ARGP_ERR_UNKNOWN;
  86     }
  87     return 0;
  88 }
  89
  90 #ifdef HAVE_OMEGA
  91
  92 Polyhedron *Omega_simplify(Polyhedron *P,
  93                             unsigned exist, unsigned nparam, char **parms)
  94 {
  95     varvector varv;
  96     varvector paramv;
  97     Relation r = Polyhedron2relation(P, exist, nparam, parms);
  98     Polyhedron_Free(P);
  99     return relation2Domain(r, varv, paramv);
 100 }
 101 #else
 102 Polyhedron *Omega_simplify(Polyhedron *P,
 103                             unsigned exist, unsigned nparam, char **parms)
 104 {
 105     return P;
 106 }
 107 #endif
 108
 109 static void verify_results(Polyhedron *P, evalue *EP, int exist, int nparam,
 110                            verify_options *options);
 111
 112 int main(int argc, char **argv)
 113 {
 114     Polyhedron *A;
 115     Matrix *MA;
 116     char **param_name;
 117     int exist, nparam, nvar;
 118     char s[128];
 119     evalue *EP;
 120     int print_solution = 1;
 121     struct arguments arguments;
 122     static struct argp_child argp_children[] = {
 123         { &barvinok_argp,       0,      0,              0 },
 124         { &verify_argp,         0,      "verification", 1 },
 125         { 0 }
 126     };
 127     static struct argp argp = { argp_options, parse_opt, 0, 0, argp_children };
 128     struct barvinok_options *options = barvinok_options_new_with_defaults();
 129
 130     arguments.verify.barvinok = options;
 131     arguments.range = 0;
 132     arguments.convert = 0;
 133     arguments.omega = 0;
 134     arguments.pip = 0;
 135     arguments.scarf = 0;
 136     arguments.series = 0;
 137     arguments.floor = 0;
 138
 139     argp_parse(&argp, argc, argv, 0, 0, &arguments);
 140
 141     if (arguments.series && !arguments.scarf) {
 142         fprintf(stderr,
 143                 "--series currently only available if --scarf is specified\n");
 144         exit(1);
 145     }
 146
 147     MA = Matrix_Read();
 148     A = Constraints2Polyhedron(MA, options->MaxRays);
 149     Matrix_Free(MA);
 150
 151     fgets(s, 128, stdin);
 152     while ((*s=='#') || (sscanf(s, "E %d", &exist)<1))
 153         fgets(s, 128, stdin);
 154
 155     fgets(s, 128, stdin);
 156     while ((*s=='#') || (sscanf(s, "P %d", &nparam)<1))
 157         fgets(s, 128, stdin);
 158
 159     /******* Read the options: initialize Min and Max ********/
 160     verify_options_set_range(&arguments.verify, A);
 161
 162     if (arguments.verify.verify)
 163         print_solution = 0;
 164
 165     if (print_solution) {
 166         Polyhedron_Print(stdout, P_VALUE_FMT, A);
 167         printf("exist: %d, nparam: %d\n", exist, nparam);
 168     }
 169     param_name = Read_ParamNames(stdin, nparam);
 170     nvar = A->Dimension - exist - nparam;
 171     if (arguments.omega) {
 172         A = Omega_simplify(A, exist, nparam, param_name);
 173         assert(!A->next);
 174         exist = A->Dimension - nvar - nparam;
 175     }
 176     if (arguments.series) {
 177         gen_fun *gf;
 178         barvinok_options *options = barvinok_options_new_with_defaults();
 179         assert(arguments.scarf);
 180         gf = barvinok_enumerate_scarf_series(A, exist, nparam, options);
 181         if (print_solution) {
 182             gf->print(std::cout, nparam, param_name);
 183             puts("");
 184         }
 185         delete gf;
 186         barvinok_options_free(options);
 187     } else {
 188         if (arguments.scarf) {
 189             barvinok_options *options = barvinok_options_new_with_defaults();
 190             EP = barvinok_enumerate_scarf(A, exist, nparam, options);
 191             barvinok_options_free(options);
 192         } else if (arguments.pip && exist > 0)
 193             EP = barvinok_enumerate_pip_with_options(A, exist, nparam, options);
 194         else
 195             EP = barvinok_enumerate_e_with_options(A, exist, nparam, options);
 196         reduce_evalue(EP);
 197         evalue_combine(EP);
 198         if (arguments.range)
 199             evalue_range_reduction(EP);
 200         if (print_solution)
 201             print_evalue(stdout, EP, param_name);
 202         if (arguments.floor) {
 203             fprintf(stderr, "WARNING: floor conversion not supported\n");
 204             evalue_frac2floor2(EP, 0);
 205             if (print_solution)
 206                 print_evalue(stdout, EP, param_name);
 207         } else if (arguments.convert) {
 208             evalue_mod2table(EP, nparam);
 209             if (print_solution)
 210                 print_evalue(stdout, EP, param_name);
 211         }
 212         if (arguments.verify.verify) {
 213             arguments.verify.params = param_name;
 214             verify_results(A, EP, exist, nparam, &arguments.verify);
 215         }
 216         free_evalue_refs(EP);
 217         free(EP);
 218     }
 219     Free_ParamNames(param_name, nparam);
 220     Polyhedron_Free(A);
 221     return 0;
 222 }
 223
 224 void verify_results(Polyhedron *P, evalue *EP, int exist, int nparam,
 225                     verify_options *options)
 226 {
 227     int i;
 228     int res;
 229     Value *p, tmp;
 230     Polyhedron *S, *CS;
 231     unsigned MaxRays = options->barvinok->MaxRays;
 232     Polyhedron *C = Polyhedron_Project(P, nparam);
 233     value_init(tmp);
 234
 235     p = (Value *)malloc(sizeof(Value) * (P->Dimension+2));
 236     for(i=0;i<=P->Dimension;i++) {
 237       value_init(p[i]);
 238       value_set_si(p[i],0);
 239     }
 240     value_init(p[i]);
 241     value_set_si(p[i],1);
 242
 243     /* S = scanning list of polyhedra */
 244     S = Polyhedron_Scan(P, C, MaxRays & POL_NO_DUAL ? 0 : MaxRays);
 245
 246     CS = check_poly_context_scan(C, options);
 247
 248     check_poly_init(C, options);
 249
 250     /******* CHECK NOW *********/
 251     res = 0;
 252     if (S && !check_poly(S, CS, EP, exist, nparam, 0, p, options)) {
 253       fprintf(stderr,"Check failed !\n");
 254       res = -1;
 255     }
 256
 257     if (!options->print_all)
 258         printf( "\n" );
 259
 260     for(i=0;i<=(P->Dimension+1);i++)
 261       value_clear(p[i]);
 262     free(p);
 263     value_clear(tmp);
 264     Domain_Free(S);
 265     Polyhedron_Free(C);
 266     if (CS)
 267         Domain_Free(CS);
 268 }