Data Structures
struct	typ_som
	structure de donnees Sommet More...

Macros
#define	SOMMET 1004
	Warning! Do not modify this file that is automatically generated! More...

#define	print_som(s) sommet_fprint(stdout,s)

#define	print_lsom(ls) fprint_lsom(stdout,ls)

#define	VERSION_FINALE

#define	SOMMET_RM(s, function_name) sommet_rm(s)

#define	sommet_denominateur(s) ((s)->denominateur)
	macros d'acces More...

Typedefs
typedef struct typ_som *	Psommet
	structure de donnees Sommet More...

typedef struct typ_som	Ssommet

Functions
Psommet	sommet_new (void)
	SOMMET. More...

Psommet	sommet_make (Value, Pvecteur)
	Psommet sommet_make(int d, Pvecteur v): allocation et initialisation d'un sommet de denominateur d et de vecteur v; le vecteur v est utilise directement; ca peut introduire du sharing;. More...

Psommet	sommet_dup (Psommet)
	Psommet sommet_dup(Psommet s_in): allocation et copie de la valeur d'un sommet. More...

void	sommet_rm (Psommet)
	void sommet_rm(Psommet s): desallocation complete d'une structure sommet More...

void	dbg_sommet_rm (Psommet, char *)

void	sommet_fprint (FILE , Psommet, char (*)(Variable))

void	sommet_fprint_as_dense (FILE *, Psommet, Pbase)
	void sommet_fprint_as_dense(FILE * f, Psommet s): impression d'un sommet More...

void	sommet_dump (Psommet)
	void sommet_dump(Psommet s): impression d'un sommet sur stderr avec variable_debug_name() More...

void	fprint_lsom (FILE , Psommet, char (*)(Variable))

void	fprint_lsom_as_dense (FILE *, Psommet, Pbase)
	void fprint_lsom_as_dense(FILE * f, Psommet s): impression d'une liste de sommets More...

void	sommet_normalize (Psommet)
	void sommet_normalize(Psommet ns): normalisation des coordonnees d'un sommet par le pgcd des coordonnees et du denominateur More...

bool	som_in_liste (Psommet, Psommet)
	bool som_in_liste(Psommet s, Psommet l): test de l'appartenance du sommet s a la liste de sommets l More...

bool	sommet_egal (Psommet, Psommet)
	bool sommet_egal(Psommet s1, Psommet s2): test de l'egalite de representation de deux sommets More...

bool	egaliste_s (Psommet, Psommet *)
	bool egaliste_s(Psommet l1, Psommet * ad_l2): test d'egalite de listes de sommets More...

void	sommet_add (Psommet , Psommet, int )
	void sommet_add(Psommet ps, Psommet som, int nb_soms): Ajout d'un sommet a une liste de sommets Le sommet est ajoute a la fin de la liste. More...

Psommet	sommets_dup (Psommet)
	sommets.c More...

void	sommets_rm (Psommet)
	void sommets_rm(Psommet ps): liberation de l'espace memoire alloue a une liste de sommets More...

void	sommets_normalize (Psommet)
	void sommets_normalize(som) Normalisation des elements d'une liste de sommets i.e. More...

Macro Definition Documentation

◆ print_lsom

#define print_lsom ( ls ) fprint_lsom(stdout,ls)

Definition at line 81 of file sommet.h.

◆ print_som

#define print_som ( s ) sommet_fprint(stdout,s)

Definition at line 79 of file sommet.h.

◆ SOMMET

#define SOMMET 1004

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

Modify src/Libs/sommet/sommet-local.h instead, to add your own modifications. header file built by cproto sommet-local.h package sommet: structure de donnees representant les sommets d'un systeme generateur; elle contient:

le vecteur correspondant, a un coefficient multiplicatif pret qui le rend entier,
son denominateur,
un eventuel tableau de saturation (par rapport a une liste implicite de contraintes),
le chainage vers les autres rayons ou droites.

Francois Irigoin, Mai 1989

Cette structure de donnees est aussi utilisee dans plint.dir pour representer la fonction economique, les contraintes lineaires et les systemes de contraintes lineaires.

FI: commentaires a completer par Corinne, declaration d'un type synonyme pour eviter les conflits? valeur numerique utilise pour flagger les structures de donnees de type sommet

