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