sommet.h File Reference

Go to the source code of this file.

Functions

Psommet sommet_new (void)
 Warning! Do not modify this file that is automatically generated!
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;.
Psommet sommet_dup (Psommet)
 Psommet sommet_dup(Psommet s_in): allocation et copie de la valeur d'un sommet.
void sommet_rm (Psommet)
 void sommet_rm(Psommet s): desallocation complete d'une structure sommet
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
void sommet_dump (Psommet)
 void sommet_dump(Psommet s): impression d'un sommet sur stderr avec variable_dump_name()
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
void sommet_normalize (Psommet)
 void sommet_normalize(Psommet ns): normalisation des coordonnees d'un sommet par le pgcd des coordonnees et du denominateur
boolean som_in_liste (Psommet, Psommet)
 boolean som_in_liste(Psommet s, Psommet l): test de l'appartenance du sommet s a la liste de sommets l
boolean sommet_egal (Psommet, Psommet)
 boolean sommet_egal(Psommet s1, Psommet s2): test de l'egalite de representation de deux sommets
boolean egaliste_s (Psommet, Psommet *)
 boolean egaliste_s(Psommet l1, Psommet * ad_l2): test d'egalite de listes de sommets
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.
Psommet sommets_dup (Psommet)
 sommets.c
void sommets_rm (Psommet)
 void sommets_rm(Psommet ps): liberation de l'espace memoire alloue a une liste de sommets
void sommets_normalize (Psommet)
 void sommets_normalize(som) Normalisation des elements d'une liste de sommets i.e.

Function Documentation

void dbg_sommet_rm ( Psommet  ,
char *   
)

Definition at line 113 of file sommet.c.

References dbg_vect_rm(), fprintf(), FREE, SOMMET, sommet_fprint(), and variable_dump_name().

00116 {
00117     (void) fprintf(stderr,"destruction de sommet dans %s : ",f);
00118     sommet_fprint(stderr, s, variable_dump_name);
00119     dbg_vect_rm(s->vecteur,f);
00120     FREE((char *)s,SOMMET,f);
00121 }

Here is the call graph for this function:

boolean egaliste_s ( Psommet  l1,
Psommet *  ad_l2 
)

boolean 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 254 of file sommet.c.

References FALSE, NULL, sommet_egal(), typ_som::succ, and TRUE.

Referenced by egal_soms().

00256 {
00257     int egalite;
00258     Psommet eq1,eq2,eq21,eq23,*ad_aux;
00259  
00260     if (l1==(*ad_l2)) return(TRUE);
00261 
00262     /* elements pour lesquels il reste a trouver un "jumeau" dans l1 */
00263     eq2 = *ad_l2;
00264     /* adresse a laquelle il faudra raccrocher les elements de l2
00265        successivement testes */
00266     ad_aux = ad_l2;
00267 
00268     (*ad_l2) = NULL;
00269 
00270     for(eq1=l1;eq1!=NULL;eq1=eq1->succ)  {
00271         egalite = 0;
00272         for(eq21=eq2,eq23=eq2;eq21!=NULL;) {
00273             if (sommet_egal(eq21,eq1)) {
00274                 /* on a trouve un element (eq21) de eq2 egal a
00275                    l'element courant de l1; on remet donc
00276                    eq21 dans l2, en distingant 2
00277                    cas suivant qu'il est en tete de
00278                    eq2 ou pas
00279                    */
00280                 /* eq23 est le predecesseur de eq21 dans eq2
00281                    il faut le conserver pour enlever eq21
00282                    de eq2
00283                    */
00284                 if (eq21==eq2) {
00285                     eq2=eq2->succ;
00286                     eq21->succ = NULL;
00287                     (*ad_aux) = eq21;
00288                     ad_aux = &(eq21->succ);
00289                     eq21 = eq23 = eq2;
00290                 }
00291                 else {
00292                     eq23->succ = eq21->succ;
00293                     eq21->succ = NULL;
00294                     (*ad_aux) = eq21;
00295                     ad_aux = &(eq21->succ);
00296                     eq21 = eq23->succ;
00297                 }
00298                 egalite = 1;
00299                 break;
00300             }
00301             else {
00302                 /* eq21 est different de l'element de l1
00303                    qui est teste; il faut voir le reste de
00304                    la liste eq2
00305                    */
00306                 eq23 = eq21;
00307                 eq21 = eq21->succ;
00308             }
00309         }
00310         if (egalite == 0) {
00311             /* on a trouve un element de l1 qui n'a pas
00312                de "jumeau" dans l2 => reformer l2 et sortir
00313                */
00314             (* ad_aux) = eq2;
00315             return(FALSE);
00316         }
00317         else egalite = 0;
00318     }
00319     if (eq2==NULL)
00320         /* tous les elements de l1 ont un jumeau
00321            (=> l1 est inclus dans l2)
00322            si tous les elements de l2 sont jumeaux
00323            (inclusion inverse) => egalite
00324            */
00325         return(TRUE);
00326     else 
00327         /* dans le cas inverse reformer l2 et sortir */
00328         (*ad_aux) = eq2;
00329     return(FALSE);
00330 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 187 of file sommet.c.

References e, NULL, sommet_fprint_as_dense(), and typ_som::succ.

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

00191 {
00192     Psommet e;
00193     for (e = ls; e != NULL; e = e->succ) {
00194         sommet_fprint_as_dense(f, e, b);
00195     }
00196 }

Here is the call graph for this function:

Here is the caller graph for this function:

boolean som_in_liste ( Psommet  s,
Psommet  listes 
)

boolean 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 218 of file sommet.c.

References typ_som::denominateur, FALSE, NULL, s1, typ_som::succ, TRUE, vect_equal(), and typ_som::vecteur.

00221 {
00222     Psommet s1;
00223 
00224     for (s1=listes;s1!=NULL;s1=s1->succ) {
00225         if ((s1->denominateur)==(s->denominateur)) {
00226             if (vect_equal((s1->vecteur),(s->vecteur))) return(TRUE);
00227         }
00228     }
00229     return(FALSE);
00230 }

Here is the call graph for this function:

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.

Definition at line 338 of file sommet.c.

References NULL, and typ_som::succ.

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

00341 {
00342 
00343     if (som != NULL)
00344     {
00345         Psommet pred,ps1;
00346 
00347         pred = *ps;
00348         for (ps1 = pred; ps1 != NULL; pred = ps1, ps1 = ps1->succ);
00349         pred->succ = som;
00350         som->succ = NULL;
00351         *nb_som = (*nb_som) +1;
00352     }
00353 }

Here is the caller graph for this function:

void sommet_dump ( Psommet   ) 

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

Definition at line 164 of file sommet.c.

References sommet_fprint(), and variable_dump_name().

00166 {
00167     sommet_fprint(stderr, s, variable_dump_name);
00168 }

Here is the call graph for this function:

Psommet sommet_dup ( Psommet   ) 

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

Definition at line 78 of file sommet.c.

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

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

00080 {
00081     Psommet s_out;
00082 
00083     s_out = (Psommet) MALLOC(sizeof(Ssommet), SOMMET, "sommet_dup");
00084 
00085     if(s_in->eq_sat!=NULL) {
00086         (void) fprintf(stderr,
00087                        "sommet_dup: warning eq_sat is not duplicated\n");
00088     }
00089 
00090     if(s_in->denominateur==0) {
00091         (void) fprintf(stderr,"sommet_dup: denominateur nul\n");
00092         abort();
00093     }
00094 
00095     s_out = (Psommet) MALLOC(sizeof(Ssommet),SOMMET,"sommet_dup");
00096     s_out->succ = NULL;
00097     s_out->eq_sat = NULL;
00098     s_out->vecteur = vect_dup(s_in->vecteur);
00099     s_out->denominateur = s_in->denominateur;
00100 
00101     return s_out;
00102 }

Here is the call graph for this function:

Here is the caller graph for this function:

boolean sommet_egal ( Psommet  s1,
Psommet  s2 
)

boolean 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 238 of file sommet.c.

References FALSE, sommet_denominateur, and vect_equal().

Referenced by egaliste_s().

00240 {
00241     if (sommet_denominateur(s1)!=sommet_denominateur(s2))
00242         return(FALSE);
00243     else
00244         return(vect_equal(s1->vecteur,s2->vecteur));
00245 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 148 of file sommet.c.

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

Referenced by fprint_lsom_as_dense().

00152 {
00153     if(value_notone_p(s->denominateur)) {
00154         (void) fprintf(f,"denominator = ");
00155         fprint_Value(f,s->denominateur);
00156         (void) fprintf(f, "\t");
00157     }
00158     vect_fprint_as_dense(f,s->vecteur, b);
00159 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 63 of file sommet.c.

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

Referenced by mk_rn(), and polyhedron_to_sg().

00066 {
00067     Psommet s;
00068 
00069     s = sommet_new();
00070     s->denominateur = d;
00071     s->vecteur = v;
00072     return (s);
00073 }

Here is the call graph for this function:

Here is the caller graph for this function:

Psommet sommet_new ( void   ) 

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 cprotopackage 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?SOMMETsommet.c

Definition at line 47 of file sommet.c.

References typ_som::denominateur, typ_som::eq_sat, MALLOC, NULL, s, 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().

00048 {
00049     Psommet s;
00050 
00051     s = (Psommet) MALLOC(sizeof(Ssommet), SOMMET, "sommet_dup");
00052     s->denominateur =0;
00053     s->vecteur = NULL;
00054     s->eq_sat =NULL;
00055     s->succ = NULL;
00056     return (s);
00057 }

Here is the caller graph for this function:

void sommet_normalize ( Psommet   ) 

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

Definition at line 201 of file sommet.c.

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

Referenced by sommets_normalize().

00203 {
00204     Value div = vect_pgcd_all(ns->vecteur);
00205 
00206     assert(value_pos_p(div));
00207     div = pgcd(div, ns->denominateur);
00208     value_division(ns->denominateur,div);
00209     (void) vect_div(ns->vecteur, div);
00210 }

Here is the call graph for this function:

Here is the caller graph for this function:

void sommet_rm ( Psommet   ) 

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

Definition at line 106 of file sommet.c.

References FREE, SOMMET, and vect_rm().

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

Here is the call graph for this function:

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 45 of file sommets.c.

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

00047 {
00048 
00049     Psommet som1,som2;
00050     /* pointeur vers le dernier element de la liste*/
00051     Psommet pred;
00052     /* pointeur vers le premier element de la liste*/
00053     Psommet debut = NULL;
00054 
00055 
00056 #ifdef TRACE
00057     printf(" ***** duplication du systeme \n");
00058 #endif
00059     if (som)
00060     {
00061         som2 = sommet_dup(som);
00062         debut = som2;
00063         pred = som2;
00064         for (som1 = som->succ; som1 != NULL; som1 = som1->succ)
00065         {
00066 
00067             som2 = sommet_dup(som1);
00068             pred->succ = som2;
00069             pred = som2;
00070         };
00071     };
00072     return (debut);
00073 }

Here is the call graph for this function:

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 104 of file sommets.c.

References NULL, sommet_normalize(), and typ_som::succ.

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

00106 {
00107     Psommet ps;
00108     for (ps = som;ps!= NULL; ps= ps->succ)
00109         sommet_normalize(ps);
00110 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 79 of file sommets.c.

References typ_som::eq_sat, FREE, NULL, 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().

00081 {
00082     Psommet p1,p2;
00083 
00084 #ifdef TRACE2
00085     printf(" ***** erase systeme \n");
00086 #endif  
00087 
00088     for (p2 = ps;p2 != NULL;)
00089     {
00090         p1 = p2->succ;
00091         FREE((int *)p2->eq_sat,INTEGER,"sommets_rm");
00092         vect_rm(p2->vecteur);
00093         FREE((Psommet)p2,SOMMET,"sommets_rm");
00094         p2 = p1;
00095     }
00096 
00097 }

Here is the call graph for this function:

Here is the caller graph for this function:

Generated by  doxygen 1.6.2-20100208