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...

Macros
#define	TSG   101
	Warning! Do not modify this file that is automatically generated! More...
#define	TSGSOMS   103
#define	TSGVECTS   104
#define	SG_UNDEFINED   ((Ptsg) NULL)
#define	SG_UNDEFINED_P(sg)   ((sg)==(SG_UNDEFINED))
#define	sg_sommets(sg)   ((sg)->soms_sg.ssg)
	vieilles definitions des fonctions d'impression void sg_fprint(); #define print_sg(sg) sg_fprint(stdout,sg) More...
#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) More...
#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) More...
#define	sg_nbre_sommets(sg)   ((sg)->soms_sg.nb_s)
	nombre de sommets: int sg_nbre_sommets(Ptsg) More...
#define	sg_nbre_rayons(sg)   ((sg)->rays_sg.nb_v)
	nombre de rayons: int sg_nbre_rayons(Ptsg) More...
#define	sg_nbre_droites(sg)   ((sg)->dtes_sg.nb_v)
	nombre de droites: int sg_nbre_droites(Ptsg) More...
#define	sg_base(sg)   ((sg)->base)
	Basis used for the generating system. More...
#define	sg_empty(sg)    ((sg)->soms_sg.nb_s==0 &&(sg)-> rays_sg.nb_v == 0 && (sg)->dtes_sg.nb_v == 0)
	Test for an empty generating system, which corresponds to an empty set. More...

Typedefs
typedef struct ttsg_soms *	Ptsg_soms
	Representation d'un ensemble de sommets. More...
typedef struct ttsg_soms	Stsg_soms
typedef struct ttsg_vects *	Ptsg_vects
	Representation d'un ensemble de droites. More...
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. More...
typedef struct type_sg	Stsg

Functions
Ptsg	sg_new (void)
	Obsolete macros of Malik Imadache #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) More...
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. More...
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. More...
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. More...
void	sg_rm_sommets (Ptsg)
	void sg_rm_sommets(Ptsg sg): desallocation d'une liste de sommets d'un systeme generateur More...
void	sg_rm_rayons (Ptsg)
	void sg_rm_rayons(Ptsg sg): desallocation d'une liste de rayons d'un systeme generateur More...
void	sg_rm_droites (Ptsg)
	void sg_rm_droites(Ptsg sg): desallocation d'une liste de droites d'un systeme generateur More...
void	sg_rm (Ptsg)
	void sg_rm(Ptsg sg): liberation de l'espace memoire occupe par un systeme generateur More...
void	sg_fprint (FILE *, Ptsg, char *(*)(Variable))
void	sg_print (Ptsg, char *(*)(Variable))
void	sg_dump (Ptsg)
	For debugging. More...
void	sg_fprint_as_dense (FILE *, Ptsg, Pbase)
	void sg_fprint_as_dense(FILE * f, Ptsg sg): impression d'un systeme generateur More...
void	sg_fprint_as_ddv (FILE *, Ptsg)
bool	sg_egal (Ptsg, Ptsg)
	bool sg_egal(Ptsg sg1, Ptsg sg2): test de l'egalite de deux systemes generateur sg1 et sg2 More...
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;. More...
Ptsg	ajout_dte (Ptsg, Variable)
	Ptsg ajout_dte(Ptsg sg, Variable v): ajoute une droite dans la direction correspondant a la variable v. More...
bool	sommet_in_sg_p (Psommet, Ptsg)
bool	ray_in_sg_p (Pray_dte, Ptsg)
bool	dte_in_sg_p (Pray_dte, Ptsg)
Ptsg	sg_union (Ptsg, Ptsg)

Macro Definition Documentation

sg_base

#define sg_base

(

sg

)

((sg)->base)

Basis used for the generating system.

Definition at line 113 of file sg.h.

sg_droites

#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 101 of file sg.h.

sg_empty

#define sg_empty

(

sg

)

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

Test for an empty generating system, which corresponds to an empty set.

Definition at line 116 of file sg.h.

sg_nbre_droites

#define sg_nbre_droites

(

sg

)

((sg)->dtes_sg.nb_v)

nombre de droites: int sg_nbre_droites(Ptsg)

Definition at line 110 of file sg.h.

sg_nbre_rayons

#define sg_nbre_rayons

(

sg

)

((sg)->rays_sg.nb_v)

nombre de rayons: int sg_nbre_rayons(Ptsg)

Definition at line 107 of file sg.h.

sg_nbre_sommets

#define sg_nbre_sommets

(

sg

)

((sg)->soms_sg.nb_s)

nombre de sommets: int sg_nbre_sommets(Ptsg)

Definition at line 104 of file sg.h.

sg_rayons

#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 97 of file sg.h.

sg_sommets

#define sg_sommets

(

sg

)

((sg)->soms_sg.ssg)

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

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

Definition at line 93 of file sg.h.

SG_UNDEFINED

#define SG_UNDEFINED   ((Ptsg) NULL)

Definition at line 81 of file sg.h.

SG_UNDEFINED_P

#define SG_UNDEFINED_P

(

sg

)

((sg)==(SG_UNDEFINED))

Definition at line 82 of file sg.h.

TSG

#define TSG   101

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 cproto sg-local.h package 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.

TSGSOMS

#define TSGSOMS   103

Definition at line 45 of file sg.h.

TSGVECTS

#define TSGVECTS   104

Definition at line 46 of file sg.h.

Typedef Documentation

Ptsg

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.

Ptsg_soms

typedef struct ttsg_soms * Ptsg_soms

Representation d'un ensemble de sommets.

Ptsg_vects

typedef struct ttsg_vects * Ptsg_vects

Representation d'un ensemble de droites.

Stsg

typedef struct type_sg Stsg

Stsg_soms

typedef struct ttsg_soms Stsg_soms

Stsg_vects

typedef struct ttsg_vects Stsg_vects

Function Documentation

ajout_dte()

Ptsg ajout_dte	(	Ptsg	sg,
		Variable	v
	)

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

creation

ajout

Parameters

sg

g

Definition at line 487 of file sg.c.

{
    Pray_dte dte;
 
    /* creation */
 
    dte = (Pray_dte ) MALLOC(sizeof(Sray_dte),RAY_DTE,"ajout_dte");
    dte->vecteur = vect_new(v, VALUE_ONE);
 
    /* ajout */
 
    dte->succ = sg_droites(sg);
    sg_droites(sg) = dte;
    sg_nbre_droites(sg)++;
    return(sg);
}

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

Here is the call graph for this function:

dte_in_sg_p()

bool dte_in_sg_p	(	Pray_dte	dte,
		Ptsg	sg
	)

Parameters

dte	te
sg	g

Definition at line 537 of file sg.c.

{
    Pray_dte pr;
    bool trouve = false;
 
    if (!SG_UNDEFINED_P(sg)) {
        for (pr = sg->dtes_sg.vsg; pr != NULL; pr=pr->succ) {
            trouve = trouve || vect_equal(dte->vecteur,pr->vecteur);
        }
    }
    return (trouve);
}

References type_sg::dtes_sg, sg, SG_UNDEFINED_P, rdte::succ, vect_equal(), rdte::vecteur, and ttsg_vects::vsg.

Referenced by sg_union().

Here is the call graph for this function:

Here is the caller graph for this function:

mk_rn()

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 451 of file sg.c.

{
    Ptsg sg;
    Pray_dte d;
 
    ifdebug(8) (void) fprintf(stderr,"mk_rn: begin\n");
 
    sg = sg_new();
 
    /* un sommet a l'origine */
    (sg->soms_sg).nb_s = 1;
    (sg->soms_sg).ssg = sommet_make(VALUE_ONE, VECTEUR_NUL);
 
    /* il n'y a aucun rayon */
    (sg->rays_sg).nb_v = 0;
    (sg->rays_sg).vsg = NULL;
 
    /* enfin, une droite par dimension */
    (sg->dtes_sg).nb_v = base_dimension(b);
    (sg->dtes_sg).vsg = NULL;
    for (;!VECTEUR_NUL_P(b); b = b->succ) {
        d = ray_dte_make(vect_new(vecteur_var(b), VALUE_ONE));
        d->succ = (sg->dtes_sg).vsg;
        (sg->dtes_sg).vsg = d;
    }
    ifdebug(8) {
        sg_fprint(stderr, sg, variable_dump_name);
        (void) fprintf(stderr,"mk_rn: end\n");
    }
    return(sg);
}

