PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "linear_assert.h"
#include <time.h>
#include <sys/time.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "sommet.h"
#include "polyedre.h"
#include "union.h"
Go to the source code of this file.
Macros | |
#define | hspara_join(se1, se2) (((se1) >= (se2))?hspara_jm[(se1)][(se2)]:hspara_jm[(se2)][(se1)]) |
#define | hspara_meet(se1, se2) (((se1) <= (se2))?hspara_jm[(se1)][(se2)]:hspara_jm[(se2)][(se1)]) |
#define | hspara_to_string(se) (char*) hspara_string[(int) (se)] |
Functions | |
static char *hspara_string[10] | __attribute__ ((unused)) |
Package : C3/union Author : Arnauld LESERVOT (leservot(a)limeil.cea.fr) Date : Modified : 04 04 95 Documents: UNION.tex : `‘Extension de C3 aux unions de polyedres’' Comments : More... | |
enum hspara_elem | vect_parallel (Pvecteur in_v1, Pvecteur in_v2) |
enum hspara_elem vect_parallel(Pvecteur in_v1, Pvecteur in_v2) AL950711 input: 2 Pvecteur in_v1 and in_v2 output: hspara_elem (element of the parallel half space lattice) memory: Inspector (nothing is shared, nor modified, output allocated). More... | |
enum hspara_elem | contrainte_parallel_in_liste (Pcontrainte in_co, Pcontrainte in_lc) |
enum enum hspara_elem contrainte_parallel_in_liste( in_co, in_lc ) AL950711 input: 1 constraint in_co and a list of constraints in_lc output: hspara_elem (element of the parallel half space lattice) memory: Inspector (nothing is shared, nor modified, output allocated). More... | |
Psysteme | sc_supress_parallel_redund_constraints (Psysteme in_ps1, Psysteme in_ps2) |
Psysteme sc_supress_parallel_redund_constraints( in_ps1, in_ps2 ) input: 2 Psystemes in_ps1 and in_ps2 output: in_ps1 / in_ps2 (cut operation on polyhedrons) memory: Inspector (nothing is shared, nor modified, output allocated). More... | |
Psysteme | sc_supress_same_constraints (Psysteme in_ps1, Psysteme in_ps2) |
Psysteme sc_supress_same_constraints( in_ps1, in_ps2 ) supress in in_ps2 constraints that are in in_ps1. More... | |
Psysteme | sc_elim_redund_with_first_ofl_ctrl (Psysteme in_ps1, Psysteme in_ps2, int ofl_ctrl) |
Psysteme sc_elim_redund_with_first_ofl_ctrl( in_ps1, in_ps2, ofl_ctrl ) Returns constraints of in_ps2 which cut in_ps1. More... | |
Ppath | pa_supress_same_constraints (Ppath in_pa) |
Ppath pa_supress_same_constraints( (Ppath) in_pa ) Supress from complements of in_pa same constraints than those in positif Psystem in_pa->psys. More... | |
Pdisjunct | pa_path_to_disjunct_rule4_ofl_ctrl (Ppath in_pa, int ofl_ctrl) |
Pdisjunct pa_path_to_disjunct_rule4_ofl_ctrl( (Ppath) in_pa, int ofl_ctrl) Returns the corresponding disjunction according rule 4. More... | |
Pdisjunct | pa_path_to_few_disjunct_ofl_ctrl (Ppath in_pa, int ofl_ctrl) |
line 1197 "reduc.w" More... | |
bool | pa_inclusion_p_ofl_ctrl (Psysteme ps1, Psysteme ps2, int ofl_ctrl) |
bool pa_inclusion_p(Psysteme ps1, Psysteme ps2) BA, AL 31/05/94 returns true if ps1 represents a subset of ps2, false otherwise Inspector (no sharing on memory). More... | |
bool | pa_system_equal_p_ofl_ctrl (Psysteme ps1, Psysteme ps2, int ofl_ctrl) |
bool pa_system_equal_p(Psysteme ps1, Psysteme ps2) BA More... | |
Pdisjunct | pa_system_difference_ofl_ctrl (Psysteme ps1, Psysteme ps2, int ofl_ctrl) |
Pdisjunct pa_system_difference_ofl_ctrl(ps1, ps2) input : two Psystemes output : a disjunction representing ps1 - ps2 modifies : nothing comment : algorihtm : chemin = ps1 inter complement of (ps2) ret_dj = dj_simple_inegs_to_eg( pa_path_to_few_disjunct(chemin) ) More... | |
bool | pa_convex_hull_equals_union_p_ofl_ctrl (Psysteme conv_hull, Psysteme ps1, Psysteme ps2, int ofl_ctrl, volatile bool ofl_res) |
bool pa_convex_hull_equals_union_p(conv_hull, ps1, ps2) input : two Psystems and their convex hull AL,BC 23/03/95 output : true if ps1 U ps2 = convex_hull, false otherwise modifies : nothing comment : complexity = nb_constraints(ps1) * nb_constraints(ps2) if ofl_ctrl = OFL_CTRL, conservatively returns ofl_ctrl when an overflow error occurs More... | |
Variables | |
static enum hspara_elem | hspara_jm [10][10] |
#define hspara_to_string | ( | se | ) | (char*) hspara_string[(int) (se)] |
|
static |
Package : C3/union Author : Arnauld LESERVOT (leservot(a)limeil.cea.fr) Date :
Modified : 04 04 95 Documents: UNION.tex : `‘Extension de C3 aux unions de polyedres’' Comments :
WARNING
THOSE FUNCTIONS ARE AUTOMATICALLY DERIVED
FROM THE WEB SOURCES !
Ansi includes
Linear includes
Definition at line 4277 of file bootstrap.c.
References functional_parameters, functional_undefined, is_type_functional, make_functional(), make_parameter_list(), make_type(), MakeOverloadedResult(), MakeVoidParameter(), NIL, and type_undefined.
enum hspara_elem contrainte_parallel_in_liste | ( | Pcontrainte | in_co, |
Pcontrainte | in_lc | ||
) |
enum enum hspara_elem contrainte_parallel_in_liste( in_co, in_lc ) AL950711 input: 1 constraint in_co and a list of constraints in_lc output: hspara_elem (element of the parallel half space lattice) memory: Inspector (nothing is shared, nor modified, output allocated).
complexity: length(in_lc) * comp(vect_parallel()) comment: in_co represents a1 X+b1 <= 0 and in_lc aj X + bj <=0. Returns in_co/in_lc = join_j( vect_parallel( in_co, in_lc_j ) ) between keep, empty and full.
debuging
debuging
in_co | n_co |
in_lc | n_lc |
Definition at line 49 of file reduc.c.
Referenced by sc_supress_parallel_redund_constraints().
bool pa_convex_hull_equals_union_p_ofl_ctrl | ( | Psysteme | conv_hull, |
Psysteme | ps1, | ||
Psysteme | ps2, | ||
int | ofl_ctrl, | ||
volatile bool | ofl_res | ||
) |
bool pa_convex_hull_equals_union_p(conv_hull, ps1, ps2) input : two Psystems and their convex hull AL,BC 23/03/95 output : true if ps1 U ps2 = convex_hull, false otherwise modifies : nothing comment : complexity = nb_constraints(ps1) * nb_constraints(ps2) if ofl_ctrl = OFL_CTRL, conservatively returns ofl_ctrl when an overflow error occurs
conv_hull | onv_hull |
ps1 | s1 |
ps2 | s2 |
ofl_ctrl | fl_ctrl |
ofl_res | fl_res |
Definition at line 937 of file reduc.c.
References CATCH, FWD_OFL_CTRL, OFL_CTRL, overflow_error, pa_feasibility_ofl_ctrl(), pa_free1(), pa_make(), sl_append_system(), TRY, and UNCATCH.
bool pa_inclusion_p(Psysteme ps1, Psysteme ps2) BA, AL 31/05/94 returns true if ps1 represents a subset of ps2, false otherwise Inspector (no sharing on memory).
ps1 | s1 |
ps2 | s2 |
ofl_ctrl | fl_ctrl |
Definition at line 868 of file reduc.c.
References CATCH, overflow_error, pa_feasibility_ofl_ctrl(), pa_free1(), pa_make(), sl_append_system(), TRY, and UNCATCH.
Referenced by pa_system_equal_p_ofl_ctrl().
Pdisjunct pa_path_to_disjunct_rule4_ofl_ctrl( (Ppath) in_pa, int ofl_ctrl)
Returns the corresponding disjunction according rule 4.
AL 05/16/95 No sharing.
Returns according to different cases
we've modified P0 systeme
in_pa | n_pa |
ofl_ctrl | fl_ctrl |
Definition at line 570 of file reduc.c.
References C3_DEBUG, C3_RETURN, dj_append_system(), dj_empty(), DJ_UNDEFINED, fprintf(), IS_DJ, pa_empty_p(), pa_fprint, pa_free(), pa_make(), pa_max_constraints_nb(), pa_path_to_disjunct_ofl_ctrl(), pa_reduce_simple_complement(), PA_UNDEFINED, PATH_MAX_CONSTRAINTS, Spath::pcomp, Ssyslist::psys, Spath::psys, sc_dup(), sc_elim_redund_with_first_ofl_ctrl(), sc_empty_p(), sc_free(), sc_full_p(), sl_append_system(), sl_free(), sl_length(), Ssyslist::succ, and union_variable_name.
Referenced by pa_path_to_few_disjunct_ofl_ctrl().
line 1197 "reduc.w"
Pdisjunct pa_path_to_few_disjunct_ofl_ctrl( (Ppath) in_pa, (int) ofl_ctrl )
Produces a Pdisjunct corresponding to the path Ppath and reduces the number of disjunctions. See "Extension de C3 aux Unions de Polyedres" Version 2, for a complete explanation about this function. in_pa is modified. AL 23/03/95
line 1208 "reduc.w"
If it's an empty path or if it has no complements : return
We are looking for a common hyperplan
removes cons_pv and vect_dup(vect_1)
take care of rule 2
take care of rule 2
Manage memory, free: cons_oppose, common_ps, common_ps_oppose, cons_pv, vect_1, pa1, pa2
Manage memory
in_pa | n_pa |
ofl_ctrl | fl_ctrl |
Definition at line 648 of file reduc.c.
References C3_DEBUG, C3_RETURN, contrainte_free(), contrainte_in_liste(), contrainte_make(), CONTRAINTE_UNDEFINED, dj_empty(), dj_fprint_tab(), dj_free(), dj_full(), DJ_UNDEFINED, dj_union(), fprintf(), Ssysteme::inegalites, IS_DJ, pa_empty(), pa_empty_p(), pa_fprint, pa_fprint_tab(), pa_free(), pa_free1(), pa_full_p(), pa_make(), pa_new, pa_path_to_disjunct_rule4_ofl_ctrl(), pa_reduce_simple_complement(), pa_transform_eg_in_ineg(), PA_UNDEFINED_P, Spath::pcomp, Ssyslist::psys, Spath::psys, sc_dup(), sc_free(), sc_make(), sc_safe_append(), sc_supress_same_constraints(), sl_append_system(), sl_dup(), Ssyslist::succ, TCST, union_variable_name, VALUE_ONE, vect_add(), vect_chg_sgn(), vect_dup(), vect_fprint(), vect_new(), vect_rm(), and Scontrainte::vecteur.
Referenced by dj_intersect_djcomp_ofl_ctrl(), pa_feasibility_ofl_ctrl(), and pa_system_difference_ofl_ctrl().
Ppath pa_supress_same_constraints( (Ppath) in_pa )
Supress from complements of in_pa same constraints than those in positif Psystem in_pa->psys.
Returned path have no more equalities. AL050795 No sharing, no modification of inputs.
Special cases
debuging
General case
Psysteme ps = sc_supress_same_constraints( positif, comp->psys );
in_pa | n_pa |
Definition at line 528 of file reduc.c.
References C3_DEBUG, C3_RETURN, fprintf(), IS_PA, pa_empty(), pa_empty_p(), pa_fprint_tab(), pa_full(), pa_full_p(), pa_make(), PA_UNDEFINED, PA_UNDEFINED_P, Ssyslist::psys, sc_dup(), sc_supress_parallel_redund_constraints(), sc_transform_eg_in_ineg(), sl_append_system(), sl_free(), Ssyslist::succ, and union_variable_name.
Referenced by pa_feasibility_ofl_ctrl().
Pdisjunct pa_system_difference_ofl_ctrl(ps1, ps2) input : two Psystemes output : a disjunction representing ps1 - ps2 modifies : nothing comment : algorihtm : chemin = ps1 inter complement of (ps2) ret_dj = dj_simple_inegs_to_eg( pa_path_to_few_disjunct(chemin) )
ps1 | s1 |
ps2 | s2 |
ofl_ctrl | fl_ctrl |
Definition at line 908 of file reduc.c.
References dj_empty(), dj_free(), dj_simple_inegs_to_eg(), DJ_UNDEFINED, pa_free1(), pa_make(), pa_path_to_few_disjunct_ofl_ctrl(), sc_dup(), sc_empty_p(), and sl_append_system().
bool pa_system_equal_p(Psysteme ps1, Psysteme ps2) BA
ps1 | s1 |
ps2 | s2 |
ofl_ctrl | fl_ctrl |
Definition at line 890 of file reduc.c.
References pa_inclusion_p_ofl_ctrl().
Psysteme sc_elim_redund_with_first_ofl_ctrl( in_ps1, in_ps2, ofl_ctrl ) Returns constraints of in_ps2 which cut in_ps1.
AL 06 04 95 It is assumed that in_ps1 and in_ps2 are feasible ! in_ps1 is not modified, in_ps2 is modified.
Return on special cases
debuging
build in_ps1.and.in_ps2 with sharing on in_ps2 This also works if in_ps1 is full space
debuging
update information on ps1
debuging
Normalize 2 inputs systems
returns if there is no intersection
We run over in_ps2 constraints (shared by ps1) and detect redundance
eliminate the constraint from in_ps2, and thus from ps1
in_ps1 | n_ps1 |
in_ps2 | n_ps2 |
ofl_ctrl | fl_ctrl |
Definition at line 412 of file reduc.c.
References assert, Ssysteme::base, base_union(), C3_DEBUG, C3_RETURN, contrainte_free(), contrainte_reverse(), CONTRAINTE_UNDEFINED, Ssysteme::dimension, eq, eq_set_vect_nul(), fprintf(), Ssysteme::inegalites, IS_SC, Ssysteme::nb_eq, Ssysteme::nb_ineq, sc_dup(), sc_empty(), sc_fprint(), sc_free(), sc_full(), sc_full_p(), sc_rational_feasibility_ofl_ctrl(), sc_transform_eg_in_ineg(), sc_weak_consistent_p(), Scontrainte::succ, union_variable_name, vect_fprint(), vect_normalize(), vect_rm(), vect_size(), and Scontrainte::vecteur.
Referenced by pa_path_to_disjunct_rule4_ofl_ctrl().
Psysteme sc_supress_parallel_redund_constraints( in_ps1, in_ps2 ) input: 2 Psystemes in_ps1 and in_ps2 output: in_ps1 / in_ps2 (cut operation on polyhedrons) memory: Inspector (nothing is shared, nor modified, output allocated).
comment: Supress in dup(in_ps2) parallel constraints that are redundant relatively to in_ps1. Returned Psysteme have only inequalities.
debuging
Transforms equalities in inequalities if necessary
Compare with inequalities
update base and normalize
Manage memory and return
in_ps1 | n_ps1 |
in_ps2 | n_ps2 |
Definition at line 255 of file reduc.c.
References abort, Ssysteme::base, C3_DEBUG, C3_RETURN, contrainte_dup(), contrainte_parallel_in_liste(), empty, fprintf(), full, Ssysteme::inegalites, IS_SC, keep, sc_add_inegalite(), sc_creer_base(), sc_dup(), sc_empty(), sc_empty_p(), sc_fprint(), sc_free(), sc_make(), sc_normalize(), sc_transform_eg_in_ineg(), Scontrainte::succ, union_variable_name, and vect_rm().
Referenced by pa_supress_same_constraints().
Psysteme sc_supress_same_constraints( in_ps1, in_ps2 ) supress in in_ps2 constraints that are in in_ps1.
Nothing is shared, nor modified. Returned Psysteme have only inequalities. This function should be superseded by sc_supress_parallel_redund_contraints
Compare with equalities a == 0 <=> a <= 0 and -a <= 0
add co to returned inegs
add eq to returned inegs
add co and eq to returned inegs
Compare with inequalities
in_ps1 | n_ps1 |
in_ps2 | n_ps2 |
Definition at line 329 of file reduc.c.
References Ssysteme::base, C3_DEBUG, C3_RETURN, contrainte_chg_sgn(), contrainte_dup(), contrainte_free(), contrainte_in_liste(), contrainte_make(), eq, eq_in_ineq(), fprintf(), IS_SC, sc_add_inegalite(), sc_creer_base(), sc_dup(), sc_fprint(), sc_make(), sc_normalize(), Scontrainte::succ, union_variable_name, vect_chg_sgn(), vect_dup(), vect_rm(), and Scontrainte::vecteur.
Referenced by pa_path_to_few_disjunct_ofl_ctrl().
enum hspara_elem vect_parallel | ( | Pvecteur | in_v1, |
Pvecteur | in_v2 | ||
) |
enum hspara_elem vect_parallel(Pvecteur in_v1, Pvecteur in_v2) AL950711 input: 2 Pvecteur in_v1 and in_v2 output: hspara_elem (element of the parallel half space lattice) memory: Inspector (nothing is shared, nor modified, output allocated).
complexity: length(in_v1) * length(in_v2) comment: in_v1 = a1 X + b1 represents a1 X+b1 <= 0 and in_v2 a2 X + b2 <=0. if (a1!=a2) || (a1!=-a2), returns unpara else if (a1==a2), return sign(b2-b1) in ss part of hspara else if (a1==-a2), return sign(-b2-b1) in op part of hspara.
gcd of each vector
length of each vector without TCST
value of TCST and their diff
debuging
get gcd of each vector and constant linked to TCST
Determine what kind of parallel hyperplane we are in
coefficient value was 0 and was not represented
compute return value
debuging
in_v1 | n_v1 |
in_v2 | n_v2 |
Definition at line 49 of file reduc.c.
|
static |