PIPS
Macros | Functions
sc-res-smith.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "matrix.h"
#include "sommet.h"
#include "plint.h"
+ Include dependency graph for sc-res-smith.c:

Go to the source code of this file.

Macros

#define MALLOC(s, t, f)   malloc((unsigned)(s))
 Package plint (Programmation Lineaire en nombres entiers, i.e. More...
 
#define FREE(s, t, f)   free((char *)(s))
 
#define MATRIX   0
 

Functions

Psysteme sc_resol_smith (Psysteme ps)
 Psysteme sc_resol_smith(Psysteme ps): Resolution d'un systeme d'egalites en nombres entiers par la methode de Smith. More...
 

Macro Definition Documentation

◆ FREE

#define FREE (   s,
  t,
  f 
)    free((char *)(s))

Definition at line 45 of file sc-res-smith.c.

◆ MALLOC

#define MALLOC (   s,
  t,
  f 
)    malloc((unsigned)(s))

Package plint (Programmation Lineaire en nombres entiers, i.e.

INTeger)

Definition at line 44 of file sc-res-smith.c.

◆ MATRIX

#define MATRIX   0

Definition at line 47 of file sc-res-smith.c.

Function Documentation

◆ sc_resol_smith()

Psysteme sc_resol_smith ( Psysteme  ps)

Psysteme sc_resol_smith(Psysteme ps): Resolution d'un systeme d'egalites en nombres entiers par la methode de Smith.

(c.f. Programmation Lineaire. M.MINOUX. (83))

resultat retourne par la fonction :

Psysteme : systeme lineaire dont le systeme d'inequations est
identique a celui du systeme initial. 

    le systeme d'equations est remplace par le systeme 
    d'egalites correspondant a la solution du systeme

d'equations du systeme d'egalites initial.

Les parametres de la fonction :

Psysteme ps : systeme lineaire

Pre-multiplication par la matrice P

ajout des variables non contraintes

Pre-multiplication par la matrice Q

conversion en systeme lineaire

Definition at line 66 of file sc-res-smith.c.

