barvinok_enumerate_e.cc

   1 #include <ctype.h>
   2 #include <unistd.h>
   3 #include <stdlib.h>
   4 #include <assert.h>
   5 #include <barvinok/util.h>
   6 #include <barvinok/barvinok.h>
   7 #include "argp.h"
   8 #include "progname.h"
   9 #include "error.h"
  10 #include "config.h"
  11 #ifdef HAVE_OMEGA
  12 #include "omega_interface/convert.h"
  13 #include "omega_interface/count.h"
  14 #endif
  15 #include "skewed_genfun.h"
  16 #include "verify.h"
  17 #include "verif_ehrhart.h"
  18 #include "verify_series.h"
  19 #include "evalue_convert.h"
  20
  21 /* The input of this example program is a polytope in combined
  22  * data and parameter space followed by two lines indicating
  23  * the number of existential variables and parameters respectively.
  24  * The first lines starts with "E ", followed by a number.
  25  * The second lines starts with "P ", followed by a number.
  26  * These two lines are (optionally) followed by the names of the parameters.
  27  * The polytope is in PolyLib notation.
  28  */
  29
  30 struct argp_option argp_options[] = {
  31     { "isl",                'i',    0,      0 },
  32     { "omega",              'o',    0,      0 },
  33     { "parker",             'P',    0,      0 },
  34     { "pip",                'p',    0,      0 },
  35     { "series",             's',    0,      0 },
  36     { "series",             's', 0, 0, "compute rational generating function" },
  37     { "explicit",           'e', 0, 0, "convert rgf to psp" },
  38     { "scarf",              'S',    0,      0 },
  39     { 0 }
  40 };
  41
  42 struct arguments {
  43     struct verify_options    verify;
  44     struct convert_options   convert;
  45     int isl;
  46     int omega;
  47     int parker;
  48     int pip;
  49     int scarf;
  50     int series;
  51     int function;
  52 };
  53
  54 error_t parse_opt(int key, char *arg, struct argp_state *state)
  55 {
  56     struct arguments *arguments = (struct arguments *)(state->input);
  57
  58     switch (key) {
  59     case ARGP_KEY_INIT:
  60         state->child_inputs[0] = arguments->verify.barvinok;
  61         state->child_inputs[1] = &arguments->verify;
  62         state->child_inputs[2] = &arguments->convert;
  63         break;
  64     case 'e':
  65         arguments->function = 1;
  66         /* fall through */
  67     case 's':
  68         arguments->series = 1;
  69         break;
  70     case 'S':
  71         arguments->scarf = 1;
  72         break;
  73     case 'o':
  74 #ifdef HAVE_OMEGA
  75         arguments->omega = 1;
  76 #else
  77         error(0, 0, "--omega option not supported");
  78 #endif
  79         break;
  80     case 'P':
  81 #ifdef USE_PARKER
  82         arguments->parker = 1;
  83 #else
  84         error(0, 0, "--parker option not supported");
  85 #endif
  86         break;
  87     case 'i':
  88         arguments->isl = 1;
  89         break;
  90     case 'p':
  91         arguments->pip = 1;
  92         break;
  93     default:
  94         return ARGP_ERR_UNKNOWN;
  95     }
  96     return 0;
  97 }
  98
  99 #ifdef HAVE_OMEGA
 100
 101 Polyhedron *Omega_simplify(Polyhedron *P,
 102                             unsigned exist, unsigned nparam, const char **parms,
 103                             unsigned MaxRays)
 104 {
 105     varvector varv;
 106     varvector paramv;
 107     Relation r = Polyhedron2relation(P, exist, nparam, parms);
 108     Polyhedron_Free(P);
 109     return relation2Domain(r, varv, paramv, MaxRays);
 110 }
 111 #else
 112 Polyhedron *Omega_simplify(Polyhedron *P,
 113                             unsigned exist, unsigned nparam, const char **parms,
 114                             unsigned MaxRays)
 115 {
 116     return P;
 117 }
 118
 119 evalue *barvinok_enumerate_parker(Polyhedron *P,
 120                                         unsigned exist, unsigned nparam,
 121                                         unsigned MaxRays)
 122 {
 123     assert(0);
 124     return NULL;
 125 }
 126 #endif
 127
 128 static void verify_results(Polyhedron *P, evalue *EP, gen_fun *gf,
 129                            int exist, int nparam,
 130                            arguments *options);
 131
 132 static char *next_line(FILE *input, char *line, unsigned len)
 133 {
 134         char *p;
 135
 136         do {
 137                 if (!(p = fgets(line, len, input)))
 138                         return NULL;
 139                 while (isspace(*p) && *p != '\n')
 140                         ++p;
 141         } while (*p == '#' || *p == '\n');
 142
 143         return p;
 144 }
 145
 146 int main(int argc, char **argv)
 147 {
 148     Polyhedron *A;
 149     Matrix *MA;
 150     const char **param_name;
 151     int exist, nparam, nvar;
 152     char s[128];
 153     evalue *EP = NULL;
 154     gen_fun *gf = NULL;
 155     int print_solution = 1;
 156     struct arguments arguments;
 157     static struct argp_child argp_children[] = {
 158         { &barvinok_argp,       0,      0,                      0 },
 159         { &verify_argp,         0,      "verification",         BV_GRP_LAST+1 },
 160         { &convert_argp,        0,      "output conversion",    BV_GRP_LAST+2 },
 161         { 0 }
 162     };
 163     static struct argp argp = { argp_options, parse_opt, 0, 0, argp_children };
 164     struct barvinok_options *options = barvinok_options_new_with_defaults();
 165
 166     arguments.verify.barvinok = options;
 167     arguments.isl = 0;
 168     arguments.omega = 0;
 169     arguments.parker = 0;
 170     arguments.pip = 0;
 171     arguments.scarf = 0;
 172     arguments.series = 0;
 173     arguments.function = 0;
 174
 175     set_program_name(argv[0]);
 176     argp_parse(&argp, argc, argv, 0, 0, &arguments);
 177
 178     MA = Matrix_Read();
 179     A = Constraints2Polyhedron(MA, options->MaxRays);
 180     Matrix_Free(MA);
 181
 182     exist = -1;
 183     while (next_line(stdin, s, sizeof(s)))
 184         if (sscanf(s, "E %d", &exist) == 1)
 185             break;
 186     assert(exist >= 0);
 187
 188     nparam = -1;
 189     while (next_line(stdin, s, sizeof(s)))
 190         if (sscanf(s, "P %d", &nparam) == 1)
 191             break;
 192     assert(nparam >= 0);
 193
 194     /******* Read the options: initialize Min and Max ********/
 195
 196     if (arguments.verify.verify) {
 197         verify_options_set_range(&arguments.verify, A->Dimension);
 198         if (!options->verbose)
 199             print_solution = 0;
 200     }
 201
 202     if (print_solution && options->verbose) {
 203         Polyhedron_Print(stdout, P_VALUE_FMT, A);
 204         printf("exist: %d, nparam: %d\n", exist, nparam);
 205     }
 206     param_name = Read_ParamNames(stdin, nparam);
 207     nvar = A->Dimension - exist - nparam;
 208     if (arguments.omega) {
 209         A = Omega_simplify(A, exist, nparam, param_name, options->MaxRays);
 210         assert(!A->next);
 211         exist = A->Dimension - nvar - nparam;
 212     }
 213     if (arguments.series) {
 214         if (arguments.scarf)
 215             gf = barvinok_enumerate_scarf_series(A, exist, nparam, options);
 216         else
 217             gf = barvinok_enumerate_e_series(A, exist, nparam, options);
 218         if (print_solution) {
 219             gf->print(std::cout, nparam, param_name);
 220             puts("");
 221         }
 222         if (arguments.function) {
 223             EP = *gf;
 224             if (print_solution)
 225                 print_evalue(stdout, EP, param_name);
 226         }
 227     } else {
 228         if (arguments.parker)
 229             EP = barvinok_enumerate_parker(A, A->Dimension-nparam-exist,
 230                                                 nparam, options->MaxRays);
 231         else if (arguments.scarf)
 232             EP = barvinok_enumerate_scarf(A, exist, nparam, options);
 233         else if (arguments.isl && exist > 0)
 234             EP = barvinok_enumerate_isl(A, exist, nparam, options);
 235         else if (arguments.pip && exist > 0)
 236             EP = barvinok_enumerate_pip_with_options(A, exist, nparam, options);
 237         else
 238             EP = barvinok_enumerate_e_with_options(A, exist, nparam, options);
 239         reduce_evalue(EP);
 240         if (evalue_convert(EP, &arguments.convert, options->verbose, nparam,
 241                            param_name))
 242             print_solution = 0;
 243         if (print_solution)
 244             print_evalue(stdout, EP, param_name);
 245     }
 246     if (arguments.verify.verify) {
 247         arguments.verify.params = param_name;
 248         verify_results(A, EP, gf, exist, nparam, &arguments);
 249     }
 250     if (gf)
 251         delete gf;
 252     if (EP)
 253         evalue_free(EP);
 254
 255     if (options->print_stats)
 256         barvinok_stats_print(options->stats, stdout);
 257
 258     Free_ParamNames(param_name, nparam);
 259     Polyhedron_Free(A);
 260     barvinok_options_free(options);
 261     return 0;
 262 }
 263
 264 void verify_results(Polyhedron *P, evalue *EP, gen_fun *gf,
 265                        int exist, int nparam,
 266                        arguments *options)
 267 {
 268     int i;
 269     int res = 0;
 270     Vector *p;
 271     Value tmp;
 272     Polyhedron *S, *CS;
 273     unsigned MaxRays = options->verify.barvinok->MaxRays;
 274     Polyhedron *C = NULL;
 275     value_init(tmp);
 276
 277     p = Vector_Alloc(P->Dimension+2);
 278     value_set_si(p->p[P->Dimension+1], 1);
 279
 280     CS = check_poly_context_scan(P, &C, nparam, &options->verify);
 281     if (!C)
 282         C = Universe_Polyhedron(nparam);
 283
 284     /* S = scanning list of polyhedra */
 285     S = Polyhedron_Scan(P, C, MaxRays & POL_NO_DUAL ? 0 : MaxRays);
 286
 287     check_poly_init(C, &options->verify);
 288
 289     /******* CHECK NOW *********/
 290     if (S) {
 291         if (!options->series || options->function) {
 292             if (!check_poly_EP(S, CS, EP, exist, nparam, 0, p->p,
 293                                 &options->verify))
 294                 res = -1;
 295         } else {
 296             skewed_gen_fun *sgf = new skewed_gen_fun(new gen_fun(gf));
 297             if (!check_poly_gf(S, CS, sgf, exist, nparam, 0, p->p,
 298                                 &options->verify))
 299                 res = -1;
 300             delete sgf;
 301         }
 302     }
 303
 304     if (!options->verify.print_all)
 305         printf( "\n" );
 306
 307     Vector_Free(p);
 308     value_clear(tmp);
 309     Domain_Free(S);
 310     Polyhedron_Free(C);
 311     if (CS)
 312         Domain_Free(CS);
 313 }