References base_dimension, type_sg::dtes_sg, fprintf(), ifdebug, ray_dte_make(), type_sg::rays_sg, sg, sg_fprint(), sg_new(), sommet_make(), type_sg::soms_sg, rdte::succ, Svecteur::succ, VALUE_ONE, variable_dump_name(), vect_new(), VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.

Here is the call graph for this function:

ray_in_sg_p()

bool ray_in_sg_p	(	Pray_dte	ray,
		Ptsg	sg
	)

Parameters

ray	ay
sg	g

Definition at line 522 of file sg.c.

{
    Pray_dte pr;
    bool trouve = false;
 
    if (!SG_UNDEFINED_P(sg)) {
        for (pr = sg->rays_sg.vsg;  pr != NULL; pr=pr->succ) {
            trouve = trouve || vect_equal(ray->vecteur,pr->vecteur);
        }
    }
    return (trouve);
}

References type_sg::rays_sg, sg, SG_UNDEFINED_P, rdte::succ, vect_equal(), rdte::vecteur, and ttsg_vects::vsg.

Referenced by sg_union().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_add_ray()

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 189 of file sg.c.

{
    /* chainage en tete de la liste des rayons */
    ray = sg->rays_sg.vsg;
    sg->rays_sg.vsg = ray;
 
    return sg;
}

References type_sg::rays_sg, sg, and ttsg_vects::vsg.

sg_dump()

void sg_dump

(

Ptsg

sg

)

For debugging.

Parameters

sg

g

Definition at line 288 of file sg.c.

{
  sg_print(sg, variable_dump_name);
}

References sg, sg_print(), and variable_dump_name().

Here is the call graph for this function:

sg_dup()

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 84 of file sg.c.

{
  Ptsg sg_out = SG_UNDEFINED;
 
  if(!SG_UNDEFINED_P(sg_in)) {
    Pray_dte rd;
    Pray_dte rd_new;
    Psommet s;
    Psommet s_new;
 
    sg_out = sg_new();
 
    /* duplication de la liste des sommets */
    sg_out->soms_sg.nb_s = sg_in->soms_sg.nb_s;
    for(s = sg_in->soms_sg.ssg; s != NULL; s = s->succ) {
      s_new = sommet_dup(s);
      s_new->succ = sg_out->soms_sg.ssg;
      sg_out->soms_sg.ssg = s_new;
    }
 
    /* duplication de la liste des rayons */
    sg_out->rays_sg.nb_v = sg_in->rays_sg.nb_v;
    for(rd = sg_in->rays_sg.vsg; rd != NULL; rd = rd->succ) {
      rd_new = ray_dte_dup(rd);
      rd_new->succ = sg_out->rays_sg.vsg;
      sg_out->rays_sg.vsg = rd_new;
    }
 
    /* duplication de la liste des droites */
    sg_out->dtes_sg.nb_v = sg_in->dtes_sg.nb_v;
    for(rd = sg_in->dtes_sg.vsg; rd != NULL; rd = rd->succ) {
      rd_new = ray_dte_dup(rd);
      rd_new->succ = sg_out->dtes_sg.vsg;
      sg_out->dtes_sg.vsg = rd_new;
    }
 
    sg_out->base = base_dup(sg_in->base);
  }
  return sg_out;
}

References type_sg::base, base_dup(), type_sg::dtes_sg, ttsg_soms::nb_s, ttsg_vects::nb_v, ray_dte_dup(), type_sg::rays_sg, sg_new(), SG_UNDEFINED, SG_UNDEFINED_P, sommet_dup(), type_sg::soms_sg, ttsg_soms::ssg, rdte::succ, typ_som::succ, and ttsg_vects::vsg.

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

Here is the call graph for this function:

Here is the caller graph for this function:

sg_egal()

bool sg_egal	(	Ptsg	sg1,
		Ptsg	sg2
	)

bool 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 434 of file sg.c.

{
    if (! egal_soms(&(sg1->soms_sg) ,&(sg2->soms_sg) ) ) return(false);
    if (sg_nbre_sommets(sg1) == 0) return(true);
    if (! egal_rd(&(sg1->rays_sg),&(sg2->rays_sg))) return(false);
    if (! egal_rd(&(sg1->dtes_sg),&(sg2->dtes_sg))) return(false);
    return(true);
}

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

Here is the call graph for this function:

sg_fprint()

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

sg_fprint_as_ddv()

void sg_fprint_as_ddv	(	FILE *	fd,
		Ptsg	sg
	)

For each coordinate

For all vertices

For all rays

For all lines

Parameters

fd	d
sg	g

Definition at line 341 of file sg.c.

{
    Pbase c = BASE_NULLE;
    int ddv = 0;
 
    fprintf(fd, "ddv(");
 
    /* For each coordinate */
    for(c=sg->base; !BASE_NULLE_P(c); c = c->succ) {
        Psommet v;
        Pray_dte r;
        Pray_dte l;
 
        /* For all vertices */
        for(v=sg_sommets(sg); v!= NULL; v = v->succ) {
            ddv |= vertex_to_direction[1+value_sign(vect_coeff(vecteur_var(c), v->vecteur))];
        }
 
        /* For all rays */
        for(r=sg_rayons(sg); r!= NULL; r = r->succ) {
            ddv |= ray_to_direction[1+value_sign(vect_coeff(vecteur_var(c), r->vecteur))];
        }
 
        /* For all lines */
        for(l=sg_droites(sg); l!= NULL; l = l->succ) {
            ddv |= line_to_direction[1+value_sign(vect_coeff(vecteur_var(c), l->vecteur))];
        }
 
        fprintf(fd, c==sg->base? "%s" : ",%s", direction_to_representation[ddv]);
    }
 
    fprintf(fd, ")");
}

References type_sg::base, BASE_NULLE, BASE_NULLE_P, direction_to_representation, fprintf(), line_to_direction, ray_to_direction, sg, sg_droites, sg_rayons, sg_sommets, rdte::succ, typ_som::succ, Svecteur::succ, 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().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_fprint_as_dense()

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 298 of file sg.c.

{
    (void) fprintf(f,"Generating system:\n");
 
    (void) fprintf(f,"%d Vert%s \n",sg_nbre_sommets(sg),
                   sg_nbre_sommets(sg)==1? "ex" : "ices");
    fprint_lsom_as_dense(f, sg_sommets(sg), b);
 
    if(sg_nbre_rayons(sg)>0) {
        (void) fprintf(f,"\n%d Ray%s \n",sg_nbre_rayons(sg),
                       sg_nbre_rayons(sg)==1? "" : "s");
        fprint_lray_dte_as_dense(f, sg_rayons(sg), b);
    }
 
    if(sg_nbre_droites(sg)>0) {
        (void) fprintf(f,"\n%d Line%s \n",sg_nbre_droites(sg),
                       sg_nbre_rayons(sg)==1? "" : "s");
        fprint_lray_dte_as_dense(f, sg_droites(sg), b);
    }
 
    (void) fprintf(f,"\nEnd of generating system ****\n");
}

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

sg_new()

Ptsg sg_new

(

void

)

Obsolete macros of Malik Imadache #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)

TSG cproto-generated files sg.c

Obsolete macros of Malik Imadache #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)

Definition at line 55 of file sg.c.

{
    Ptsg sg;
 
    sg = (Ptsg) MALLOC(sizeof(Stsg),TSG,"sg_new");
    sg->soms_sg.nb_s = 0;
    sg->soms_sg.ssg = NULL;
    sg->rays_sg.nb_v = 0;
    sg->rays_sg.vsg = NULL;
    sg->dtes_sg.nb_v = 0;
    sg->dtes_sg.vsg = NULL;
    sg->base = NULL;
    return sg;
}

References type_sg::base, type_sg::dtes_sg, MALLOC, ttsg_soms::nb_s, ttsg_vects::nb_v, type_sg::rays_sg, sg, type_sg::soms_sg, ttsg_soms::ssg, TSG, and ttsg_vects::vsg.

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

Here is the caller graph for this function:

sg_print()

void sg_print	(	Ptsg	,
		char *	*)(Variable
	)

sg_rm()

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 249 of file sg.c.

{
    sg_rm_sommets(sg);
    sg_rm_rayons(sg);
    sg_rm_droites(sg);
    base_rm(sg->base);
    FREE((char *)sg,TSG,"sg_rm");
}

