include/piplib/piplib.h

   1 /******************************************************************************
   2  *                     PIP : Parametric Integer Programming                   *
   3  ******************************************************************************
   4  *                                 piplib.h                                   *
   5  ******************************************************************************
   6  *                                                                            *
   7  * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002                     *
   8  *                                                                            *
   9  * This is free software; you can redistribute it and/or modify it under the  *
  10  * terms of the GNU General Public License as published by the Free Software  *
  11  * Foundation; either version 2 of the License, or (at your option) any later *
  12  * 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 General Public License along    *
  20  * with software; if not, write to the Free Software Foundation, Inc.,        *
  21  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  22  *                                                                            *
  23  * Written by Cedric Bastoul                                                  *
  24  *                                                                            *
  25  ******************************************************************************/
  26
  27 /* Premiere version du 18 septembre 2002. */
  28
  29 #ifndef PIPLIB_H
  30 #define PIPLIB_H
  31 #if defined(__cplusplus)
  32 extern "C"
  33   {
  34 #endif
  35
  36 #if !defined(LINEAR_VALUE_IS_LONGLONG) && !defined(LINEAR_VALUE_IS_INT)
  37 #if !defined(LINEAR_VALUE_IS_MP)
  38 # error Please define LINEAR_VALUE_IS_* or #include polylib32.h or polylib64.h
  39 #endif
  40 #endif
  41
  42 #if defined(LINEAR_VALUE_IS_LONGLONG)
  43 # define Entier   long long
  44 # define FORMAT   "%lld"
  45 # define VAL_UN   1LL
  46 # define VAL_ZERO 0LL
  47 #elif defined(LINEAR_VALUE_IS_INT)
  48 # define Entier   long int
  49 # define FORMAT   "%ld"
  50 # define VAL_UN   1L
  51 # define VAL_ZERO 0L
  52 #elif defined(LINEAR_VALUE_IS_MP)
  53 # include <gmp.h>
  54 # define Entier   mpz_t
  55 # define FORMAT   "%d"
  56 #endif
  57
  58 # include <piplib/type.h>
  59 # include <piplib/sol.h>
  60 # include <piplib/tab.h>
  61 # include <piplib/funcall.h>
  62
  63
  64 /* Structure PipMatrix :
  65  * Structure de matrice au format PolyLib. Le premier element d'une ligne
  66  * indique quand il vaut 1 que la ligne decrit une inequation de la forme
  67  * p(x)>=0 et quand il vaut 0, que la ligne decrit une egalite de la forme
  68  * p(x)=0. Le dernier element de chaque ligne correspond au coefficient
  69  * constant.
  70  */
  71 struct pipmatrix
  72 { unsigned NbRows, NbColumns ;
  73   Entier **p ;
  74   Entier *p_Init ;
  75 } ;
  76 typedef struct pipmatrix PipMatrix ;
  77
  78
  79 /* Structure PipVector :
  80  * Cette structure contient un Vector de 'nb_elements' la ieme composante de
  81  * ce vecteur vaut the_vector[i]/the_deno[i].
  82  */
  83 struct pipvector
  84 { int nb_elements ;             /* Nombre d'elements du vecteur. */
  85   Entier * the_vector ;         /* Numerateurs du vecteur. */
  86   Entier * the_deno ;           /* Denominateurs du vecteur. */
  87 } ;
  88 typedef struct pipvector PipVector ;
  89
  90
  91 /* Structure PipNewparm :
  92  * Liste chainee de Newparm, les informations d'un newparm etant son rang, un
  93  * vecteur de coefficients et un denominateur. Le newparm est egal a la division
  94  * du vecteur par le denominateur.
  95  */
  96 struct pipnewparm
  97 { int rank ;                    /* Rang du 'newparm'. */
  98   PipVector * vector ;          /* Le vector decrivant le newparm. */
  99   Entier deno ;                 /* Denominateur du 'newparm'. */
 100   struct pipnewparm * next ;    /* Pointeur vers le newparm suivant. */
 101 } ;
 102 typedef struct pipnewparm PipNewparm ;
 103
 104
 105 /* Structure PipList :
 106  * Liste chainee de Vector.
 107  */
 108 struct piplist
 109 { PipVector * vector ;          /* Le vector contenant la partie de solution. */
 110   struct piplist * next ;       /* Pointeur vers l'element suivant. */
 111 } ;
 112 typedef struct piplist PipList ;
 113
 114
 115 /* Structure pipquast :
 116  * Arbre binaire. Conformement a la grammaire de sortie (voir mode d'emploi), un
 117  * noeud de l'arbre des solutions debute par une liste de 'newparm'. Il continue
 118  * ensuite soit par une 'list' (alors condition vaut null), soit par un 'if'
 119  * (alors le champ condition contient la condition).
 120  */
 121 struct pipquast
 122 { PipNewparm * newparm ;        /* Les 'newparm'. */
 123   PipList * list ;              /* La 'list' si pas de 'if'. */
 124   PipVector * condition ;       /* La condition si 'if'. */
 125   struct pipquast * next_then ; /* Noeud si condition et si verifiee. */
 126   struct pipquast * next_else ; /* Noeud si condition et si non verifiee. */
 127   struct pipquast * father ;    /* Pointeur vers le quast pere. */
 128 } ;
 129 typedef struct pipquast PipQuast ;
 130
 131
 132 /* Prototypes des fonctions d'affichages des structures de la PipLib. */
 133 void pip_matrix_print(FILE *, PipMatrix *) ;
 134 void pip_vector_print(FILE *, PipVector *) ;
 135 void pip_newparm_print(FILE * foo, PipNewparm *, int indent) ;
 136 void pip_list_print(FILE * foo, PipList *, int indent) ;
 137 void pip_quast_print(FILE *, PipQuast *, int) ;
 138
 139
 140 /* Prototypes des fonctions de liberation memoire des structures de la PipLib.*/
 141 void pip_matrix_free(PipMatrix *) ;
 142 void pip_vector_free(PipVector *) ;
 143 void pip_newparm_free(PipNewparm *) ;
 144 void pip_list_free(PipList *) ;
 145 void pip_quast_free(PipQuast *) ;
 146
 147
 148 /* Prototypes des fonctions d'acquisition de matrices de contraintes.*/
 149 PipMatrix * pip_matrix_alloc(unsigned, unsigned) ;
 150 PipMatrix * pip_matrix_read(FILE *) ;
 151
 152
 153 /* Prototype de la fonction de resolution :
 154  * pip_solve resoud le probleme qu'on lui passe en parametre, suivant les
 155  * options elles aussi en parametre. Elle renvoie la solution sous forme
 156  * d'un arbre de PipQuast. Parametres :
 157  * - probleme :
 158  * 1 PipMatrix : systeme des inequations definissant le domaine des inconnues,
 159  * 2 PipMatrix : systeme des inequations satisfaites par les parametres,
 160  * 3 int       : Bg le bignum,
 161  * - options :
 162  * 4 int       : Nq pour savoir si on cherche une solution entiere.
 163  * 5 int       : Verbose pour savoir si on veut creer un fichier de tracage.
 164  * 6 int       : Simplify pour demander a Pip de simplifier sa solution.
 165  * 7 int       : Max encore inutilise, doit etre mis a 0.
 166  */
 167 PipQuast * pip_solve(PipMatrix *, PipMatrix *, int, int, int, int, int) ;
 168
 169 /* Ced : ajouts specifiques a la PipLib pour funcall. */
 170 Tableau * tab_Matrix2Tableau(PipMatrix *, int, int, int) ;
 171 PipQuast * sol_quast_edit(int *, PipQuast *) ;
 172
 173 #if defined(__cplusplus)
 174   }
 175 #endif
 176 #endif /* define PIPLIB_H */