Definition at line 56 of file sommet.h.

◆ sommet_denominateur

#define sommet_denominateur ( s ) ((s)->denominateur)

macros d'acces

int sommet_denominateur(Psommet): denominateur des coordonnees d'un sommet; ex den_of()

Definition at line 95 of file sommet.h.

◆ SOMMET_RM

#define SOMMET_RM	(	s,
		function_name
	)	sommet_rm(s)

Definition at line 85 of file sommet.h.

◆ VERSION_FINALE

#define VERSION_FINALE

Definition at line 83 of file sommet.h.

Typedef Documentation

◆ Psommet

typedef struct typ_som * Psommet

structure de donnees Sommet

eq_sat: eventuel tableau des saturations du sommets par rapport a un eventuel systeme de contraintes; inutilisable quand on ne connait pas le nombre de contraintes, egalites ou inegalites
vecteur: coordonnees entieres du sommet, a un coefficient multiplicatif pres; l'inverse de ce coefficient est donne par le champ suivant
denominateur: coefficient permettant de garder les coordonnees du sommet sous forme rationnelle; les numerateurs des coordonnees se trouvent dans "vecteur"; le denominateur est unique, pour le sommet, i.e. c'est le PGCD des coordonnees; le denominateur doit toujours etre strictement positif
succ: pointeur vers le sommet suivant; on s'interesse a l'ensemble des sommets du systeme generateur plutot qu'a un sommet particulier

◆ Ssommet

typedef struct typ_som Ssommet

Function Documentation

◆ dbg_sommet_rm()

void dbg_sommet_rm	(	Psommet	s,
		char *	f
	)

Definition at line 117 of file sommet.c.

 {
     (void) fprintf(stderr,"destruction de sommet dans %s : ",f);
     sommet_fprint(stderr, s, variable_debug_name);
     dbg_vect_rm(s->vecteur,f);
     FREE((char *)s,SOMMET,f);
 }

References dbg_vect_rm(), f(), fprintf(), FREE, SOMMET, sommet_fprint(), and variable_debug_name.

Here is the call graph for this function:

◆ egaliste_s()

bool egaliste_s	(	Psommet	l1,
		Psommet *	ad_l2
	)

bool egaliste_s(Psommet l1, Psommet * ad_l2): test d'egalite de listes de sommets

 nous proposons un test direct au lieu d'un test en deux etapes 
 d'inclusion dans les deux sens; ceci justifie le second parametre
 qui est l'adresse du pointeur de liste (Malik Imadache)

elements pour lesquels il reste a trouver un "jumeau" dans l1

adresse a laquelle il faudra raccrocher les elements de l2 successivement testes

on a trouve un element (eq21) de eq2 egal a l'element courant de l1; on remet donc eq21 dans l2, en distingant 2 cas suivant qu'il est en tete de eq2 ou pas

eq23 est le predecesseur de eq21 dans eq2 il faut le conserver pour enlever eq21 de eq2

eq21 est different de l'element de l1 qui est teste; il faut voir le reste de la liste eq2

on a trouve un element de l1 qui n'a pas de "jumeau" dans l2 => reformer l2 et sortir

tous les elements de l1 ont un jumeau (=> l1 est inclus dans l2) si tous les elements de l2 sont jumeaux (inclusion inverse) => egalite

dans le cas inverse reformer l2 et sortir

Parameters

l1	1
ad_l2	d_l2

Definition at line 258 of file sommet.c.

 {
     int egalite;
     Psommet eq1,eq2,eq21,eq23,*ad_aux;
  
     if (l1==(*ad_l2)) return(true);
  
     /* elements pour lesquels il reste a trouver un "jumeau" dans l1 */
     eq2 = *ad_l2;
     /* adresse a laquelle il faudra raccrocher les elements de l2
        successivement testes */
     ad_aux = ad_l2;
  
     (*ad_l2) = NULL;
  
     for(eq1=l1;eq1!=NULL;eq1=eq1->succ)  {
         egalite = 0;
         for(eq21=eq2,eq23=eq2;eq21!=NULL;) {
             if (sommet_egal(eq21,eq1)) {
                 /* on a trouve un element (eq21) de eq2 egal a
                    l'element courant de l1; on remet donc
                    eq21 dans l2, en distingant 2
                    cas suivant qu'il est en tete de
                    eq2 ou pas
                    */
                 /* eq23 est le predecesseur de eq21 dans eq2
                    il faut le conserver pour enlever eq21
                    de eq2
                    */
                 if (eq21==eq2) {
                     eq2=eq2->succ;
                     eq21->succ = NULL;
                     (*ad_aux) = eq21;
                     ad_aux = &(eq21->succ);
                     eq21 = eq23 = eq2;
                 }
                 else {
                     eq23->succ = eq21->succ;
                     eq21->succ = NULL;
                     (*ad_aux) = eq21;
                     ad_aux = &(eq21->succ);
                     eq21 = eq23->succ;
                 }
                 egalite = 1;
                 break;
             }
             else {
                 /* eq21 est different de l'element de l1
                    qui est teste; il faut voir le reste de
                    la liste eq2
                    */
                 eq23 = eq21;
                 eq21 = eq21->succ;
             }
         }
         if (egalite == 0) {
             /* on a trouve un element de l1 qui n'a pas
                de "jumeau" dans l2 => reformer l2 et sortir
                */
             (* ad_aux) = eq2;
             return(false);
         }
         else egalite = 0;
     }
     if (eq2==NULL)
         /* tous les elements de l1 ont un jumeau
            (=> l1 est inclus dans l2)
            si tous les elements de l2 sont jumeaux
            (inclusion inverse) => egalite
            */
         return(true);
     else 
         /* dans le cas inverse reformer l2 et sortir */
         (*ad_aux) = eq2;
     return(false);
 }

References sommet_egal(), and typ_som::succ.

Referenced by egal_soms().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fprint_lsom()

void fprint_lsom	(	FILE *	,
		Psommet	,
		char *	*)(Variable
	)

◆ fprint_lsom_as_dense()

void fprint_lsom_as_dense	(	FILE *	f,
		Psommet	ls,
		Pbase	b
	)

void fprint_lsom_as_dense(FILE * f, Psommet s): impression d'une liste de sommets

Parameters

ls s

Definition at line 191 of file sommet.c.

 {
     Psommet e;
     for (e = ls; e != NULL; e = e->succ) {
         sommet_fprint_as_dense(f, e, b);
     }
 }

References f(), sommet_fprint_as_dense(), and typ_som::succ.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ som_in_liste()

bool som_in_liste	(	Psommet	s,
		Psommet	listes
	)

bool som_in_liste(Psommet s, Psommet l): test de l'appartenance du sommet s a la liste de sommets l

Les coordonnees du sommet s et des sommets de la liste l sont supposees normalisees (fractions reduites)

Parameters

listes istes

Definition at line 222 of file sommet.c.

 {
     Psommet s1;
  
     for (s1=listes;s1!=NULL;s1=s1->succ) {
         if ((s1->denominateur)==(s->denominateur)) {
             if (vect_equal((s1->vecteur),(s->vecteur))) return(true);
         }
     }
     return(false);
 }

References typ_som::denominateur, s1, vect_equal(), and typ_som::vecteur.

Here is the call graph for this function:

◆ sommet_add()

void sommet_add	(	Psommet *	ps,
		Psommet	som,
		int *	nb_som
	)

void sommet_add(Psommet *ps, Psommet som, int *nb_soms): Ajout d'un sommet a une liste de sommets Le sommet est ajoute a la fin de la liste.

Parameters

ps	s
som	om
nb_som	b_som

Definition at line 342 of file sommet.c.

 {
  
     if (som != NULL)
     {
         Psommet pred,ps1;
  
         pred = *ps;
         for (ps1 = pred; ps1 != NULL; pred = ps1, ps1 = ps1->succ);
         pred->succ = som;
         som->succ = NULL;
         *nb_som = (*nb_som) +1;
     }
 }

References typ_som::succ.

Referenced by eq_in_ineq(), plint_degen(), and plint_pas().

Here is the caller graph for this function:

◆ sommet_dump()

void sommet_dump ( Psommet s )

void sommet_dump(Psommet s): impression d'un sommet sur stderr avec variable_debug_name()

Definition at line 168 of file sommet.c.

 {
     sommet_fprint(stderr, s, variable_debug_name);
 }

References sommet_fprint(), and variable_debug_name.

Here is the call graph for this function:

◆ sommet_dup()

Psommet sommet_dup ( Psommet s_in )

Psommet sommet_dup(Psommet s_in): allocation et copie de la valeur d'un sommet.

Parameters

s_in _in

Definition at line 82 of file sommet.c.

 {
     Psommet s_out;
  
     s_out = (Psommet) MALLOC(sizeof(Ssommet), SOMMET, "sommet_dup");
  
     if(s_in->eq_sat!=NULL) {
         (void) fprintf(stderr,
                        "sommet_dup: warning eq_sat is not duplicated\n");
     }
  
     if(s_in->denominateur==0) {
         (void) fprintf(stderr,"sommet_dup: denominateur nul\n");
         abort();
     }
  
     s_out = (Psommet) MALLOC(sizeof(Ssommet),SOMMET,"sommet_dup");
     s_out->succ = NULL;
     s_out->eq_sat = NULL;
     s_out->vecteur = vect_dup(s_in->vecteur);
     s_out->denominateur = s_in->denominateur;
  
     return s_out;
 }

References abort, typ_som::denominateur, typ_som::eq_sat, fprintf(), MALLOC, SOMMET, typ_som::succ, vect_dup(), and typ_som::vecteur.

Referenced by sg_dup(), sg_union(), sommets_dup(), and sommets_dupc().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_egal()

bool sommet_egal	(	Psommet	s1,
		Psommet	s2
	)

bool sommet_egal(Psommet s1, Psommet s2): test de l'egalite de representation de deux sommets

Il faut en normaliser les coordonnees d'abord si on veut une egalite de valeur

Parameters

s1	1
s2	2

Definition at line 242 of file sommet.c.

 {
     if (sommet_denominateur(s1)!=sommet_denominateur(s2))
         return(false);
     else
         return(vect_equal(s1->vecteur,s2->vecteur));
 }

References s1, sommet_denominateur, and vect_equal().

Referenced by egaliste_s().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_fprint()

void sommet_fprint	(	FILE *	,
		Psommet	,
		char *	*)(Variable
	)

◆ sommet_fprint_as_dense()

void sommet_fprint_as_dense	(	FILE *	f,
		Psommet	s,
		Pbase	b
	)

void sommet_fprint_as_dense(FILE * f, Psommet s): impression d'un sommet

Definition at line 152 of file sommet.c.

 {
     if(value_notone_p(s->denominateur)) {
         (void) fprintf(f,"denominator = ");
         fprint_Value(f,s->denominateur);
         (void) fprintf(f, "\t");
     }
     vect_fprint_as_dense(f,s->vecteur, b);
 }

References typ_som::denominateur, f(), fprint_Value(), fprintf(), value_notone_p, vect_fprint_as_dense(), and typ_som::vecteur.

Referenced by fprint_lsom_as_dense().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_make()

Psommet sommet_make	(	Value	d,
		Pvecteur	v
	)

Psommet sommet_make(int d, Pvecteur v): allocation et initialisation d'un sommet de denominateur d et de vecteur v; le vecteur v est utilise directement; ca peut introduire du sharing;.

Definition at line 67 of file sommet.c.

 {
     Psommet s;
  
     s = sommet_new();
     s->denominateur = d;
     s->vecteur = v;
     return (s);
 }

References typ_som::denominateur, sommet_new(), and typ_som::vecteur.

Referenced by mk_rn(), and sg_of_rays().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_new()

Psommet sommet_new ( void )

SOMMET.

cproto-generated files sommet.c

SOMMET.

Definition at line 51 of file sommet.c.

 {
     Psommet s;
  
     s = (Psommet) MALLOC(sizeof(Ssommet), SOMMET, "sommet_dup");
     s->denominateur =0;
     s->vecteur = NULL;
     s->eq_sat =NULL;
     s->succ = NULL;
     return (s);
 }

References typ_som::denominateur, typ_som::eq_sat, MALLOC, SOMMET, typ_som::succ, and typ_som::vecteur.

Referenced by fonct_init(), fonct_max(), fonct_max_all(), fonct_max_d(), fonct_min(), fonct_min_all(), fonct_min_d(), fonct_read(), and sommet_make().

Here is the caller graph for this function:

◆ sommet_normalize()

void sommet_normalize ( Psommet ns )

void sommet_normalize(Psommet ns): normalisation des coordonnees d'un sommet par le pgcd des coordonnees et du denominateur

Parameters

ns s

Definition at line 205 of file sommet.c.

 {
     Value div = vect_pgcd_all(ns->vecteur);
  
     assert(value_pos_p(div));
     div = pgcd(div, ns->denominateur);
     value_division(ns->denominateur,div);
     (void) vect_div(ns->vecteur, div);
 }

References assert, pgcd, value_division, value_pos_p, vect_div(), and vect_pgcd_all().

Referenced by sommets_normalize().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_rm()

void sommet_rm ( Psommet s )

void sommet_rm(Psommet s): desallocation complete d'une structure sommet

Definition at line 110 of file sommet.c.

 {
     vect_rm(s->vecteur);
     FREE((char *)s,SOMMET,"sommet_rm");
 }

References FREE, SOMMET, and vect_rm().

Here is the call graph for this function:

◆ sommets_dup()

Psommet sommets_dup ( Psommet som )

sommets.c

pointeur vers le dernier element de la liste

pointeur vers le premier element de la liste

Parameters

som om

Definition at line 49 of file sommets.c.

 {
  
     Psommet som1,som2;
     /* pointeur vers le dernier element de la liste*/
     Psommet pred;
     /* pointeur vers le premier element de la liste*/
     Psommet debut = NULL;
  
  
 #ifdef TRACE
     printf(" ***** duplication du systeme \n");
 #endif
     if (som)
     {
         som2 = sommet_dup(som);
         debut = som2;
         pred = som2;
         for (som1 = som->succ; som1 != NULL; som1 = som1->succ)
         {
  
             som2 = sommet_dup(som1);
             pred->succ = som2;
             pred = som2;
         };
     };
     return (debut);
 }

References printf(), sommet_dup(), and typ_som::succ.

Here is the call graph for this function:

◆ sommets_normalize()

void sommets_normalize ( Psommet som )

void sommets_normalize(som) Normalisation des elements d'une liste de sommets i.e.

division par le pgcd de tous les elements.

Parameters

som om

Definition at line 108 of file sommets.c.

 {
     Psommet ps;
     for (ps = som;ps!= NULL; ps= ps->succ)
         sommet_normalize(ps);
 }

References sommet_normalize(), and typ_som::succ.

Referenced by eq_in_ineq(), pivoter(), and primal_pivot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommets_rm()

void sommets_rm ( Psommet ps )

void sommets_rm(Psommet ps): liberation de l'espace memoire alloue a une liste de sommets

Parameters

ps s

Definition at line 83 of file sommets.c.

 {
     Psommet p1,p2;
  
 #ifdef TRACE2
     printf(" ***** erase systeme \n");
 #endif  
  
     for (p2 = ps;p2 != NULL;)
     {
         p1 = p2->succ;
         FREE((int *)p2->eq_sat,INTEGER,"sommets_rm");
         vect_rm(p2->vecteur);
         FREE((Psommet)p2,SOMMET,"sommets_rm");
         p2 = p1;
     }
  
 }

References typ_som::eq_sat, FREE, printf(), SOMMET, typ_som::succ, vect_rm(), and typ_som::vecteur.

Referenced by dual_pivot(), dual_pivot_pas(), find_eg(), gomory_eq(), plint(), plint_degen(), plint_pas(), plreal(), primal(), primal_pivot(), and primal_positive().

Here is the call graph for this function:

Here is the caller graph for this function:

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ print_lsom

◆ print_som

◆ SOMMET

◆ sommet_denominateur

◆ SOMMET_RM

◆ VERSION_FINALE

Typedef Documentation

◆ Psommet

◆ Ssommet

Function Documentation

◆ dbg_sommet_rm()

◆ egaliste_s()

◆ fprint_lsom()

◆ fprint_lsom_as_dense()

◆ som_in_liste()

◆ sommet_add()

◆ sommet_dump()

◆ sommet_dup()

◆ sommet_egal()

◆ sommet_fprint()

◆ sommet_fprint_as_dense()

◆ sommet_make()

◆ sommet_new()

◆ sommet_normalize()

◆ sommet_rm()

◆ sommets_dup()

◆ sommets_normalize()

◆ sommets_rm()