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