68 {
69 
70  Psysteme sys=sc_dup(ps);
71  int i;
72 
73  Pmatrix MAT= MATRIX_UNDEFINED;
74  Pmatrix P=MATRIX_UNDEFINED;
75  Pmatrix Q=MATRIX_UNDEFINED;
76  Pmatrix B=MATRIX_UNDEFINED;
77  Pmatrix B2=MATRIX_UNDEFINED;
78  Pmatrix D=MATRIX_UNDEFINED;
79 
80  Value den=VALUE_ONE;
81  int nbl;
82  int n;
83  int m;
84  bool infaisab = false;
85  if (ps) {
86  sys = sc_normalize(sc_dup(sys));
87  m = sys->dimension;
88  n = sys->nb_eq;
89 
90  if (m && (n >1) && (sys != NULL)) {
91 
92  MAT = matrix_new(n,m);
93  D = matrix_new(n,m);
94 
95  P = matrix_new(n,n);
96  Q = matrix_new(m,m);
97 
98  B = matrix_new(m,m);
99  B2 = matrix_new(m,m);
100 
101 #ifdef TRACE
102  printf(" systeme lineaire initial \n");
103  sc_fprint (stdout,sys,noms_var);
104 #endif
105 
106  sys_mat_conv(sys,MAT,B,n,m);
107 
108  if (sys->egalites != NULL) contraintes_free(sys->egalites);
109  sys->egalites = NULL;
110 
111  MATRIX_DENOMINATOR(B)=VALUE_ONE;
112  MATRIX_DENOMINATOR(MAT) = VALUE_ONE;
113 
114  matrix_nulle(B2);
115 
116  matrix_smith(MAT,P,D,Q);
117 
118  matrix_assign(D,MAT);
119 
120  /* Pre-multiplication par la matrice P */
121 
122  matrix_multiply(P,B,B2);
123  matrix_assign(B2,B);
124 
125 
126 #ifdef TRACE
127  printf (" apres pre-multiplication par P \n");
128  matrix_print(B);
129  matrix_print(D);
130 #endif
131 
132  nbl = 2;
133  for (i=1;i<=n && i<=m && !infaisab;i++)
134  {
135  /*
136  * Division de chaque terme non nul de B par le
137  terme correspondant de la
138  * diagonale de la matrice D
139  */
140  Value matii=MATRIX_ELEM(MAT,i,i);
141  if (value_notzero_p(matii))
142  if (value_zero_p(value_mod(MATRIX_ELEM(B,i,1), matii)))
143  value_division(MATRIX_ELEM(B,i,1),matii);
144  else infaisab = true;
145 
146  else
147  {
148  /*
149  * Si un terme diagonal est nul, on verifie
150  que la variable correspondante est
151  * bien nulle, i.e. que son coefficient dans
152  B est bien zero et on
153  * ajoute une variable non contrainte au systeme.
154  * En effet, l'equation "0 * x = 0"
155  ==> la variable x est non contrainte
156  */
157  if (value_zero_p(MATRIX_ELEM(B,i,1)))
158  { MATRIX_ELEM(B,i,nbl) = den;
159  nbl++;
160  }
161  else
162  /*
163  * si la variable est non nulle ==> il y a une erreur ==> systeme infaisable
164  */
165  infaisab = true;
166 
167  }
168  }
169 
170 
171  if (infaisab) {
172  matrix_nulle(B);
173  sc_rm(sys);
174  sys = NULL;
175 #ifdef TRACE
176  printf (" systeme infaisable en nombres entiers \n");
177 #endif
178  }
179  else {
180 
181 #ifdef TRACE
182  printf (" apres division par les elements diagonaux de D \n");
183  matrix_print(B);
184 #endif
185 
186  /* ajout des variables non contraintes */
187  if (m>n)
188  for (i=n+1; i<=m; i++,nbl++)
189  MATRIX_ELEM(B,i,nbl) = den;
190  nbl -=2;
191 
192  /* Pre-multiplication par la matrice Q */
193 
194  matrix_multiply(Q,B,B2);
195  matrix_assign(B2,B);
196 #ifdef TRACE
197  printf (" apres pre-multiplication par Q \n");
198  matrix_print(B);
199 #endif
200 
201  matrix_normalizec(B);
202 
203  /* conversion en systeme lineaire */
204 #ifdef TRACE
205  printf (" conversion en systeme lineaire \n");
206 #endif
207  mat_sys_conv(sys,B,m,m,nbl);
208 
209  }
210 
211  FREE(MAT,MATRIX,"smith");
212  FREE(P,MATRIX,"smith");
213  FREE(Q,MATRIX,"smith");
214  FREE(B,MATRIX,"smith");
215  FREE(B2,MATRIX,"smith");
216  }
217 
218  }
219 #ifdef TRACE
220  sc_fprint(stdout,sys,noms_var);
221 #endif
222 
223  return(sys);
224 }
value_notzero_p
#define value_notzero_p(val)
Definition: arithmetique-local.h:391
value_zero_p
#define value_zero_p(val)
Definition: arithmetique-local.h:388
Value
int Value
Definition: arithmetique-local.h:296
value_division
#define value_division(ref, val)
Definition: arithmetique-local.h:365
VALUE_ONE
#define VALUE_ONE
Definition: arithmetique-local.h:303
value_mod
#define value_mod(v1, v2)
Definition: arithmetique-local.h:344
noms_var
char * noms_var(entity e)
comp_expr_to_pnome.c
Definition: comp_expr_to_pnome.c:60
contraintes_free
Pcontrainte contraintes_free(Pcontrainte pc)
Pcontrainte contraintes_free(Pcontrainte pc): desallocation de toutes les contraintes de la liste pc.
Definition: alloc.c:226
B
#define B(A)
Definition: iabrev.h:61
D
#define D(A)
Definition: iabrev.h:56
MATRIX_UNDEFINED
#define MATRIX_UNDEFINED
Definition: matrix-local.h:70
MATRIX_DENOMINATOR
#define MATRIX_DENOMINATOR(matrix)
int MATRIX_DENONIMATOR(matrix): acces au denominateur global d'une matrice matrix
Definition: matrix-local.h:86
MATRIX_ELEM
#define MATRIX_ELEM(matrix, i, j)
Macros d'acces aux elements d'une matrice.
Definition: matrix-local.h:80
matrix_new
Pmatrix matrix_new(int m, int n)
package matrix
Definition: alloc.c:41
matrix_normalizec
void matrix_normalizec(Pmatrix MAT)
void matrix_normalizec(Pmatrix MAT): Normalisation des coefficients de la matrice MAT,...
Definition: matrix.c:187
matrix_nulle
void matrix_nulle(Pmatrix Z)
void matrix_nulle(Pmatrix Z): Initialisation de la matrice Z a la valeur matrice nulle
Definition: matrix.c:293
matrix_multiply
void matrix_multiply(const Pmatrix a, const Pmatrix b, Pmatrix c)
void matrix_multiply(Pmatrix a, Pmatrix b, Pmatrix c): multiply rational matrix a by rational matrix ...
Definition: matrix.c:95
matrix_assign
void matrix_assign(Pmatrix A, Pmatrix B)
void matrix_assign(Pmatrix A, Pmatrix B) Copie de la matrice A dans la matrice B
Definition: matrix.c:259
matrix_print
void matrix_print(Pmatrix)
void matrix_print(matrice a): print an (nxm) rational matrix
Definition: matrix_io.c:70
matrix_smith
void matrix_smith(Pmatrix, Pmatrix, Pmatrix, Pmatrix)
smith.c
Definition: smith.c:68
Q
#define Q
Definition: pip__type.h:39
FREE
#define FREE(s, t, f)
Definition: sc-res-smith.c:45
MATRIX
#define MATRIX
Definition: sc-res-smith.c:47
sc_rm
void sc_rm(Psysteme ps)
void sc_rm(Psysteme ps): liberation de l'espace memoire occupe par le systeme de contraintes ps;
Definition: sc_alloc.c:277
sc_dup
Psysteme sc_dup(Psysteme ps)
Psysteme sc_dup(Psysteme ps): should becomes a link.
Definition: sc_alloc.c:176
sc_fprint
void sc_fprint(FILE *fp, Psysteme ps, get_variable_name_t nom_var)
void sc_fprint(FILE * f, Psysteme ps, char * (*nom_var)()): cette fonction imprime dans le fichier po...
Definition: sc_io.c:220
printf
int printf()
sc_normalize
Psysteme sc_normalize(Psysteme ps)
Psysteme sc_normalize(Psysteme ps): normalisation d'un systeme d'equation et d'inequations lineaires ...
Definition: sc_normalize.c:2152
mat_sys_conv
void mat_sys_conv(Psysteme ps, Pmatrix B, int n, int m, int nbl)
void mat_sys_conv(Psysteme ps, matrice B, int n, int m, int nbl) remplissage du champ des egalites ps...
Definition: sc_to_matrice.c:103
sys_mat_conv
void sys_mat_conv(Psysteme ps, Pmatrix A, Pmatrix B, int n, int m)
package sur les polyedres
Definition: sc_to_matrice.c:65
Pmatrix
package matrice
Definition: matrix-local.h:63
Ssysteme::egalites
Pcontrainte egalites
Definition: sc-local.h:70
Ssysteme::dimension
int dimension
Definition: sc-local.h:74
Ssysteme::nb_eq
int nb_eq
Definition: sc-local.h:72

References B, contraintes_free(), D, Ssysteme::dimension, Ssysteme::egalites, FREE, mat_sys_conv(), MATRIX, matrix_assign(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_multiply(), matrix_new(), matrix_normalizec(), matrix_nulle(), matrix_print(), matrix_smith(), MATRIX_UNDEFINED, Ssysteme::nb_eq, noms_var(), printf(), Q, sc_dup(), sc_fprint(), sc_normalize(), sc_rm(), sys_mat_conv(), value_division, value_mod, value_notzero_p, VALUE_ONE, and value_zero_p.

+ Here is the call graph for this function: