sc-red-int.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-red-int.c:

Go to the source code of this file.

Macros
#define	MALLOC(s, t, f)   malloc(s)
	package plint More...

Functions
Psysteme	sys_int_redond (Psysteme sys)
	Psysteme sys_int_redond(Psysteme sys): elimination des contraintes lineaires redondantes d'un systeme lineaire en nombres entiers par tests de faisabilite exacts. More...

Macro Definition Documentation

MALLOC

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

package plint

Definition at line 44 of file sc-red-int.c.

Function Documentation

sys_int_redond()

Psysteme sys_int_redond

(

Psysteme

sys

)

Psysteme sys_int_redond(Psysteme sys): elimination des contraintes lineaires redondantes d'un systeme lineaire en nombres entiers par tests de faisabilite exacts.

Chaque inegalite est inversee tour a tour, et la faisabilite de chacun des systemes ainsi obtenus est teste par sys_int_fais(), l'algorithme des congruences decroissantes.

inversion du sens de l'inegalite par multiplication

par -1 du coefficient de chaque variable

test de faisabilite avec la nouvelle inegalite

si le systeme est non faisable ==> inegalite redondante ==> elimination de cette inegalite

Definition at line 53 of file sc-red-int.c.

{
 
    Pcontrainte eq,eq1;
 
    sys = sc_normalize(sc_dup(sys));
    if (sys && (sys->nb_ineq <= NB_INEQ_MAX2) && sys_int_fais(sys) && 
        sys != NULL) {
        for (eq = sys->inegalites;
             eq != NULL && sys->nb_ineq > 1;
             eq = eq1)
        {
            eq1 = eq->succ;
            /* inversion du sens de l'inegalite par multiplication */
            /* par -1 du coefficient de chaque variable            */
            vect_chg_sgn(eq->vecteur);
            vect_add_elem(&(eq->vecteur),TCST,VALUE_ONE);
            /* test de faisabilite avec la nouvelle inegalite      */
            if (sys_int_fais(sys) == false)
            {
                /* si le systeme est non faisable 
                   ==> inegalite redondante
                   ==> elimination de cette inegalite         */
                eq_set_vect_nul (eq);
                sc_rm_empty_constraints(sys,0);
            }
            else
            {
                vect_add_elem (&(eq->vecteur),TCST,VALUE_MONE);
                vect_chg_sgn(eq->vecteur);
            }
        }
    }
    return (sys);
}

References eq, eq_set_vect_nul(), sc_dup(), sc_normalize(), sc_rm_empty_constraints(), Scontrainte::succ, sys_int_fais(), TCST, VALUE_MONE, VALUE_ONE, vect_add_elem(), vect_chg_sgn(), and Scontrainte::vecteur.

Here is the call graph for this function: