include/piplib/piplib.h

   1 /******************************************************************************
   2  *                     PIP : Parametric Integer Programming                   *
   3  ******************************************************************************
   4  *                                 piplib.h                                   *
   5  ******************************************************************************
   6  *                                                                            *
   7  * Copyright Paul Feautrier, 1988-2005                                        *
   8  *                                                                            *
   9  * This library is free software; you can redistribute it and/or modify it    *
  10  * under the terms of the GNU Lesser General Public License as published by   *
  11  * the Free Software Foundation; either version 2.1 of the License, or (at    *
  12  * your option) any later version.                                            *
  13  *                                                                            *
  14  * This software is distributed in the hope that it will be useful, but       *
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
  16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
  17  * for more details.                                                          *
  18  *                                                                            *
  19  * You should have received a copy of the GNU Lesser General Public License   *
  20  * along with this library; if not, write to the Free Software Foundation,    *
  21  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA         *
  22  *                                                                            *
  23  * Written by Cedric Bastoul                                                  *
  24  *                                                                            *
  25  ******************************************************************************/
  26
  27 #include <stdio.h>
  28
  29 /* Premiere version du 18 septembre 2002. */
  30
  31 #if !defined(LINEAR_VALUE_IS_LONGLONG) && !defined(LINEAR_VALUE_IS_INT)
  32 #if !defined(LINEAR_VALUE_IS_MP)
  33 # error Please define LINEAR_VALUE_IS_* or #include polylib32.h or polylib64.h
  34 #endif
  35 #endif
  36
  37 #if defined(LINEAR_VALUE_IS_LONGLONG)
  38
  39 # define Entier   long long
  40 # define FORMAT   "%lld"
  41 # define VAL_UN   1LL
  42 # define VAL_ZERO 0LL
  43
  44 #define ENTIER_TO_INT(val) ((int)(val))
  45 #define ENTIER_TO_DOUBLE(val) ((double)(val))
  46
  47 #elif defined(LINEAR_VALUE_IS_INT)
  48
  49 # define Entier   long int
  50 # define FORMAT   "%ld"
  51 # define VAL_UN   1L
  52 # define VAL_ZERO 0L
  53
  54 #define ENTIER_TO_INT(val) ((int)(val))
  55 #define ENTIER_TO_DOUBLE(val) ((double)(val))
  56
  57 #elif defined(LINEAR_VALUE_IS_MP)
  58
  59 # include <gmp.h>
  60 # define Entier   mpz_t
  61 # define FORMAT   "%d"
  62 # define GMP_INPUT_FORMAT   "%lZd"
  63
  64 #define ENTIER_TO_INT(val) ((int)mpz_get_si(val))
  65 #define ENTIER_TO_DOUBLE(val) (mpz_get_d(val))
  66
  67 #endif
  68
  69 #if defined(LINEAR_VALUE_IS_MP)
  70
  71 #define entier_addto(ref,val1,val2)     (mpz_add((ref),(val1),(val2)))
  72 #define entier_increment(ref,val)       (mpz_add_ui((ref),(val),1))
  73 #define entier_assign(v1,v2)            (mpz_set((v1),(v2)))
  74 #define entier_clear(val)               (mpz_clear((val)))
  75 #define entier_divexact(d,v1,v2)        (mpz_divexact((d),(v1),(v2)))
  76 #define entier_gcd(g,v1,v2)             (mpz_gcd((g),(v1),(v2)))
  77 #define entier_init(val)                (mpz_init((val)))
  78 #define entier_init_zero(val)           (mpz_init((val)))
  79 #define entier_init_set(v1,v2)          (mpz_init_set((v1),(v2)))
  80 #define entier_pdivision(ref,val1,val2) (mpz_fdiv_q((ref),(val1),(val2)))
  81 #define entier_pmodulus(ref,val1,val2)  (mpz_fdiv_r((ref),(val1),(val2)))
  82 #define entier_oppose(ref,val)          (mpz_neg((ref),(val)))
  83 #define entier_set_si(val,i)            (mpz_set_si((val),(i)))
  84 #define entier_subtract(ref,val1,val2)  (mpz_sub((ref),(val1),(val2)))
  85 #define entier_decrement(ref,val)       (mpz_sub_ui((ref),(val),1))
  86 #define entier_sgn(val)                 (mpz_sgn(val))
  87 #define entier_eq(v1,v2)                (mpz_cmp((v1),(v2)) == 0)
  88 #define entier_ne(v1,v2)                (mpz_cmp((v1),(v2)) != 0)
  89 #define entier_one_p(val)               (mpz_cmp_si(val,1) == 0)
  90 #define entier_llog(val)                (mpz_sizeinbase(val, 2))
  91
  92 #else
  93
  94 #define entier_addto(ref,val1,val2)     ((ref) = (val1)+(val2))
  95 #define entier_increment(ref,val)       ((ref) = (val)+1)
  96 #define entier_assign(v1,v2)            ((v1) = (v2))
  97 #define entier_clear(val)               do { } while(0)
  98 #define entier_divexact(d,v1,v2)        ((d) = (v1) / (v2))
  99 #define entier_gcd(g,v1,v2)             ((g) = pgcd((v1),(v2)))
 100 #define entier_init(val)                do { } while(0)
 101 #define entier_init_zero(v1)            ((v1) = 0)
 102 #define entier_init_set(v1,v2)          ((v1) = (v2))
 103 #define entier_pdivision(ref,val1,val2) ((ref) = ((val1)-mod((val1),(val2)))/(val2))
 104 #define entier_pmodulus(ref,val1,val2)  ((ref) = mod((val1),(val2)))
 105 #define entier_oppose(ref,val)          ((ref) = -(val))
 106 #define entier_set_si(val,i)            ((val) = (Entier)(i))
 107 #define entier_subtract(ref,val1,val2)  ((ref) = (val1)-(val2))
 108 #define entier_decrement(ref,val)       ((ref) = (val)-1)
 109 #define entier_sgn(val)                 (val)
 110 #define entier_eq(v1,v2)                ((v1) == (v2))
 111 #define entier_ne(v1,v2)                ((v1) != (v2))
 112 #define entier_one_p(val)               ((val) == 1)
 113 #define entier_llog(val)                (llog(val))
 114
 115 #endif
 116
 117 #define entier_zero_p(val)              (entier_sgn(val) == 0)
 118 #define entier_notzero_p(val)           (entier_sgn(val) != 0)
 119 #define entier_pos_p(val)               (entier_sgn(val) > 0)
 120
 121 #ifndef PIPLIB_H
 122 #define PIPLIB_H
 123 #if defined(__cplusplus)
 124 extern "C"
 125   {
 126 #endif
 127
 128
 129 /* Structure PipMatrix :
 130  * Structure de matrice au format PolyLib. Le premier element d'une ligne
 131  * indique quand il vaut 1 que la ligne decrit une inequation de la forme
 132  * p(x)>=0 et quand il vaut 0, que la ligne decrit une egalite de la forme
 133  * p(x)=0. Le dernier element de chaque ligne correspond au coefficient
 134  * constant.
 135  */
 136 struct pipmatrix
 137 { unsigned NbRows, NbColumns ;
 138   Entier **p ;
 139   Entier *p_Init ;
 140   int p_Init_size;              /* Only for PolyLib compatibility under MP
 141                                  * version: PolyLib makes sometimes
 142                                  * overestimates on the size of the matrices,
 143                                  * in order to go faster. Thus
 144                                  * NbRows*NbColumns is not the number of
 145                                  * allocated elements. With MP version, we
 146                                  * have to think to mpz_clear() all the
 147                                  * initialized elements before freing, then
 148                                  * we need to know the number of allocated
 149                                  * elements: p_Init_size.
 150                                  */
 151 } ;
 152 typedef struct pipmatrix PipMatrix ;
 153
 154
 155 /* Structure PipVector :
 156  * Cette structure contient un Vector de 'nb_elements' la ieme composante de
 157  * ce vecteur vaut the_vector[i]/the_deno[i].
 158  */
 159 struct pipvector
 160 { int nb_elements ;             /* Nombre d'elements du vecteur. */
 161   Entier * the_vector ;         /* Numerateurs du vecteur. */
 162   Entier * the_deno ;           /* Denominateurs du vecteur. */
 163 } ;
 164 typedef struct pipvector PipVector ;
 165
 166
 167 /* Structure PipNewparm :
 168  * Liste chainee de Newparm, les informations d'un newparm etant son rang, un
 169  * vecteur de coefficients et un denominateur. Le newparm est egal a la division
 170  * du vecteur par le denominateur.
 171  */
 172 struct pipnewparm
 173 { int rank ;                    /* Rang du 'newparm'. */
 174   PipVector * vector ;          /* Le vector decrivant le newparm. */
 175   Entier deno ;                 /* Denominateur du 'newparm'. */
 176   struct pipnewparm * next ;    /* Pointeur vers le newparm suivant. */
 177 } ;
 178 typedef struct pipnewparm PipNewparm ;
 179
 180
 181 /* Structure PipList :
 182  * Liste chainee de Vector.
 183  */
 184 struct piplist
 185 { PipVector * vector ;          /* Le vector contenant la partie de solution. */
 186   struct piplist * next ;       /* Pointeur vers l'element suivant. */
 187 } ;
 188 typedef struct piplist PipList ;
 189
 190
 191 /* Structure pipquast :
 192  * Arbre binaire. Conformement a la grammaire de sortie (voir mode d'emploi), un
 193  * noeud de l'arbre des solutions debute par une liste de 'newparm'. Il continue
 194  * ensuite soit par une 'list' (alors condition vaut null), soit par un 'if'
 195  * (alors le champ condition contient la condition).
 196  */
 197 struct pipquast
 198 { PipNewparm * newparm ;        /* Les 'newparm'. */
 199   PipList * list ;              /* La 'list' si pas de 'if'. */
 200   PipVector * condition ;       /* La condition si 'if'. */
 201   struct pipquast * next_then ; /* Noeud si condition et si verifiee. */
 202   struct pipquast * next_else ; /* Noeud si condition et si non verifiee. */
 203   struct pipquast * father ;    /* Pointeur vers le quast pere. */
 204 } ;
 205 typedef struct pipquast PipQuast ;
 206
 207
 208 /* Structure pipoptions:
 209  * This structure contains each option that can be set to change the PIP
 210  * behaviour.
 211  */
 212 struct pipoptions
 213 { int Nq ;                      /* 1 if an integer solution is needed,
 214                                  * 0 otherwise.
 215                                  */
 216   int Verbose ;                 /* -1 -> absolute silence,
 217                                  *  0 -> relative silence,
 218                                  *  1 -> information on cuts when an integer
 219                                  *       solution is needed,
 220                                  *  2 -> information sur les pivots et les
 221                                  *       déterminants,
 222                                  *  3 -> information on arrays,
 223                                  * Each option include the preceding.
 224                                  */
 225   int Simplify ;                /* Set to 1 to eliminate some trivial
 226                                  * solutions, 0 otherwise.
 227                                  */
 228   int Deepest_cut ;             /* Set to 1 to include deepest cut
 229                                  * algorithm.
 230                                  */
 231   int Maximize;                 /* Set to 1 if maximum is needed. */
 232   int Urs_parms;                /* -1 -> all parameters may be negative
 233                                  *  0 -> all parameters are non-negative
 234                                  */
 235   int Urs_unknowns;             /* -1 -> all unknowns may be negative
 236                                  *  0 -> all unknowns are non-negative
 237                                  */
 238   int Compute_dual;
 239 } ;
 240 typedef struct pipoptions PipOptions ;
 241
 242
 243 /* Prototypes des fonctions d'affichages des structures de la PipLib. */
 244 void pip_matrix_print(FILE *, PipMatrix *) ;
 245 void pip_vector_print(FILE *, PipVector *) ;
 246 void pip_newparm_print(FILE * foo, PipNewparm *, int indent) ;
 247 void pip_list_print(FILE * foo, PipList *, int indent) ;
 248 void pip_quast_print(FILE *, PipQuast *, int) ;
 249
 250
 251 /* Prototypes des fonctions de liberation memoire des structures de la PipLib.*/
 252 void pip_matrix_free(PipMatrix *) ;
 253 void pip_vector_free(PipVector *) ;
 254 void pip_newparm_free(PipNewparm *) ;
 255 void pip_list_free(PipList *) ;
 256 void pip_quast_free(PipQuast *) ;
 257 void pip_options_free(PipOptions *) ;
 258
 259
 260 /* Prototypes des fonctions d'acquisition de matrices de contraintes et
 261  * options.
 262  */
 263 PipMatrix * pip_matrix_alloc(unsigned, unsigned) ;
 264 PipMatrix * pip_matrix_read(FILE *) ;
 265 PipOptions * pip_options_init(void) ;
 266
 267
 268 /* initialization of pip library */
 269 void pip_init();
 270 void pip_close();
 271
 272
 273 /* Prototype de la fonction de resolution :
 274  * pip_solve resoud le probleme qu'on lui passe en parametre, suivant les
 275  * options elles aussi en parametre. Elle renvoie la solution sous forme
 276  * d'un arbre de PipQuast. Parametres :
 277  * - probleme :
 278  * 1 PipMatrix  : systeme des inequations definissant le domaine des inconnues,
 279  * 2 PipMatrix  : systeme des inequations satisfaites par les parametres,
 280  * 3 int        : column rank of the bignum, or negative value if there
 281  *                is no big parameter.
 282  * 4 PipOptions : options for PIP.
 283  */
 284 PipQuast * pip_solve(PipMatrix *, PipMatrix *, int, PipOptions *) ;
 285
 286 #define SOL_SHIFT               (1 << 0)    /* Shift solution over -bigparam */
 287 #define SOL_NEGATE              (1 << 1)    /* Negate solution */
 288 #define SOL_REMOVE              (1 << 2)    /* Remove big parameter */
 289 #define SOL_MAX                 (SOL_SHIFT | SOL_NEGATE)
 290                                             /* Maximum was computed */
 291 #define SOL_DUAL                (1 << 3)    /* Create dual leaf */
 292 PipQuast *sol_quast_edit(int *i, PipQuast *father, int Bg, int Urs_p, int flags);
 293
 294 #if defined(__cplusplus)
 295   }
 296 #endif
 297 #endif /* define PIPLIB_H */