1 /******************************************************************************
2 * PIP : Parametric Integer Programming *
3 ******************************************************************************
5 ******************************************************************************
7 * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002 *
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 *
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 *
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 *
23 * Written by Cedric Bastoul *
25 ******************************************************************************/
27 /* Premiere version du 18 septembre 2002. */
31 #if defined(__cplusplus)
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
42 #if defined(LINEAR_VALUE_IS_LONGLONG)
43 # define Entier long long
44 # define FORMAT "%lld"
47 #elif defined(LINEAR_VALUE_IS_INT)
48 # define Entier long int
52 #elif defined(LINEAR_VALUE_IS_MP)
58 # include <piplib/type.h>
59 # include <piplib/sol.h>
60 # include <piplib/tab.h>
61 # include <piplib/funcall.h>
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
72 { unsigned NbRows
, NbColumns
;
76 typedef struct pipmatrix PipMatrix
;
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].
84 { int nb_elements
; /* Nombre d'elements du vecteur. */
85 Entier
* the_vector
; /* Numerateurs du vecteur. */
86 Entier
* the_deno
; /* Denominateurs du vecteur. */
88 typedef struct pipvector PipVector
;
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.
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. */
102 typedef struct pipnewparm PipNewparm
;
105 /* Structure PipList :
106 * Liste chainee de Vector.
109 { PipVector
* vector
; /* Le vector contenant la partie de solution. */
110 struct piplist
* next
; /* Pointeur vers l'element suivant. */
112 typedef struct piplist PipList
;
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).
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. */
129 typedef struct pipquast PipQuast
;
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) ;
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
*) ;
148 /* Prototypes des fonctions d'acquisition de matrices de contraintes.*/
149 PipMatrix
* pip_matrix_alloc(unsigned, unsigned) ;
150 PipMatrix
* pip_matrix_read(FILE *) ;
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 :
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,
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.
167 PipQuast
* pip_solve(PipMatrix
*, PipMatrix
*, int, int, int, int, int) ;
169 /* Ced : ajouts specifiques a la PipLib pour funcall. */
170 Tableau
* tab_Matrix2Tableau(PipMatrix
*, int, int, int) ;
171 PipQuast
* sol_quast_edit(int *, PipQuast
*) ;
173 #if defined(__cplusplus)
176 #endif /* define PIPLIB_H */