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