PIPS
|
#include <stdio.h>
#include <stdlib.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "matrix.h"
#include "ray_dte.h"
#include "sommet.h"
#include "polyedre.h"
#include "plint.h"
Go to the source code of this file.
Macros | |
#define | MALLOC(s, t, f) malloc((unsigned)(s)) |
package plint More... | |
#define | FREE(s, t, f) free((char *)(s)) |
Functions | |
void | var_posit (Psysteme ps, Pmatrix B, int m, int nbl) |
void var_posit(Psysteme ps, int B[], int m, int nbl): Recherche des inegalites que doivent respecter les variables non contraintes pour que les variables de depart soient positives More... | |
Psysteme | smith_int (Psysteme ps) |
Psysteme smith_int(Psysteme ps): Resolution d'un systeme d'egalites en nombres entiers par la methode de Smith et recherche du systeme lineaire que doit verifier les nouvelles variables non contraintes du systeme pour que les variables de depart soient positives. More... | |
bool | syst_smith (Psysteme ps) |
bool syst_smith(Psysteme ps): Test de faisabilite d'un systeme lineaire en nombres entiers positifs par resolution du systeme par la methode de Smith. More... | |
Definition at line 56 of file sc-fais-int-sm.c.
package plint
pour recuperer les declarations des fonctions de conversion de sc en liste de sommets et reciproquement, bien que ca casse le DAG des types de donnees
Definition at line 55 of file sc-fais-int-sm.c.
Psysteme smith_int(Psysteme ps): Resolution d'un systeme d'egalites en nombres entiers par la methode de Smith et recherche du systeme lineaire que doit verifier les nouvelles variables non contraintes du systeme pour que les variables de depart soient positives.
resultat retourne par la fonction :
Psysteme : le systeme lineaire que doit verifier les
variables non contraintes
Les parametres de la fonction :
Psysteme ps : systeme lineaire
nombre de lignes du systeme
nombre de variables du systeme
nombre d'equations du systeme
nombre de variables du systeme
numero de la ligne et de la colonne correspondant au plus petit entier non nul appartenant a la partie triangulaire superieure de la matrice
Initialisation des parametres
Pre-multiplication par la matrice P
Division de chaque terme non nul de B par le terme correspondant de la diagonale de la matrice D
Si un terme diagonal est nul, on verifie que la variable correspondante est bien nulle, i.e. que son coefficient dans B est bien zero et on ajoute une variable non contrainte au systeme.
En effet, l'equation "0 * x = 0" ==> "la variable x est non contrainte"
si la variable est non nulle ==> il y a une erreur ==> systeme infaisable
ajout des variables non contraintes
Pre-multiplication par la matrice Q
recherche des contraintes lineaires que doivent respecter les variables supplementaires pour que les variables de depart soient positives
Definition at line 140 of file sc-fais-int-sm.c.
References B, contraintes_free(), Ssysteme::dimension, Ssysteme::egalites, FREE, level, MATRIX, matrix_assign(), matrix_col_el(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_identity(), matrix_line_el(), matrix_maj_col(), matrix_maj_line(), matrix_min(), matrix_multiply(), matrix_new(), matrix_normalizec(), matrix_nulle(), matrix_perm_col(), matrix_perm_line(), matrix_print(), 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, value_zero_p, and var_posit().
Referenced by syst_smith().
bool syst_smith(Psysteme ps): Test de faisabilite d'un systeme lineaire en nombres entiers positifs par resolution du systeme par la methode de Smith.
Le resultat n'est pas toujours bon. Il existe des cas ou la fonction ne detecte pas l'infaisabilite du systeme en nombres entiers, mais il sera du moins dans ce cas faisable en nombres reels.
resultat retourne par la fonction :
boolean : true si le systeme lineaire a une solution entiere false si le systeme lineaire n'a pas de solution entiere
Les parametres de la fonction :
Psommet ps : systeme lineaire
resolution du systeme par la methode de Smith et recherche du systeme de contraintes (sys_cond_posit) que doit verifier les variables non contraintes pour que les variables de depart soient positives.
Test de faisabilite du systeme de contraintes obtenu.
Definition at line 422 of file sc-fais-int-sm.c.
References Ssysteme::base, base_dup(), BASE_NULLE, Ssysteme::dimension, printf(), sc_dup(), sc_normalize(), sc_rm(), smith_int(), and var_ecart_sup().
Referenced by plint().
void var_posit(Psysteme ps, int B[], int m, int nbl): Recherche des inegalites que doivent respecter les variables non contraintes pour que les variables de depart soient positives
La matrice B passee en parametres est celle calculee a l'aide de la fonction "matrice_smith"
Les parametres de la fonction :
!Psysteme ps : systeme lineaire d'inegalites int B[] : matrice de dimension (m,m+1) correspondant a la matrice solution du systeme d'egalites du systeme lineaire int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice int nbl : nombre de variables non contraintes ajoutees a la matrice
Definition at line 75 of file sc-fais-int-sm.c.
References assert, B, contrainte_new(), cp, creat_new_var(), MATRIX_DENOMINATOR, MATRIX_ELEM, Svecteur::succ, TCST, VALUE_ONE, value_oppose, value_sign, vect_chg_coeff(), vect_clean(), vect_new(), VECTEUR_NUL, and vecteur_var.
Referenced by smith_int().