References type_sg::base, base_rm, FREE, sg, sg_rm_droites(), sg_rm_rayons(), sg_rm_sommets(), and TSG.

Referenced by dependence_cone_positive(), initialize_newgen(), sg_of_sc(), and TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_rm_droites()

void sg_rm_droites

(

Ptsg

sg

)

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

Parameters

sg

g

Definition at line 233 of file sg.c.

{
    elim_tt_rd(sg->rays_sg.vsg);
    sg->rays_sg.vsg = NULL;
    sg->rays_sg.nb_v = 0;
}

References elim_tt_rd(), ttsg_vects::nb_v, type_sg::rays_sg, sg, and ttsg_vects::vsg.

Referenced by sg_rm().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_rm_rayons()

void sg_rm_rayons

(

Ptsg

sg

)

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

Parameters

sg

g

Definition at line 222 of file sg.c.

{
    elim_tt_rd(sg->rays_sg.vsg);
    sg->rays_sg.vsg = NULL;
    sg->rays_sg.nb_v = 0;
}

References elim_tt_rd(), ttsg_vects::nb_v, type_sg::rays_sg, sg, and ttsg_vects::vsg.

Referenced by sg_rm().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_rm_sommets()

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 205 of file sg.c.

{
    Psommet s,s1;
 
    for (s=sg->soms_sg.ssg; s!=NULL;) {
        s1 = s->succ;
        SOMMET_RM(s,"sg_rm_sommets");
        s = s1;
    }
    sg->soms_sg.ssg = NULL;
    sg->soms_sg.nb_s = 0;
}

References ttsg_soms::nb_s, s1, sg, SOMMET_RM, type_sg::soms_sg, ttsg_soms::ssg, and typ_som::succ.

Referenced by sg_rm().

Here is the caller graph for this function:

sg_union()

Ptsg sg_union	(	Ptsg	sg1,
		Ptsg	sg2
	)

union des sommets

union des rayons

nion des droites

Parameters

sg1	g1
sg2	g2

Definition at line 552 of file sg.c.

{
    Ptsg sg;
    bool newsommet = (sg_nbre_sommets(sg1)== 0) ? true : false;
    bool newray = (sg_nbre_rayons(sg1)== 0) ? true : false;
    bool newdte = (sg_nbre_droites(sg1)== 0) ? true : false;
    Psommet ps, ps_tmp;
    Pray_dte pr,pr_tmp;
 
    if (sg1 == NULL)    
        return (sg_dup(sg2));
    if (sg2 == NULL)
        return (sg_dup(sg1));
 
    sg = sg_dup(sg1); 
    sg->soms_sg.nb_s = sg_nbre_sommets(sg1);
    sg->rays_sg.nb_v =sg_nbre_rayons(sg1) ;
    sg->dtes_sg.nb_v = sg_nbre_droites(sg1);
    /* union des sommets */
 
    for (ps = sg->soms_sg.ssg, ps_tmp = ps; ps != NULL ;  ps_tmp = ps, ps=ps->succ)
        ;
    for (ps = sg2->soms_sg.ssg; ps != NULL; ps=ps->succ) {
        if (newsommet) {
            sg->soms_sg.ssg = ps_tmp=sommet_dup(ps);
            newsommet = false;
            sg->soms_sg.nb_s++;
        } else {
            if (!sommet_in_sg_p(ps,sg)) {
                ps_tmp->succ=sommet_dup(ps);
                ps_tmp = ps_tmp->succ; sg->soms_sg.nb_s++;
            }
        }
    }
 
    /* union des rayons */
    for (pr = sg->rays_sg.vsg, pr_tmp=pr; pr!= NULL; pr_tmp = pr, pr = pr->succ)
        ;
    for (pr = sg2->rays_sg.vsg; pr != NULL; pr=pr->succ) {
        if (newray) {
            sg->rays_sg.vsg = pr_tmp=ray_dte_dup(pr);
            newray = false;
            sg->rays_sg.nb_v++;
        } else {
            if (!ray_in_sg_p(pr,sg)) {
                pr_tmp->succ=ray_dte_dup(pr);
                pr_tmp = pr_tmp->succ;
                sg->rays_sg.nb_v++;
            }
        }
    }
 
    /*union des droites */
    for (pr = sg->dtes_sg.vsg, pr_tmp=pr; pr!= NULL; pr_tmp = pr,pr=pr->succ)
        ;
    for (pr = sg2->dtes_sg.vsg; pr != NULL; pr=pr->succ) {
        if (newdte) {
            sg->dtes_sg.vsg = pr_tmp=ray_dte_dup(pr);
            newdte = false;
            sg->dtes_sg.nb_v++;
        } else {
            if (!dte_in_sg_p(pr,sg)) {
                pr_tmp->succ=ray_dte_dup(pr);
                pr_tmp = pr_tmp->succ;
                sg->dtes_sg.nb_v++;
            }
        }
    }
    base_rm(sg->base);
    sg->base = base_union(sg1->base,sg2->base);
    return (sg); 
}

