sg.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"

Include dependency graph for sg.c:

Go to the source code of this file.

Macros
#define	ifdebug(n)   if((n)<sg_debug_level)
#define	MALLOC(s, t, f)   malloc(s)
#define	FREE(p, t, f)   free(p)
#define	LESSER_DIRECTION   4
	Print a generating system as a dependence direction vector. More...
#define	GREATER_DIRECTION   1
#define	ZERO_DIRECTION   2
#define	ANY_DIRECTION   7
#define	NO_DIRECTION   0

Functions
Ptsg	sg_new ()
	Ptsg sg_new(): allocation d'un systeme generateur et initialisation a la valeur ensemble vide. More...
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. More...
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. More...
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. More...
void	sg_rm_sommets (Ptsg sg)
	void sg_rm_sommets(Ptsg sg): desallocation d'une liste de sommets d'un systeme generateur More...
void	sg_rm_rayons (Ptsg sg)
	void sg_rm_rayons(Ptsg sg): desallocation d'une liste de rayons d'un systeme generateur More...
void	sg_rm_droites (Ptsg sg)
	void sg_rm_droites(Ptsg sg): desallocation d'une liste de droites d'un systeme generateur More...
void	sg_rm (Ptsg sg)
	void sg_rm(Ptsg sg): liberation de l'espace memoire occupe par un systeme generateur More...
void	sg_fprint (FILE *f, Ptsg sg, char *(*nom_var)(Variable))
	void sg_fprint(FILE * f, Ptsg sg, char * (*nom_var)()): impression d'un systeme generateur More...
void	sg_print (Ptsg sg, char *(*nom_var)(Variable))
	For debugging. More...
void	sg_dump (Ptsg sg)
	For debugging. More...
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 More...
void	sg_fprint_as_ddv (FILE *fd, Ptsg sg)
static bool	egal_soms (Ptsg_soms sgs1, Ptsg_soms sgs2)
	bool egal_soms(Ptsg_soms sgs1, Ptsg_soms sgs2): test de l'egalite de deux listes de sommets associees a un systeme generateur More...
static bool	egal_rd (Ptsg_vects rdgs1, Ptsg_vects rdgs2)
	bool egal_rd(Ptsg_vects rdgs1, Ptsg_vects rdgs2): test de de l'egalite des deux objets representes par des structures tsg_vects More...
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 More...
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;. More...
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. More...
bool	sommet_in_sg_p (Psommet som, Ptsg sg)
bool	ray_in_sg_p (Pray_dte ray, Ptsg sg)
bool	dte_in_sg_p (Pray_dte dte, Ptsg sg)
Ptsg	sg_union (Ptsg sg1, Ptsg sg2)

Variables
static int	sg_debug_level = 0
	package pour la structure de donnees tsg (systeme generateur) et pour les deux structures de donnees inclues tsg_vects et tsg_soms qui representent les listes de rayons, de droites et de sommets d'un systeme generateur More...
static int	vertex_to_direction [3] = {LESSER_DIRECTION, ZERO_DIRECTION, GREATER_DIRECTION}
static int	ray_to_direction [3] = {LESSER_DIRECTION, NO_DIRECTION, GREATER_DIRECTION}
static int	line_to_direction [3] = {ANY_DIRECTION, NO_DIRECTION, ANY_DIRECTION}
static char *	direction_to_representation [8] = {"?", "<", "=", "<=", ">", "*", ">=", "*"}

Macro Definition Documentation

ANY_DIRECTION

#define ANY_DIRECTION   7

Definition at line 329 of file sg.c.

FREE

#define FREE	(		p,
			t,
			f
	)		free(p)

Definition at line 50 of file sg.c.

GREATER_DIRECTION

#define GREATER_DIRECTION   1

Definition at line 327 of file sg.c.

ifdebug

#define ifdebug

(

n

)

if((n)<sg_debug_level)

Definition at line 47 of file sg.c.

LESSER_DIRECTION

#define LESSER_DIRECTION   4

Print a generating system as a dependence direction vector.

Definition at line 326 of file sg.c.

MALLOC

#define MALLOC	(		s,
			t,
			f
	)		malloc(s)

Definition at line 49 of file sg.c.

NO_DIRECTION

#define NO_DIRECTION   0

Definition at line 330 of file sg.c.

ZERO_DIRECTION

#define ZERO_DIRECTION   2

Definition at line 328 of file sg.c.

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:

egal_rd()

static bool egal_rd ( Ptsg_vects  rdgs1, Ptsg_vects  rdgs2  )

static

bool egal_rd(Ptsg_vects rdgs1, Ptsg_vects rdgs2): test de de l'egalite des deux objets representes par des structures tsg_vects

Ne doit servir que dans sg_egal()

Definition at line 410 of file sg.c.

{
        int result;
        if (rdgs1->nb_v != rdgs2->nb_v) return(0);
        result = egaliste_rd(rdgs1->vsg,&(rdgs2->vsg));
        return(result);
}

References egaliste_rd().

Referenced by sg_egal().

Here is the call graph for this function:

Here is the caller graph for this function:

egal_soms()

static bool egal_soms ( Ptsg_soms  sgs1, Ptsg_soms  sgs2  )

static

bool egal_soms(Ptsg_soms sgs1, Ptsg_soms sgs2): test de l'egalite de deux listes de sommets associees a un systeme generateur

Malik: on notera que deux polyedres non faisables (nb sommets = 0) seront identiques quelque soit la representation du SC

Francois: comme la structure de donnees tsg_soms n'existe jamais "libre" mais n'est toujours qu'une partie de la structure tsg, je ne pense pas qu'il soit necessaire de rendre cette routine visible de l'exterieur

Definition at line 396 of file sg.c.

{
        if (sgs1->nb_s != sgs2->nb_s) return(false);
        if (sgs1->nb_s == 0) return(true);
        return(egaliste_s(sgs1->ssg,&(sgs2->ssg)));
}

References egaliste_s().

Referenced by sg_egal().

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 *	f,
		Ptsg	sg,
		char *(*)(Variable)	nom_var
	)

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

Definition at line 262 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(f, sg_sommets(sg), nom_var);
    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(f, sg_rayons(sg), nom_var);
    }
    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(f, sg_droites(sg), nom_var);
    }
    (void) fprintf(f,"\nEnd of generating system ****\n");
}

References f(), fprint_lray_dte(), fprint_lsom(), fprintf(), nom_var, sg, sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, and sg_sommets.

Referenced by adg_print_graph(), main(), mk_rn(), sg_print(), and sg_without_line().

Here is the call graph for this function:

Here is the caller graph for this function:

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

)

Ptsg sg_new(): allocation d'un systeme generateur et initialisation a la valeur ensemble vide.

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	sg,
		char *(*)(Variable)	nom_var
	)

For debugging.

Definition at line 282 of file sg.c.

{
  sg_fprint(stderr, sg, nom_var);
}

References nom_var, sg, and sg_fprint().

Referenced by sg_dump().

Here is the call graph for this function:

Here is the caller graph for this function:

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:

Variable Documentation

direction_to_representation

char* direction_to_representation[8] = {"?", "<", "=", "<=", ">", "*", ">=", "*"}

static

Definition at line 338 of file sg.c.

Referenced by sg_fprint_as_ddv().

line_to_direction

int line_to_direction[3] = {ANY_DIRECTION, NO_DIRECTION, ANY_DIRECTION}

static

Definition at line 336 of file sg.c.

Referenced by sg_fprint_as_ddv().

ray_to_direction

int ray_to_direction[3] = {LESSER_DIRECTION, NO_DIRECTION, GREATER_DIRECTION}

static

Definition at line 334 of file sg.c.

Referenced by sg_fprint_as_ddv().

sg_debug_level

int sg_debug_level = 0

static

package pour la structure de donnees tsg (systeme generateur) et pour les deux structures de donnees inclues tsg_vects et tsg_soms qui representent les listes de rayons, de droites et de sommets d'un systeme generateur

Francois Irigoin

Definition at line 46 of file sg.c.

vertex_to_direction

int vertex_to_direction[3] = {LESSER_DIRECTION, ZERO_DIRECTION, GREATER_DIRECTION}

static

Definition at line 332 of file sg.c.

Referenced by sg_fprint_as_ddv().