sg.h File Reference

Go to the source code of this file.

Data Structures

struct  ttsg_soms
 Representation d'un ensemble de sommets. More...
struct  ttsg_vects
 Representation d'un ensemble de droites. More...
struct  type_sg
 Representation d'un systeme generateur par trois ensembles de sommets de rayons et de droites. More...

Defines

#define TSGSOMS   103
 Warning! Do not modify this file that is automatically generated!
#define TSGVECTS   104
#define SG_UNDEFINED   ((Ptsg) NULL)
#define SG_UNDEFINED_P(sg)   ((sg)==(SG_UNDEFINED))
#define sg_empty(sg)   ((sg)->soms_sg.nb_s==0 &&(sg)-> rays_sg.nb_v == 0 && (sg)->dtes_sg.nb_v == 0)
 vieilles definitions des fonctions d'impression void sg_fprint(); define print_sg(sg) sg_fprint(stdout,sg)
#define sg_sommets(sg)   ((sg)->soms_sg.ssg)
 acces au premier sommet de la liste des sommets d'un systeme generateur defini par un pointeur: sg_sommets(Ptsg)
#define sg_rayons(sg)   ((sg)->rays_sg.vsg)
 acces au premier rayon de la liste des rayons d'un systeme generateur defini par un pointeur: sg_rayons(Ptsg)
#define sg_droites(sg)   ((sg)->dtes_sg.vsg)
 acces a la premiere droite de la liste des droites d'un systeme generateur defini par un pointeur: sg_droites(Ptsg)
#define sg_nbre_sommets(sg)   ((sg)->soms_sg.nb_s)
 nombre de sommets: int sg_nbre_sommets(Ptsg)
#define sg_nbre_rayons(sg)   ((sg)->rays_sg.nb_v)
 nombre de rayons: int sg_nbre_rayons(Ptsg)
#define sg_nbre_droites(sg)   ((sg)->dtes_sg.nb_v)
 nombre de droites: int sg_nbre_droites(Ptsg)

Typedefs

typedef struct ttsg_soms * Ptsg_soms
 Representation d'un ensemble de sommets.
typedef struct ttsg_soms Stsg_soms
typedef struct ttsg_vects * Ptsg_vects
 Representation d'un ensemble de droites.
typedef struct ttsg_vects Stsg_vects
typedef struct type_sg * Ptsg
 Representation d'un systeme generateur par trois ensembles de sommets de rayons et de droites.
typedef struct type_sg Stsg

Functions

Ptsg sg_new (void)
 Macros obsoletes de Malik define soms_of_sg(sg) (((sg).soms_sg).ssg) define rays_of_sg(sg) (((sg).rays_sg).vsg) define dtes_of_sg(sg) (((sg).dtes_sg).vsg).
Ptsg sg_dup (Ptsg)
 Ptsg sg_dup(Ptsg sg_in): allocation d'un systeme generateur sg_out et copie sans sharing des ensembles de rayons, de droites et de sommets de l'argument sg_in.
Ptsg sg_without_line (Ptsg)
 Ptsg sg_without_line(Ptsg sg_in): allocation d'un systeme generateur et copie d'un systeme generateur dont on transforme les lignes en rayons.
Ptsg sg_add_ray (Ptsg, Pray_dte)
 Ptsg sg_add_ray(Ptsg sg, Pray_dte ray): ajout d'un rayon a un syteme generateur; aucune allocation n'est affectuee; il y a donc risque de sharing pour le rayon ray; l'argument sg est modifie.
void sg_rm_sommets (Ptsg)
 void sg_rm_sommets(Ptsg sg): desallocation d'une liste de sommets d'un systeme generateur
void sg_rm_rayons (Ptsg)
 void sg_rm_rayons(Ptsg sg): desallocation d'une liste de rayons d'un systeme generateur
void sg_rm_droites (Ptsg)
 void sg_rm_droites(Ptsg sg): desallocation d'une liste de droites d'un systeme generateur
void sg_rm (Ptsg)
 void sg_rm(Ptsg sg): liberation de l'espace memoire occupe par un systeme generateur
void sg_fprint (FILE *, Ptsg, char *(*)(Variable))
void sg_fprint_as_dense (FILE *, Ptsg, Pbase)
 void sg_fprint_as_dense(FILE * f, Ptsg sg): impression d'un systeme generateur
void sg_fprint_as_ddv (FILE *, Ptsg)
void sg_dump (Ptsg)
boolean sg_egal (Ptsg, Ptsg)
 boolean sg_egal(Ptsg sg1, Ptsg sg2): test de l'egalite de deux systemes generateur sg1 et sg2
Ptsg mk_rn (Pbase)
 Ptsg mk_rn(Pbase b): construction du systeme generateur du polyedre qui represente l'espace entier; le systeme de contraintes correspondant est vide: il ne contient ni egalite ni inegalite non triviale;.
Ptsg ajout_dte (Ptsg, Variable)
 Ptsg ajout_dte(Ptsg sg, Variable v): ajoute une droite dans la direction correspondant a la variable v.
boolean sommet_in_sg_p (Psommet, Ptsg)
boolean ray_in_sg_p (Pray_dte, Ptsg)
boolean dte_in_sg_p (Pray_dte, Ptsg)
Ptsg sg_union (Ptsg, Ptsg)

Define Documentation

#define sg_droites ( sg   )     ((sg)->dtes_sg.vsg)

acces a la premiere droite de la liste des droites d'un systeme generateur defini par un pointeur: sg_droites(Ptsg)

Definition at line 102 of file sg.h.

#define sg_empty ( sg   )     ((sg)->soms_sg.nb_s==0 &&(sg)-> rays_sg.nb_v == 0 && (sg)->dtes_sg.nb_v == 0)

vieilles definitions des fonctions d'impression void sg_fprint(); define print_sg(sg) sg_fprint(stdout,sg)

macros d'acces aux champstest de sg vide

Definition at line 91 of file sg.h.

#define sg_nbre_droites ( sg   )     ((sg)->dtes_sg.nb_v)

nombre de droites: int sg_nbre_droites(Ptsg)

Definition at line 111 of file sg.h.

#define sg_nbre_rayons ( sg   )     ((sg)->rays_sg.nb_v)

nombre de rayons: int sg_nbre_rayons(Ptsg)

Definition at line 108 of file sg.h.

#define sg_nbre_sommets ( sg   )     ((sg)->soms_sg.nb_s)

nombre de sommets: int sg_nbre_sommets(Ptsg)

Definition at line 105 of file sg.h.

#define sg_rayons ( sg   )     ((sg)->rays_sg.vsg)

acces au premier rayon de la liste des rayons d'un systeme generateur defini par un pointeur: sg_rayons(Ptsg)

Definition at line 98 of file sg.h.

#define sg_sommets ( sg   )     ((sg)->soms_sg.ssg)

acces au premier sommet de la liste des sommets d'un systeme generateur defini par un pointeur: sg_sommets(Ptsg)

Definition at line 94 of file sg.h.

#define SG_UNDEFINED   ((Ptsg) NULL)

Definition at line 80 of file sg.h.

#define SG_UNDEFINED_P ( sg   )     ((sg)==(SG_UNDEFINED))

Definition at line 81 of file sg.h.

#define TSGSOMS   103

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

Modify src/Libs/sg/sg-local.h instead, to add your own modifications. header file built by cprotopackage sur les systemes generateur sg Francois Irigoin, Mai 1989

packages a inclure: boolean.h, arithmetique.h, variable.h, vecteur.h, ray_dte.h et sommet.h

package utilisateur: polyedre.h

Definition at line 44 of file sg.h.

#define TSGVECTS   104

Definition at line 45 of file sg.h.

Typedef Documentation

typedef struct type_sg * Ptsg

Representation d'un systeme generateur par trois ensembles de sommets de rayons et de droites.

L'ensemble vide est represente par un systeme generateur n'ayant aucun element dans ces trois ensembles (soms_sg.nb_s==0 && rays_sg.nb_v == 0 && dtes_sg.nb_v == 0)

L'espace tout entier Rn est represente par n droites et un sommet. Par convention ce sommet est l'origine.

La dimension de l'espace contenant le polyedre genere n'est pas accessible directement. Il faut parcourir tous les elements generateurs et chercher leurs coordonnees non nulles.

typedef struct ttsg_soms * Ptsg_soms

Representation d'un ensemble de sommets.

typedef struct ttsg_vects * Ptsg_vects

Representation d'un ensemble de droites.

typedef struct type_sg Stsg
typedef struct ttsg_soms Stsg_soms
typedef struct ttsg_vects Stsg_vects

Function Documentation

Ptsg ajout_dte ( Ptsg  ,
Variable   
)

Ptsg ajout_dte(Ptsg sg, Variable v): ajoute une droite dans la direction correspondant a la variable v.

creation

ajout

Definition at line 474 of file sg.c.

References MALLOC, RAY_DTE, sg_droites, sg_nbre_droites, rdte::succ, VALUE_ONE, vect_new(), and rdte::vecteur.

00477 {
00478     Pray_dte dte;
00479 
00480     /* creation */
00481 
00482     dte = (Pray_dte ) MALLOC(sizeof(Sray_dte),RAY_DTE,"ajout_dte");
00483     dte->vecteur = vect_new(v, VALUE_ONE);
00484 
00485     /* ajout */
00486 
00487     dte->succ = sg_droites(sg);
00488     sg_droites(sg) = dte;
00489     sg_nbre_droites(sg)++;
00490     return(sg);
00491 }

Here is the call graph for this function:

boolean dte_in_sg_p ( Pray_dte  ,
Ptsg   
)

Definition at line 524 of file sg.c.

References FALSE, NULL, SG_UNDEFINED_P, rdte::succ, vect_equal(), and rdte::vecteur.

Referenced by sg_union().

00527 {
00528     Pray_dte pr;
00529     boolean trouve = FALSE;
00530 
00531     if (!SG_UNDEFINED_P(sg)) {
00532         for (pr = sg->dtes_sg.vsg; pr != NULL; pr=pr->succ) {
00533             trouve = trouve || vect_equal(dte->vecteur,pr->vecteur);
00534         }
00535     }
00536     return (trouve);
00537 }

Here is the call graph for this function:

Here is the caller graph for this function:

Ptsg mk_rn ( Pbase  b  ) 

Ptsg mk_rn(Pbase b): construction du systeme generateur du polyedre qui represente l'espace entier; le systeme de contraintes correspondant est vide: il ne contient ni egalite ni inegalite non triviale;.

Modifications:

  • remplacement du parametre entier dim par une base (FI, 18/12/89)

un sommet a l'origine

il n'y a aucun rayon

enfin, une droite par dimension

Definition at line 438 of file sg.c.

References base_dimension, fprintf(), ifdebug, NULL, ray_dte_make(), sg, sg_fprint(), sg_new(), sommet_make(), rdte::succ, VALUE_ONE, variable_dump_name(), vect_new(), VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.

00440 {
00441     Ptsg sg;
00442     Pray_dte d;
00443 
00444     ifdebug(8) (void) fprintf(stderr,"mk_rn: begin\n");
00445 
00446     sg = sg_new();
00447 
00448     /* un sommet a l'origine */
00449     (sg->soms_sg).nb_s = 1;
00450     (sg->soms_sg).ssg = sommet_make(VALUE_ONE, VECTEUR_NUL);
00451 
00452     /* il n'y a aucun rayon */
00453     (sg->rays_sg).nb_v = 0;
00454     (sg->rays_sg).vsg = NULL;
00455 
00456     /* enfin, une droite par dimension */
00457     (sg->dtes_sg).nb_v = base_dimension(b);
00458     (sg->dtes_sg).vsg = NULL;
00459     for (;!VECTEUR_NUL_P(b); b = b->succ) {
00460         d = ray_dte_make(vect_new(vecteur_var(b), VALUE_ONE));
00461         d->succ = (sg->dtes_sg).vsg;
00462         (sg->dtes_sg).vsg = d;
00463     }
00464     ifdebug(8) {
00465         sg_fprint(stderr, sg, variable_dump_name);
00466         (void) fprintf(stderr,"mk_rn: end\n");
00467     }
00468     return(sg);
00469 }

Here is the call graph for this function:

boolean ray_in_sg_p ( Pray_dte  ,
Ptsg   
)

Definition at line 509 of file sg.c.

References FALSE, NULL, SG_UNDEFINED_P, rdte::succ, vect_equal(), and rdte::vecteur.

Referenced by sg_union().

00512 {
00513     Pray_dte pr;
00514     boolean trouve = FALSE;
00515 
00516     if (!SG_UNDEFINED_P(sg)) {
00517         for (pr = sg->rays_sg.vsg;  pr != NULL; pr=pr->succ) {
00518             trouve = trouve || vect_equal(ray->vecteur,pr->vecteur);
00519         }
00520     }
00521     return (trouve);
00522 }

Here is the call graph for this function:

Here is the caller graph for this function:

Ptsg sg_add_ray ( Ptsg  sg,
Pray_dte  ray 
)

Ptsg sg_add_ray(Ptsg sg, Pray_dte ray): ajout d'un rayon a un syteme generateur; aucune allocation n'est affectuee; il y a donc risque de sharing pour le rayon ray; l'argument sg est modifie.

Aucune elimination de redondance pour le moment. On peut en envisager trois niveaux: egalite entre rayons, proportionalite entre rayons et combinaison lineaire positive de rayons.

chainage en tete de la liste des rayons

Parameters:
sg g
ray ay

Definition at line 185 of file sg.c.

00188 {
00189     /* chainage en tete de la liste des rayons */
00190     ray = sg->rays_sg.vsg;
00191     sg->rays_sg.vsg = ray;
00192 
00193     return sg;
00194 }

void sg_dump ( Ptsg   ) 

char * (*variable_dump_name)();

Definition at line 364 of file sg.c.

References sg_fprint(), and variable_dump_name().

00366 {
00367     /* char * (*variable_dump_name)(); */
00368 
00369     sg_fprint(stderr, sg, variable_dump_name);
00370 }

Here is the call graph for this function:

Ptsg sg_dup ( Ptsg  sg_in  ) 

Ptsg sg_dup(Ptsg sg_in): allocation d'un systeme generateur sg_out et copie sans sharing des ensembles de rayons, de droites et de sommets de l'argument sg_in.

sg_in n'est pas modifie

Autre nom (obsolete): cp_sg()

Extension: duplicate undefined generating systems (FI, 22 May 2009)

sc_dup() has been replaced by sc_copy() which maintains the order in the data structure lists. Maybe we need the same change for generating systems.

duplication de la liste des sommets

duplication de la liste des rayons

duplication de la liste des droites

Parameters:
sg_in g_in

Definition at line 80 of file sg.c.

References base_dup(), NULL, ray_dte_dup(), s, sg_new(), SG_UNDEFINED, SG_UNDEFINED_P, sommet_dup(), rdte::succ, and typ_som::succ.

Referenced by conflict_dup(), initialize_newgen(), sg_union(), and sg_without_line().

00081 {
00082   Ptsg sg_out = SG_UNDEFINED;
00083 
00084   if(!SG_UNDEFINED_P(sg_in)) {
00085     Pray_dte rd;
00086     Pray_dte rd_new;
00087     Psommet s;
00088     Psommet s_new;
00089 
00090     sg_out = sg_new();
00091 
00092     /* duplication de la liste des sommets */
00093     sg_out->soms_sg.nb_s = sg_in->soms_sg.nb_s;
00094     for(s = sg_in->soms_sg.ssg; s != NULL; s = s->succ) {
00095       s_new = sommet_dup(s);
00096       s_new->succ = sg_out->soms_sg.ssg;
00097       sg_out->soms_sg.ssg = s_new;
00098     }
00099 
00100     /* duplication de la liste des rayons */
00101     sg_out->rays_sg.nb_v = sg_in->rays_sg.nb_v;
00102     for(rd = sg_in->rays_sg.vsg; rd != NULL; rd = rd->succ) {
00103       rd_new = ray_dte_dup(rd);
00104       rd_new->succ = sg_out->rays_sg.vsg;
00105       sg_out->rays_sg.vsg = rd_new;
00106     }
00107 
00108     /* duplication de la liste des droites */
00109     sg_out->dtes_sg.nb_v = sg_in->dtes_sg.nb_v;
00110     for(rd = sg_in->dtes_sg.vsg; rd != NULL; rd = rd->succ) {
00111       rd_new = ray_dte_dup(rd);
00112       rd_new->succ = sg_out->dtes_sg.vsg;
00113       sg_out->dtes_sg.vsg = rd_new;
00114     }
00115 
00116     sg_out->base = base_dup(sg_in->base);
00117   }
00118   return sg_out;
00119 }

Here is the call graph for this function:

Here is the caller graph for this function:

boolean sg_egal ( Ptsg  sg1,
Ptsg  sg2 
)

boolean sg_egal(Ptsg sg1, Ptsg sg2): test de l'egalite de deux systemes generateur sg1 et sg2

Ce test suppose que les deux systemes ont ete prealablement normalises:

  • reduction des coordonnees des sommets, des rayons et des droites par leur PGCD
  • suppression des doublons dans les listes
  • suppression des rayons qui sont des droites
  • representation unique des vecteurs directeurs des droites (vecteur lexicopositif par exemple)
  • suppression des vecteurs nuls comme rayon ou droite
  • absence d'elements redondants dans les systemes generateurs

Ancien nom: sg_egal()

Parameters:
sg1 g1
sg2 g2

Definition at line 421 of file sg.c.

References egal_rd(), egal_soms(), FALSE, sg_nbre_sommets, and TRUE.

00423 {
00424     if (! egal_soms(&(sg1->soms_sg) ,&(sg2->soms_sg) ) ) return(FALSE);
00425     if (sg_nbre_sommets(sg1) == 0) return(TRUE);
00426     if (! egal_rd(&(sg1->rays_sg),&(sg2->rays_sg))) return(FALSE);
00427     if (! egal_rd(&(sg1->dtes_sg),&(sg2->dtes_sg))) return(FALSE);
00428     return(TRUE);
00429 }

Here is the call graph for this function:

void sg_fprint ( FILE *  ,
Ptsg  ,
char *  *)(Variable 
)
void sg_fprint_as_ddv ( FILE *  ,
Ptsg   
)

For each coordinate

For all vertices

For all rays

For all lines

Definition at line 328 of file sg.c.

References BASE_NULLE, BASE_NULLE_P, c, direction_to_representation, fprintf(), line_to_direction, NULL, ray_to_direction, sg_droites, sg_rayons, sg_sommets, rdte::succ, typ_som::succ, Svecteur::succ, v, value_sign, vect_coeff(), rdte::vecteur, typ_som::vecteur, vecteur_var, and vertex_to_direction.

Referenced by check_for_conflict(), prettyprint_dependence_graph(), and prettyprint_dot_dependence_graph().

00331 {
00332     Pbase c = BASE_NULLE;
00333     int ddv = 0;
00334 
00335     fprintf(fd, "ddv(");
00336 
00337     /* For each coordinate */
00338     for(c=sg->base; !BASE_NULLE_P(c); c = c->succ) {
00339         Psommet v;
00340         Pray_dte r;
00341         Pray_dte l;
00342 
00343         /* For all vertices */
00344         for(v=sg_sommets(sg); v!= NULL; v = v->succ) {
00345             ddv |= vertex_to_direction[1+value_sign(vect_coeff(vecteur_var(c), v->vecteur))];
00346         }
00347 
00348         /* For all rays */
00349         for(r=sg_rayons(sg); r!= NULL; r = r->succ) {
00350             ddv |= ray_to_direction[1+value_sign(vect_coeff(vecteur_var(c), r->vecteur))];
00351         }
00352 
00353         /* For all lines */
00354         for(l=sg_droites(sg); l!= NULL; l = l->succ) {
00355             ddv |= line_to_direction[1+value_sign(vect_coeff(vecteur_var(c), l->vecteur))];
00356         }
00357 
00358         fprintf(fd, c==sg->base? "%s" : ",%s", direction_to_representation[ddv]);
00359     }
00360 
00361     fprintf(fd, ")");
00362 }

Here is the call graph for this function:

Here is the caller graph for this function:

void sg_fprint_as_dense ( FILE *  f,
Ptsg  sg,
Pbase  b 
)

void sg_fprint_as_dense(FILE * f, Ptsg sg): impression d'un systeme generateur

Note: b could/should be sg->base

Parameters:
sg g

Definition at line 285 of file sg.c.

References fprint_lray_dte_as_dense(), fprint_lsom_as_dense(), fprintf(), sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, and sg_sommets.

Referenced by prettyprint_dependence_graph(), prettyprint_dependence_graph_view(), and whole_loop_parallelize().

00289 {
00290     (void) fprintf(f,"Generating system:\n");
00291 
00292     (void) fprintf(f,"%d Vert%s \n",sg_nbre_sommets(sg),
00293                    sg_nbre_sommets(sg)==1? "ex" : "ices");
00294     fprint_lsom_as_dense(f, sg_sommets(sg), b);
00295 
00296     if(sg_nbre_rayons(sg)>0) {
00297         (void) fprintf(f,"\n%d Ray%s \n",sg_nbre_rayons(sg),
00298                        sg_nbre_rayons(sg)==1? "" : "s");
00299         fprint_lray_dte_as_dense(f, sg_rayons(sg), b);
00300     }
00301 
00302     if(sg_nbre_droites(sg)>0) {
00303         (void) fprintf(f,"\n%d Line%s \n",sg_nbre_droites(sg),
00304                        sg_nbre_rayons(sg)==1? "" : "s");
00305         fprint_lray_dte_as_dense(f, sg_droites(sg), b);
00306     }
00307 
00308     (void) fprintf(f,"\nEnd of generating system ****\n");
00309 }

Here is the call graph for this function:

Here is the caller graph for this function:

Ptsg sg_new ( void   ) 

Macros obsoletes de Malik define soms_of_sg(sg) (((sg).soms_sg).ssg) define rays_of_sg(sg) (((sg).rays_sg).vsg) define dtes_of_sg(sg) (((sg).dtes_sg).vsg).

TSGsg.c

Definition at line 51 of file sg.c.

References MALLOC, NULL, and sg.

Referenced by dependence_cone_positive(), main(), mk_rn(), sc_to_sg_chernikova(), and sg_dup().

00052 {
00053     Ptsg sg;
00054 
00055     sg = (Ptsg) MALLOC(sizeof(Stsg),TSG,"sg_new");
00056     sg->soms_sg.nb_s = 0;
00057     sg->soms_sg.ssg = NULL;
00058     sg->rays_sg.nb_v = 0;
00059     sg->rays_sg.vsg = NULL;
00060     sg->dtes_sg.nb_v = 0;
00061     sg->dtes_sg.vsg = NULL;
00062     sg->base = NULL;
00063     return sg;
00064 }

Here is the caller graph for this function:

void sg_rm ( Ptsg  sg  ) 

void sg_rm(Ptsg sg): liberation de l'espace memoire occupe par un systeme generateur

Ne pas oublier de remettre le pointeur correspondant a NULL dans le programme appelant

Ancien nom: elim_sg()

Parameters:
sg g

Definition at line 245 of file sg.c.

References base_rm, FREE, sg_rm_droites(), sg_rm_rayons(), and sg_rm_sommets().

Referenced by dependence_cone_positive(), initialize_newgen(), sc_to_sg_chernikova(), TestDependence(), and whole_loop_parallelize().

00247 {
00248     sg_rm_sommets(sg);
00249     sg_rm_rayons(sg);
00250     sg_rm_droites(sg);
00251     base_rm(sg->base);
00252     FREE((char *)sg,TSG,"sg_rm");
00253 }

Here is the call graph for this function:

Here is the caller graph for this function:

void sg_rm_droites ( Ptsg   ) 

void sg_rm_droites(Ptsg sg): desallocation d'une liste de droites d'un systeme generateur

Definition at line 229 of file sg.c.

References elim_tt_rd(), and NULL.

Referenced by sg_rm().

00231 {
00232     elim_tt_rd(sg->rays_sg.vsg);
00233     sg->rays_sg.vsg = NULL;
00234     sg->rays_sg.nb_v = 0;
00235 }

Here is the call graph for this function:

Here is the caller graph for this function:

void sg_rm_rayons ( Ptsg   ) 

void sg_rm_rayons(Ptsg sg): desallocation d'une liste de rayons d'un systeme generateur

Definition at line 218 of file sg.c.

References elim_tt_rd(), and NULL.

Referenced by sg_rm().

00220 {
00221     elim_tt_rd(sg->rays_sg.vsg);
00222     sg->rays_sg.vsg = NULL;
00223     sg->rays_sg.nb_v = 0;
00224 }

Here is the call graph for this function:

Here is the caller graph for this function:

void sg_rm_sommets ( Ptsg  sg  ) 

void sg_rm_sommets(Ptsg sg): desallocation d'une liste de sommets d'un systeme generateur

Ex-fonction elim_tt_som() qui prenait en argument une liste de sommets

Parameters:
sg g

Definition at line 201 of file sg.c.

References NULL, s, s1, SOMMET_RM, and typ_som::succ.

Referenced by sg_rm().

00203 {
00204     Psommet s,s1;
00205 
00206     for (s=sg->soms_sg.ssg; s!=NULL;) {
00207         s1 = s->succ;
00208         SOMMET_RM(s,"sg_rm_sommets");
00209         s = s1;
00210     }
00211     sg->soms_sg.ssg = NULL;
00212     sg->soms_sg.nb_s = 0;
00213 }

Here is the caller graph for this function:

Ptsg sg_union ( Ptsg  ,
Ptsg   
)

union des sommets

union des rayons

nion des droites

Definition at line 539 of file sg.c.

References base_rm, base_union(), dte_in_sg_p(), FALSE, NULL, ray_dte_dup(), ray_in_sg_p(), sg, sg_dup(), sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sommet_dup(), sommet_in_sg_p(), rdte::succ, typ_som::succ, and TRUE.

Referenced by main().

00541 {
00542     Ptsg sg;
00543     boolean newsommet = (sg_nbre_sommets(sg1)== 0) ? TRUE : FALSE;
00544     boolean newray = (sg_nbre_rayons(sg1)== 0) ? TRUE : FALSE;
00545     boolean newdte = (sg_nbre_droites(sg1)== 0) ? TRUE : FALSE;
00546     Psommet ps, ps_tmp;
00547     Pray_dte pr,pr_tmp;
00548 
00549     if (sg1 == NULL)    
00550         return (sg_dup(sg2));
00551     if (sg2 == NULL)
00552         return (sg_dup(sg1));
00553 
00554     sg = sg_dup(sg1); 
00555     sg->soms_sg.nb_s = sg_nbre_sommets(sg1);
00556     sg->rays_sg.nb_v =sg_nbre_rayons(sg1) ;
00557     sg->dtes_sg.nb_v = sg_nbre_droites(sg1);
00558     /* union des sommets */
00559 
00560     for (ps = sg->soms_sg.ssg, ps_tmp = ps; ps != NULL ;  ps_tmp = ps, ps=ps->succ)
00561         ;
00562     for (ps = sg2->soms_sg.ssg; ps != NULL; ps=ps->succ) {
00563         if (newsommet) {
00564             sg->soms_sg.ssg = ps_tmp=sommet_dup(ps);
00565             newsommet = FALSE;
00566             sg->soms_sg.nb_s++;
00567         } else {
00568             if (!sommet_in_sg_p(ps,sg)) {
00569                 ps_tmp->succ=sommet_dup(ps);
00570                 ps_tmp = ps_tmp->succ; sg->soms_sg.nb_s++;
00571             }
00572         }
00573     }
00574 
00575     /* union des rayons */
00576     for (pr = sg->rays_sg.vsg, pr_tmp=pr; pr!= NULL; pr_tmp = pr, pr = pr->succ)
00577         ;
00578     for (pr = sg2->rays_sg.vsg; pr != NULL; pr=pr->succ) {
00579         if (newray) {
00580             sg->rays_sg.vsg = pr_tmp=ray_dte_dup(pr);
00581             newray = FALSE;
00582             sg->rays_sg.nb_v++;
00583         } else {
00584             if (!ray_in_sg_p(pr,sg)) {
00585                 pr_tmp->succ=ray_dte_dup(pr);
00586                 pr_tmp = pr_tmp->succ;
00587                 sg->rays_sg.nb_v++;
00588             }
00589         }
00590     }
00591 
00592     /*union des droites */
00593     for (pr = sg->dtes_sg.vsg, pr_tmp=pr; pr!= NULL; pr_tmp = pr,pr=pr->succ)
00594         ;
00595     for (pr = sg2->dtes_sg.vsg; pr != NULL; pr=pr->succ) {
00596         if (newdte) {
00597             sg->dtes_sg.vsg = pr_tmp=ray_dte_dup(pr);
00598             newdte = FALSE;
00599             sg->dtes_sg.nb_v++;
00600         } else {
00601             if (!dte_in_sg_p(pr,sg)) {
00602                 pr_tmp->succ=ray_dte_dup(pr);
00603                 pr_tmp = pr_tmp->succ;
00604                 sg->dtes_sg.nb_v++;
00605             }
00606         }
00607     }
00608     base_rm(sg->base);
00609     sg->base = base_union(sg1->base,sg2->base);
00610     return (sg); 
00611 }

Here is the call graph for this function:

Here is the caller graph for this function:

Ptsg sg_without_line ( Ptsg  sg_in  ) 

Ptsg sg_without_line(Ptsg sg_in): allocation d'un systeme generateur et copie d'un systeme generateur dont on transforme les lignes en rayons.

Aucune elimination de redondance pour le moment. On peut en envisager trois niveaux: egalite entre rayons, proportionalite entre rayons et combinaison lineaire positive de rayons.

ajout des l'oppose des vecteurs directeur des droites a la liste des rayons

allocation et calcul du vecteur opppose

chainage en tete de la liste des rayons

ajout (sans duplication en memoire) de la liste des vecteurs directeurs des droites a la liste des rayons, si l'ensemble des droites n'est pas vide

ajout de l'ensemble des rayons a l'ensemble des droites

transfert de la liste des droites a la liste des rayons

mise a jour des nombres de droites et de vecteurs

Parameters:
sg_in g_in

Definition at line 128 of file sg.c.

References fprintf(), ifdebug, NULL, ray_oppose(), sg_dup(), sg_fprint(), rdte::succ, and variable_dump_name().

00130 {
00131     Ptsg sg_out;
00132     Pray_dte rd;
00133     Pray_dte rd_new;
00134     Pray_dte rd_prec;
00135 
00136     ifdebug(8) {
00137         (void) fprintf(stderr,"sg_without_line: begin\n");
00138         (void) fprintf(stderr,"sg_without_line: sg_in\n");
00139         sg_fprint(stderr, sg_in, variable_dump_name);
00140     }
00141 
00142     sg_out = sg_dup(sg_in);
00143 
00144     /* ajout des l'oppose des vecteurs directeur des droites a la liste
00145        des rayons */
00146     for(rd_prec=rd=sg_out->dtes_sg.vsg; rd!=NULL; rd_prec=rd, rd=rd->succ) {
00147         /* allocation et calcul du vecteur opppose */
00148         rd_new = ray_oppose(rd);
00149         /* chainage en tete de la liste des rayons */
00150         rd_new = sg_out->rays_sg.vsg;
00151         sg_out->rays_sg.vsg = rd_new;
00152     }
00153 
00154     /* ajout (sans duplication en memoire) de la liste des vecteurs directeurs
00155        des droites a la liste des rayons, si l'ensemble des droites n'est
00156        pas vide */
00157     if(rd_prec!=NULL) {
00158         /* ajout de l'ensemble des rayons a l'ensemble des droites */
00159         rd_prec->succ = sg_out->rays_sg.vsg;
00160         /* transfert de la liste des droites a la liste des rayons */
00161         sg_out->rays_sg.vsg = sg_out->dtes_sg.vsg;
00162         sg_out->dtes_sg.vsg = NULL;
00163         /* mise a jour des nombres de droites et de vecteurs */
00164         sg_out->rays_sg.nb_v += 2*(sg_out->dtes_sg.nb_v);
00165         sg_out->dtes_sg.nb_v = 0;
00166     }
00167 
00168     ifdebug(8) {
00169         (void) fprintf(stderr,"sg_without_line: sg_out\n");
00170         sg_fprint(stderr, sg_out, variable_dump_name);
00171         (void) fprintf(stderr,"sg_without_line: end\n");
00172     }
00173 
00174     return sg_out;
00175 }

Here is the call graph for this function:

boolean sommet_in_sg_p ( Psommet  ,
Ptsg   
)

Definition at line 494 of file sg.c.

References FALSE, NULL, SG_UNDEFINED_P, typ_som::succ, vect_equal(), and typ_som::vecteur.

Referenced by sg_union().

00497 {
00498     Psommet ps;
00499     boolean trouve = FALSE;
00500 
00501     if (!SG_UNDEFINED_P(sg)) {
00502         for (ps = sg->soms_sg.ssg; ps != NULL && !trouve ; ps=ps->succ) {
00503             trouve = trouve || vect_equal(som->vecteur,ps->vecteur);
00504         }
00505     }
00506     return (trouve);
00507 }

Here is the call graph for this function:

Here is the caller graph for this function:

Generated by  doxygen 1.6.2-20100208