sc_elim_redund.c File Reference

#include <stdio.h>
#include <string.h>
#include "arithmetique.h"
#include "boolean.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"

Include dependency graph for sc_elim_redund.c:

Go to the source code of this file.

Functions
Psysteme	sc_inequations_elim_redund (Psysteme ps)
	package sc More...
Psysteme	sc_elim_redund (Psysteme ps)
	Psysteme sc_elim_redund(Psysteme ps): elimination des contraintes lineaires redondantes dans le systeme par test de faisabilite. More...
Psysteme	sc_safe_elim_redund (Psysteme ps)
	Same as above, but the basis is preserved and sc_empty is returned is the system is not feasible. More...

Function Documentation

sc_elim_redund()

Psysteme sc_elim_redund

(

Psysteme

ps

)

Psysteme sc_elim_redund(Psysteme ps): elimination des contraintes lineaires redondantes dans le systeme par test de faisabilite.

Les tests de faisabilite sont appliques sur tout le systeme. L'elimination des redondances est donc totale.

resultat retourne par la fonction :

Psysteme : Le systeme initial est modifie. Il est egal a NULL si le systeme initial est non faisable.

Les parametres de la fonction :

Psysteme ps : systeme lineaire

Definition at line 100 of file sc_elim_redund.c.

{
  Pcontrainte eq;
 
  for (eq = ps->egalites; eq != NULL; eq=eq->succ)
    vect_normalize(eq->vecteur);
 
  ps = sc_kill_db_eg(ps);
 
  if (SC_UNDEFINED_P(ps))
    return ps;
 
  if (!sc_rational_feasibility_ofl_ctrl(ps,OFL_CTRL,true))
  {
    sc_rm(ps);
    return NULL;
  }
 
  ps = sc_inequations_elim_redund(ps);
  return ps;
}

References Ssysteme::egalites, eq, OFL_CTRL, sc_inequations_elim_redund(), sc_kill_db_eg(), sc_rational_feasibility_ofl_ctrl(), sc_rm(), Scontrainte::succ, vect_normalize(), and Scontrainte::vecteur.

Referenced by adg_update_dfg(), sc_build_triang_elim_redund(), sc_safe_elim_redund(), simplify_minmax_contrainte(), and transformer_pattern_fix_point().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_inequations_elim_redund()

Psysteme sc_inequations_elim_redund

(

Psysteme

ps

)

package sc

Psysteme sc_inequations_elim_redund(Psysteme ps):

Elimination des contraintes lineaires redondantes dans le systeme par test de faisabilite. Le polyedre rationnel definit par ps peut etre augmente par cette procedure qui utilise contrainte_reverse() et un test de faisabilite: E(ps) peut etre strictement inclu dans E(ps'). Les sommets rationnels du systeme generateur de ps ne sont pas respectes.

Remarque: il ne faut pas appliquer de normalisation du systeme apres inversion de la contrainte et avant le test de faisabilite en RATIONELS, car l'elimination des redondances n'est alors pas necessairement correcte en entiers.

resultat retourne par la fonction :

Psysteme : Le systeme initial est modifie. Il est egal a NULL si le systeme initial est non faisable.

Les parametres de la fonction :

Psysteme ps : systeme lineaire

Definition at line 63 of file sc_elim_redund.c.

{
  Pcontrainte eq, eq1;
 
  // hmmm... in order to prevent overflows and keep systems simple,
  // there may be some strategy to try to remove bad constraints first?
 
  // hmmm... why choosing "eq" to scan inequalities?
  for (eq = ps->inegalites;eq != NULL; eq = eq1) {
    eq1 = eq->succ;
    contrainte_reverse(eq);
    if (sc_rational_feasibility_ofl_ctrl(ps, OFL_CTRL,true))
            contrainte_reverse(eq);
    else  {
            eq_set_vect_nul(eq);
            sc_rm_empty_constraints(ps,0);
    }
  }
  return ps;
}

References contrainte_reverse(), eq, eq_set_vect_nul(), Ssysteme::inegalites, OFL_CTRL, sc_rational_feasibility_ofl_ctrl(), sc_rm_empty_constraints(), and Scontrainte::succ.

Referenced by sc_elim_redund().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_safe_elim_redund()

Psysteme sc_safe_elim_redund

(

Psysteme

ps

)

Same as above, but the basis is preserved and sc_empty is returned is the system is not feasible.

ps is assumed to be a consistent system of constraints.

if (SC_UNDEFINED_P(ps)) return(ps);

Definition at line 125 of file sc_elim_redund.c.

{
  Pbase b = base_copy(sc_base(ps));
 
  /* if (SC_UNDEFINED_P(ps)) return(ps); */
 
  ps = sc_elim_redund(ps);
 
  if(ps==NULL) {
    ps = sc_empty(b);
  }
  else {
    base_rm(b);
  }
 
  return ps;
}

References base_copy(), base_rm, sc_elim_redund(), and sc_empty().

Referenced by region_to_statement(), and transformer_normalize().

Here is the call graph for this function:

Here is the caller graph for this function: