sc_enveloppe.c File Reference

#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 "sommet.h"
#include "ray_dte.h"
#include "sg.h"
#include "polyedre.h"

Include dependency graph for sc_enveloppe.c:

Go to the source code of this file.

Functions
Psysteme	sc_enveloppe_chernikova_ofl_ctrl (Psysteme s1, Psysteme s2, int ofl_ctrl)
	package polyedre: enveloppe convexe de deux systemes lineaires More...
Psysteme	sc_enveloppe_chernikova (Psysteme s1, Psysteme s2)
static Psysteme	actual_convex_union (Psysteme s1, Psysteme s2)
	call chernikova with compatible base. More...
Psysteme	elementary_convex_union (Psysteme s1, Psysteme s2)
	implements FC basic idea of simple fast cases... More...
static bool	base_to_set (linear_hashtable_pt s, Pvecteur b)
	put base variables in set. More...
static bool	contains_variables (Pvecteur v, linear_hashtable_pt vars)
	returns whether c contains variables of vars. More...
static bool	transitive_closure_pass (Pcontrainte *pc, Pcontrainte *ex, linear_hashtable_pt vars)
	one pass only of transitive closure. More...
static Psysteme	transitive_closure_system (Psysteme s, linear_hashtable_pt vars)
	transtitive extraction of constraints. More...
static Psysteme	transitive_closure_from_two_bases (Psysteme s, Pbase b1, Pbase b2)
	returns constraints from s which may depend on variables in b1 and b2. More...
Psysteme	sc_cute_convex_hull (Psysteme is1, Psysteme is2)
	returns s1 v s2. More...
Psysteme	sc_rectangular_hull (Psysteme sc, Pbase pb)
	take the rectangular bounding box of the systeme sc, by projecting each constraint of the systeme against each of the basis in pb More...

Function Documentation

actual_convex_union()

static Psysteme actual_convex_union ( Psysteme  s1, Psysteme  s2  )

static

call chernikova with compatible base.

same common base!

call chernikova directly. sc_common_projection_convex_hull improvements have already been included.

restaure initial base

Definition at line 134 of file sc_enveloppe.c.

{
  Psysteme s;
 
  /* same common base! */
  Pbase b1 = sc_base(s1), b2 = sc_base(s2), bu = base_union(b1, b2);
  int d1 = sc_dimension(s1), d2 = sc_dimension(s2), du = vect_size(bu);
 
  sc_base(s1) = bu;
  sc_dimension(s1) = du;
  sc_base(s2) = bu;
  sc_dimension(s2) = du;
 
  /* call chernikova directly.
     sc_common_projection_convex_hull improvements have already been included.
  */
  s = sc_enveloppe_chernikova(s1, s2);
 
  /* restaure initial base */
  sc_base(s1) = b1;
  sc_dimension(s1) = d1;
  sc_base(s2) = b2;
  sc_dimension(s2) = d2;
 
  base_rm(bu);
 
  return s;
}

References b1, b2, base_rm, base_union(), s1, sc_enveloppe_chernikova(), and vect_size().

Referenced by elementary_convex_union().

Here is the call graph for this function:

Here is the caller graph for this function:

base_to_set()

static bool base_to_set ( linear_hashtable_pt  s, Pvecteur  b  )

static

put base variables in set.

returns whether something was put.

Definition at line 217 of file sc_enveloppe.c.

{
  bool modified = false;
 
  for (; b; b=b->succ)
    if (b->var && !linear_hashtable_isin(s, b->var)) 
    {
      linear_hashtable_put(s, b->var, b->var);
      modified = true;
    }
 
  return modified;
}

References linear_hashtable_isin(), linear_hashtable_put(), Svecteur::succ, and Svecteur::var.

Referenced by transitive_closure_from_two_bases(), and transitive_closure_pass().

Here is the call graph for this function:

Here is the caller graph for this function:

contains_variables()

static bool contains_variables ( Pvecteur  v, linear_hashtable_pt  vars  )

static

returns whether c contains variables of vars.

Definition at line 232 of file sc_enveloppe.c.

{
  for (; v; v = v->succ)
    if (v->var && linear_hashtable_isin(vars, v->var))
      return true;
  return false;
}

References linear_hashtable_isin(), Svecteur::succ, and Svecteur::var.

Referenced by transitive_closure_pass().

Here is the call graph for this function:

Here is the caller graph for this function:

elementary_convex_union()

Psysteme elementary_convex_union	(	Psysteme	s1,
		Psysteme	s2
	)

implements FC basic idea of simple fast cases...

returns s1 v s2. s1 and s2 are not touched. The bases should be minimum for best efficiency! otherwise useless columns are allocated and computed. a common base is rebuilt in actual_convex_union. other fast cases may be added?

Parameters

s1	1
s2	2

Definition at line 171 of file sc_enveloppe.c.

{
  bool
    b1 = sc_empty_p(s1),
    b2 = sc_empty_p(s2);
    
  if (b1 && b2)
    return sc_empty(base_union(sc_base(s1), sc_base(s2)));
 
  if (b1) {
    Psysteme s = sc_dup(s2);
    Pbase b = base_union(sc_base(s1), sc_base(s2));
    base_rm(sc_base(s));
    sc_base(s) = b;
    return s;
  }
  
  if (b2) {
    Psysteme s = sc_dup(s1);
    Pbase b = base_union(sc_base(s1), sc_base(s2));
    base_rm(sc_base(s));
    sc_base(s) = b;
    return s;
  }
  
  if (sc_rn_p(s1) || sc_rn_p(s2) || 
      !vect_common_variables_p(sc_base(s1), sc_base(s2)))
    return sc_rn(base_union(sc_base(s1), sc_base(s2)));
 
  /*
  if (sc_dimension(s1)==1 && sc_dimension(s2)==1 && 
      sc_base(s1)->var == sc_base(s2)->var)
  {
    // fast computation...
  }
  */
 
  return actual_convex_union(s1, s2);
}

References actual_convex_union(), b1, b2, base_rm, base_union(), s1, sc_dup(), sc_empty(), sc_empty_p(), sc_rn(), sc_rn_p(), and vect_common_variables_p().

Referenced by sc_cute_convex_hull().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_cute_convex_hull()

Psysteme sc_cute_convex_hull	(	Psysteme	is1,
		Psysteme	is2
	)

returns s1 v s2.

initial systems are not changed.

v convex union u union n intersection T orthogonality

(1) CA:

P1 v P2 = (P n X1) v (P n X2) = let P = P' n P'' so that P' T X1 and P' T X2 and P' T P'' built by transitive closure, then P1 v P2 = (P' n (P'' n X1)) v (P' n (P'' n X2)) = P' n ((P'' n X1) v (P'' n X2))

Proof by considering generating systems: Def: A T B <=> var(A) n var(B) = 0 Prop: A n B if A T B Let A = (x,v,l), B = (y,w,m) A n B = { z | z = (x) \mu + (v) d + (l) e + (0) f (0) + (0) + (0) (I) and z = (0) \nu + (0) g + (0) h + (I) f' (y) + (w) + (m) (0) with \mu>0, \nu>0, \sum\mu=1, \sum\nu=1, d>0, g>0 } we can always find f and f' equals to the other part (by extension) so A n B = { z | z = (x 0) \mu + (v 0) d + (l 0) e (0 y) \nu (0 w) g (0 m) h with \mu \nu d g constraints... } It is a convex : ((xi) , (v 0), (l 0)) (yj)ij, (0 w), (0 m) we just need to prove that Cmn == Cg defined as (x 0) \mu == (xi) \gamma with >0 and \sum = 1 (0 y) \nu (yj)ij . Cg in a convex. . Cg \in Cmn since ((xi)(yj) ij) in Cmn with \mu = \delta i, \nu = \delta j . Cmn \in Cg by chosing \gamma_ij = \mu_i\nu_j, which >0 and \sum = 1 Prop: A T B and A T C => A T (B v C) and A T (B n C) Theo: A T B and A T C => (A n B) v (A n C) = A n (B v C) compute both generating systems with above props. they are equal.

(2) FI:

perform exact projections of common equalities. no proof at the time. It looks ok anyway.

(3) FC:

base(P) n base(Q) = 0 => P u Q = Rn and some other very basic simplifications... which are not really interesting if no decomposition is performed?

on overflows FI suggested.

1/ we want to compute : (A n B1) u (A n B2) 2/ we chose to approximate it as : (A n B1) v (A n B2) 3/ we try Corinne's factorization with transitive closure A' n ((A'' n B1) v (A'' n B2)) 4/ on overflow, we can try A n (B1 v B2) // NOT IMPLEMENTED YET 5/ if we have one more overflow, then A looks good as an approximation.

CA: extract common disjoint part.

FI: in sc_common_projection_convex_hull note that equalities are not that big a burden to chernikova?

fast sc_append

usually we use V (convex hull) as a U (set union) approximation. as we have : (A n B1) U (A n B2) \in A the common part of both systems is an approximation of the union! sc_rn is returned on overflows (and some other case). I don't think that the result is improved apart when actual overflow occurs. FC/CA.

dead. either rm or moved as sc.

better compatibility with previous version, as the convex union normalizes the system and removes redundancy, what is not done if part of the system is separated. Other calls may be considered here?

ok, it will look better.

misleading... not really projected. { x==y, y==3 } => { x==3, y==3 }

sc, su: fast union of disjoint.

regenerate the expected base.

Parameters

is1	s1
is2	s2

Definition at line 369 of file sc_enveloppe.c.

{
  Psysteme s1, s2, sc, stc, su, scsaved;
  int current_overflow_count;
 
  s1 = sc_dup(is1);
  s2 = sc_dup(is2);
 
  /* CA: extract common disjoint part.
   */
  sc = extract_common_syst(s1, s2);
  scsaved = sc_dup(sc);
  stc = transitive_closure_from_two_bases(sc, s1->base, s2->base);
 
  /* FI: in sc_common_projection_convex_hull
     note that equalities are not that big a burden to chernikova?
   */
  sc_extract_exact_common_equalities(stc, sc, s1, s2);
 
  /* fast sc_append */
  s1 = sc_fusion(s1, sc_dup(stc));
  sc_fix(s1);
 
  s2 = sc_fusion(s2, stc);
  sc_fix(s2);
 
  stc = NULL;
 
  current_overflow_count = linear_number_of_exception_thrown;
 
  su = elementary_convex_union(s1, s2);
  
  /* usually we use V (convex hull) as a U (set union) approximation.
   * as we have : (A n B1) U (A n B2) \in A
   * the common part of both systems is an approximation of the union!
   * sc_rn is returned on overflows (and some other case).
   * I don't think that the result is improved apart 
   * when actual overflow occurs. FC/CA.
   */
  if (current_overflow_count!=linear_number_of_exception_thrown)
  {
    if (su) sc_rm(su), su = NULL;
    if (sc) sc_rm(sc), sc = NULL;
    sc = scsaved;
  }
  else
  {
    sc_rm(scsaved);
  }
 
  scsaved = NULL; /* dead. either rm or moved as sc. */
  sc_rm(s1); 
  sc_rm(s2);
 
  /* better compatibility with previous version, as the convex union
   * normalizes the system and removes redundancy, what is not done
   * if part of the system is separated. Other calls may be considered here?
   */
  sc_transform_ineg_in_eg(sc); /* ok, it will look better. */
  /* misleading... not really projected. { x==y, y==3 } => { x==3, y==3 } */
  sc_project_very_simple_equalities(sc);
 
  /* sc, su: fast union of disjoint. */
  sc = sc_fusion(sc, su);
 
  /* regenerate the expected base. */
  if (sc) 
  {
    sc_fix(sc);
    if (sc_base(sc)) base_rm(sc_base(sc));
  }
  else
  {
      sc = sc_rn(NULL);
  }
  sc_base(sc) = base_union(sc_base(is1), sc_base(is2));
  sc_dimension(sc) = vect_size(sc_base(sc));
  
  return sc;
}

References Ssysteme::base, base_rm, base_union(), elementary_convex_union(), extract_common_syst(), is2(), linear_number_of_exception_thrown, s1, sc_dup(), sc_fix(), sc_fusion(), sc_rm(), sc_rn(), sc_transform_ineg_in_eg(), transitive_closure_from_two_bases(), and vect_size().

Referenced by cute_convex_union(), do_array_expansion(), and statement_insertion_fix_access().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_enveloppe_chernikova()

Psysteme sc_enveloppe_chernikova	(	Psysteme	s1,
		Psysteme	s2
	)

Parameters

s1	1
s2	2

Definition at line 127 of file sc_enveloppe.c.

{
  return sc_enveloppe_chernikova_ofl_ctrl((s1), (s2), OFL_CTRL);
}

References OFL_CTRL, s1, and sc_enveloppe_chernikova_ofl_ctrl().

Referenced by actual_convex_union(), and dependence_cone_positive().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_enveloppe_chernikova_ofl_ctrl()

Psysteme sc_enveloppe_chernikova_ofl_ctrl	(	Psysteme	s1,
		Psysteme	s2,
		int	ofl_ctrl
	)

package polyedre: enveloppe convexe de deux systemes lineaires

Warning! Do not modify this file that is automatically generated!

Ce module est range dans le package polyedre bien qu'il soit utilisable en n'utilisant que des systemes lineaires (package sc) parce qu'il utilise lui-meme des routines sur les polyedres.

Francois Irigoin, Janvier 1990 Corinne Ancourt, Fabien Coelho from time to time (1999/2000) Psysteme sc_enveloppe_chernikova_ofl_ctrl(Psysteme s1, s2, int ofl_ctrl) input : output : modifies : s1 and s2 are NOT modified. comment : s1 and s2 must have a basis.

s = enveloppe(s1, s2); return s;

calcul d'une representation par systeme lineaire de l'enveloppe convexe des polyedres definis par les systemes lineaires s1 et s2

mem_spy_begin();

calcul de l'enveloppe convexe

printf("systeme final \n"); sc_dump(s);

mem_spy_end("sc_enveloppe_chernikova_ofl_ctrl");

Parameters

s1	1
s2	2
ofl_ctrl	fl_ctrl

Definition at line 68 of file sc_enveloppe.c.

{
  Psysteme s = SC_UNDEFINED;
  volatile bool catch_performed = false;
  /* mem_spy_begin(); */
 
  assert(!SC_UNDEFINED_P(s1) && !SC_UNDEFINED_P(s2));
 
  // yuk
  if (ofl_ctrl == OFL_CTRL)
  {
    ofl_ctrl = FWD_OFL_CTRL;
    catch_performed = true;
    CATCH(overflow_error|timeout_error) {
      //CATCH(overflow_error) {
      /*
       *   PLEASE do not remove this warning.
       *
       *   BC 24/07/95
       */
      fprintf(stderr, "[sc_enveloppe_chernikova_ofl_ctrl] "
              "arithmetic error occured\n" );
      s = sc_rn(base_dup(sc_base(s1)));
      return s;
    }
  }
 
  if (SC_RN_P(s2) || sc_rn_p(s2) || sc_dimension(s2)==0
      || sc_empty_p(s1) || !sc_faisabilite_ofl(s1))
  {
    Psysteme sc2 = sc_dup(s2);
    sc2 = sc_elim_redond(sc2);
    s = SC_UNDEFINED_P(sc2)? sc_empty(base_dup(sc_base(s2))): sc2;
  }
  else
  {
    if (SC_RN_P(s1) ||sc_rn_p(s1) || sc_dimension(s1)==0
        || sc_empty_p(s2) || !sc_faisabilite_ofl(s2))
    {
      Psysteme sc1 = sc_dup(s1);
      sc1 = sc_elim_redond(sc1);
      s = SC_UNDEFINED_P(sc1)? sc_empty(base_dup(sc_base(s1))): sc1;
    }
    else
    {
      /* calcul de l'enveloppe convexe */
      s = sc_convex_hull(s1,s2);
      /* printf("systeme final \n"); sc_dump(s);  */
    }
  }
  if (catch_performed)
    UNCATCH(overflow_error|timeout_error);
  /* mem_spy_end("sc_enveloppe_chernikova_ofl_ctrl"); */
  return s;
}

References assert, base_dup(), CATCH, fprintf(), FWD_OFL_CTRL, OFL_CTRL, overflow_error, s1, sc_convex_hull(), sc_dup(), sc_empty(), sc_empty_p(), sc_rn(), sc_rn_p(), timeout_error, and UNCATCH.

Referenced by sc_enveloppe_chernikova().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_rectangular_hull()

Psysteme sc_rectangular_hull	(	Psysteme	sc,
		Pbase	pb
	)

take the rectangular bounding box of the systeme sc, by projecting each constraint of the systeme against each of the basis in pb

SG: this is basically a renaming of sc_projection_on_variables ...

Parameters

sc	c
pb	b

Definition at line 456 of file sc_enveloppe.c.

                                                    {
    volatile Psysteme rectangular = SC_UNDEFINED;
    rectangular = sc_projection_on_variables(sc,pb,pb);
    CATCH(overflow_error) {
        ;
        // it does not matter if we fail ...
    }
    TRY {
        sc_nredund(&rectangular);
        UNCATCH(overflow_error);
    }
    return rectangular;
}

References CATCH, overflow_error, TRY, and UNCATCH.

Referenced by do_array_expansion(), do_solve_hardware_constraints_on_nb_proc(), and rectangularization_region().

Here is the caller graph for this function:

transitive_closure_from_two_bases()

static Psysteme transitive_closure_from_two_bases ( Psysteme  s, Pbase  b1, Pbase  b2  )

static

returns constraints from s which may depend on variables in b1 and b2.

these constraints are removed from s, hence s is modified.

Definition at line 292 of file sc_enveloppe.c.

{
  Psysteme st;
  linear_hashtable_pt vars = linear_hashtable_make();
 
  base_to_set(vars, b1);
  base_to_set(vars, b2);
  st = transitive_closure_system(s, vars);
  linear_hashtable_free(vars);
 
  return st;
}

References b1, b2, base_to_set(), linear_hashtable_free(), linear_hashtable_make(), and transitive_closure_system().

Referenced by sc_cute_convex_hull().

Here is the call graph for this function:

Here is the caller graph for this function:

transitive_closure_pass()

static bool transitive_closure_pass ( Pcontrainte *  pc, Pcontrainte *  ex, linear_hashtable_pt  vars  )

static

one pass only of transitive closure.

returns whether vars was modified. appends extracted constraints to ex.

Definition at line 245 of file sc_enveloppe.c.

{
  Pcontrainte c, cp, cn;
  bool modified = false;
 
  for (c=*pc, 
         cp = CONTRAINTE_UNDEFINED, 
         cn = c? c->succ: CONTRAINTE_UNDEFINED; 
       c;
       cp = c==cn? cp: c,
         c = cn, 
         cn = c? c->succ: CONTRAINTE_UNDEFINED)
  {
    if (contains_variables(c->vecteur, vars)) 
    {
      modified |= base_to_set(vars, c->vecteur);
      c->succ = *ex, *ex = c;
      if (cp) cp->succ = cn; else *pc = cn;
      c = cn;
    }
  }
 
  return modified;
}

References base_to_set(), contains_variables(), CONTRAINTE_UNDEFINED, cp, Scontrainte::succ, Svecteur::succ, and Scontrainte::vecteur.

Referenced by transitive_closure_system().

Here is the call graph for this function:

Here is the caller graph for this function:

transitive_closure_system()

static Psysteme transitive_closure_system ( Psysteme  s, linear_hashtable_pt  vars  )

static

transtitive extraction of constraints.

Definition at line 273 of file sc_enveloppe.c.

{
  Pcontrainte e = CONTRAINTE_UNDEFINED, i = CONTRAINTE_UNDEFINED;
  bool modified;
 
  do {
    modified = transitive_closure_pass(&s->egalites, &e, vars);
    modified |= transitive_closure_pass(&s->inegalites, &i, vars);
  }
  while (modified);
 
  sc_fix(s);
  return sc_make(e, i);
}

References CONTRAINTE_UNDEFINED, Ssysteme::egalites, Ssysteme::inegalites, sc_fix(), sc_make(), and transitive_closure_pass().

Referenced by transitive_closure_from_two_bases().

Here is the call graph for this function:

Here is the caller graph for this function: