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