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 "sommet.h"
#include "ray_dte.h"
#include "sg.h"
#include "polyedre.h"
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... | |
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.
References b1, b2, base_rm, base_union(), s1, sc_enveloppe_chernikova(), and vect_size().
Referenced by elementary_convex_union().
|
static |
put base variables in set.
returns whether something was put.
Definition at line 217 of file sc_enveloppe.c.
References linear_hashtable_isin(), linear_hashtable_put(), Svecteur::succ, and Svecteur::var.
Referenced by transitive_closure_from_two_bases(), and transitive_closure_pass().
|
static |
returns whether c contains variables of vars.
Definition at line 232 of file sc_enveloppe.c.
References linear_hashtable_isin(), Svecteur::succ, and Svecteur::var.
Referenced by transitive_closure_pass().
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?
s1 | 1 |
s2 | 2 |
Definition at line 171 of file sc_enveloppe.c.
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().
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.
is1 | s1 |
is2 | s2 |
Definition at line 369 of file sc_enveloppe.c.
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().
s1 | 1 |
s2 | 2 |
Definition at line 127 of file sc_enveloppe.c.
References OFL_CTRL, s1, and sc_enveloppe_chernikova_ofl_ctrl().
Referenced by actual_convex_union(), and dependence_cone_positive().
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
calcul de l'enveloppe convexe
printf("systeme final \n"); sc_dump(s);
mem_spy_end("sc_enveloppe_chernikova_ofl_ctrl");
s1 | 1 |
s2 | 2 |
ofl_ctrl | fl_ctrl |
Definition at line 68 of file sc_enveloppe.c.
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().
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 ...
sc | c |
pb | b |
Definition at line 456 of file sc_enveloppe.c.
References CATCH, overflow_error, TRY, and UNCATCH.
Referenced by do_array_expansion(), do_solve_hardware_constraints_on_nb_proc(), and rectangularization_region().
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.
References b1, b2, base_to_set(), linear_hashtable_free(), linear_hashtable_make(), and transitive_closure_system().
Referenced by sc_cute_convex_hull().
|
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.
References base_to_set(), contains_variables(), CONTRAINTE_UNDEFINED, cp, Scontrainte::succ, Svecteur::succ, and Scontrainte::vecteur.
Referenced by transitive_closure_system().
|
static |
transtitive extraction of constraints.
Definition at line 273 of file sc_enveloppe.c.
References CONTRAINTE_UNDEFINED, Ssysteme::egalites, Ssysteme::inegalites, sc_fix(), sc_make(), and transitive_closure_pass().
Referenced by transitive_closure_from_two_bases().