vector_partition_chambers.c

   1 #include <barvinok/options.h>
   2 #include "argp.h"
   3 #include "progname.h"
   4 #include "param_util.h"
   5
   6 /* This program computes the full-dimensional chambers of the vector
   7  * partition function
   8  *
   9  *                      A \lambda = u
  10  *
  11  * The input is the matrix A in PolyLib notation.
  12  * The output consists of the number of chambers, followed by
  13  * a constraint description of each chamber in PolyLib notation.
  14  *
  15  * Example run:
  16  *
  17  *      $ cat elke
  18  *      2 4
  19  *
  20  *      1 1 1 1
  21  *      0 1 2 3
  22  *
  23  *      $ ./vector_partition_chambers < elke
  24  *      3
  25  *
  26  *      3 4
  27  *         1    1   -1    0
  28  *         1    0    1    0
  29  *         1    0    0    1
  30  *
  31  *      3 4
  32  *         1   -1    1    0
  33  *         1    2   -1    0
  34  *         1    0    0    1
  35  *
  36  *      3 4
  37  *         1    3   -1    0
  38  *         1   -2    1    0
  39  *         1    0    0    1
  40  */
  41
  42 static Polyhedron *partition2polyhedron(Matrix *A,
  43                                         struct barvinok_options *options)
  44 {
  45         int i;
  46         unsigned nvar, nparam;
  47         Matrix *M;
  48         Polyhedron *P;
  49
  50         nvar = A->NbColumns;
  51         nparam = A->NbRows;
  52
  53         M = Matrix_Alloc(nvar + nparam, 1 + nvar + nparam + 1);
  54         assert(M);
  55
  56         for (i = 0; i < nparam; ++i) {
  57                 Vector_Copy(A->p[i], M->p[i] + 1, nvar);
  58                 value_set_si(M->p[i][1 + nvar + i], -1);
  59         }
  60         for (i = 0; i < nvar; ++i) {
  61                 value_set_si(M->p[nparam + i][0], 1);
  62                 value_set_si(M->p[nparam + i][1 + i], 1);
  63         }
  64
  65         P = Constraints2Polyhedron(M, options->MaxRays);
  66         Matrix_Free(M);
  67
  68         return P;
  69 }
  70
  71 int main(int argc, char **argv)
  72 {
  73         int nchamber;
  74         unsigned nparam;
  75         Matrix *A;
  76         Polyhedron *P, *C;
  77         Param_Polyhedron *PP;
  78         Param_Domain *PD;
  79         struct barvinok_options *options = barvinok_options_new_with_defaults();
  80
  81         set_program_name(argv[0]);
  82         argp_parse(&barvinok_argp, argc, argv, 0, 0, options);
  83
  84         A = Matrix_Read();
  85         assert(A);
  86
  87         nparam = A->NbRows;
  88         C = Universe_Polyhedron(nparam);
  89         P = partition2polyhedron(A, options);
  90         Matrix_Free(A);
  91
  92         PP = Polyhedron2Param_Polyhedron(P, C, options);
  93         Polyhedron_Free(P);
  94         Polyhedron_Free(C);
  95
  96         nchamber = 0;
  97         for (PD = PP->D; PD; PD = PD->next)
  98                 nchamber++;
  99
 100         printf("%d\n", nchamber);
 101         for (PD = PP->D; PD; PD = PD->next) {
 102                 printf("\n");
 103                 Polyhedron_PrintConstraints(stdout, P_VALUE_FMT, PD->Domain);
 104         }
 105         Param_Polyhedron_Free(PP);
 106
 107         barvinok_options_free(options);
 108         return 0;
 109 }