References type_sg::base, base_rm, base_union(), dte_in_sg_p(), type_sg::dtes_sg, ttsg_soms::nb_s, ttsg_vects::nb_v, ray_dte_dup(), ray_in_sg_p(), type_sg::rays_sg, sg, sg_dup(), sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sommet_dup(), sommet_in_sg_p(), type_sg::soms_sg, ttsg_soms::ssg, rdte::succ, typ_som::succ, and ttsg_vects::vsg.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_without_line()

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 132 of file sg.c.

{
    Ptsg sg_out;
    Pray_dte rd;
    Pray_dte rd_new;
    Pray_dte rd_prec;
 
    ifdebug(8) {
        (void) fprintf(stderr,"sg_without_line: begin\n");
        (void) fprintf(stderr,"sg_without_line: sg_in\n");
        sg_fprint(stderr, sg_in, variable_dump_name);
    }
 
    sg_out = sg_dup(sg_in);
 
    /* ajout des l'oppose des vecteurs directeur des droites a la liste
       des rayons */
    for(rd_prec=rd=sg_out->dtes_sg.vsg; rd!=NULL; rd_prec=rd, rd=rd->succ) {
        /* allocation et calcul du vecteur opppose */
        rd_new = ray_oppose(rd);
        /* chainage en tete de la liste des rayons */
        rd_new = sg_out->rays_sg.vsg;
        sg_out->rays_sg.vsg = rd_new;
    }
 
    /* 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 */
    if(rd_prec!=NULL) {
        /* ajout de l'ensemble des rayons a l'ensemble des droites */
        rd_prec->succ = sg_out->rays_sg.vsg;
        /* transfert de la liste des droites a la liste des rayons */
        sg_out->rays_sg.vsg = sg_out->dtes_sg.vsg;
        sg_out->dtes_sg.vsg = NULL;
        /* mise a jour des nombres de droites et de vecteurs */
        sg_out->rays_sg.nb_v += 2*(sg_out->dtes_sg.nb_v);
        sg_out->dtes_sg.nb_v = 0;
    }
 
    ifdebug(8) {
        (void) fprintf(stderr,"sg_without_line: sg_out\n");
        sg_fprint(stderr, sg_out, variable_dump_name);
        (void) fprintf(stderr,"sg_without_line: end\n");
    }
 
    return sg_out;
}

References type_sg::dtes_sg, fprintf(), ifdebug, ttsg_vects::nb_v, ray_oppose(), type_sg::rays_sg, sg_dup(), sg_fprint(), rdte::succ, variable_dump_name(), and ttsg_vects::vsg.

Here is the call graph for this function:

sommet_in_sg_p()

bool sommet_in_sg_p	(	Psommet	som,
		Ptsg	sg
	)

Parameters

som	om
sg	g

Definition at line 507 of file sg.c.

{
    Psommet ps;
    bool trouve = false;
 
    if (!SG_UNDEFINED_P(sg)) {
        for (ps = sg->soms_sg.ssg; ps != NULL && !trouve ; ps=ps->succ) {
            trouve = trouve || vect_equal(som->vecteur,ps->vecteur);
        }
    }
    return (trouve);
}

References sg, SG_UNDEFINED_P, type_sg::soms_sg, ttsg_soms::ssg, typ_som::succ, vect_equal(), and typ_som::vecteur.

Referenced by sg_union().

Here is the call graph for this function:

Here is the caller graph for this function: