sc-fais-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 "sommet.h"
#include "matrix.h"
#include "plint.h"

Include dependency graph for sc-fais-int.c:

Go to the source code of this file.

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

Functions
bool	sys_int_fais (Psysteme sys1)
	bool sys_int_fais(Psysteme sys1): Test de faisabilite d'un systeme lineaire syst1 en nombres entiers par l'algorithme des congruences decroissantes (cf. More...

Macro Definition Documentation

MALLOC

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

package plint

Definition at line 45 of file sc-fais-int.c.

Function Documentation

sys_int_fais()

bool sys_int_fais

(

Psysteme

sys1

)

bool sys_int_fais(Psysteme sys1): Test de faisabilite d'un systeme lineaire syst1 en nombres entiers par l'algorithme des congruences decroissantes (cf.

livre ???, pp. ??? ). Renvoie true si le systeme est satisfiable (i.e. il definit un polyedre convexe non vide), false sinon.

Ce test est exact, mais il est tres couteux en temps CPU.

Le systeme de contrainte syst1 n'est pas modifie

cas ou le systeme est faisable

Definition at line 57 of file sc-fais-int.c.

{
    Psysteme sys2 = NULL;
    Psommet fonct = fonct_min(sys1->dimension,sys1->base);
    Psolution sol1 = NULL;
 
    bool is_faisable = false;
 
    sys2=sc_dup(sys1);
    /*
     * Recherche d'une solution par l'algorithme des congruences
     * decroissantes a partir d'une fonction economique minimale (
     * recherche du minimum de la premiere variable du systeme)
     */
    if ((sys2 != NULL) && 
        ( (sys2->egalites != NULL) || (sys2->inegalites != NULL))) 
        sys2 = plint(sys2,fonct,&sol1);
    else
        is_faisable = true;
 
    if ((sys2 != NULL) && ((sys2->egalites != NULL)
                           || (sys2->inegalites != NULL)))
        is_faisable = true;
 
    if (is_faisable)
        /* cas ou le systeme est faisable          */
        sc_rm(sys2);
    return (is_faisable);
}

References Ssysteme::egalites, fonct_min(), Ssysteme::inegalites, plint(), sc_dup(), and sc_rm().

Referenced by sys_int_redond().

Here is the call graph for this function:

Here is the caller graph for this function: