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