Algorithmique Avancée 2023

Graphes

1. Note
   

   L'essentiel de ce cours est présenté par Benjamin Dupont et est donc présent sur sa page de cours

2. Préparation
   1. Arbres binaires
      Commençons par une déclaration et une construction :

      /* Arbres binaires tout simplement */ #include <stdio.h> #include <stdlib.h> #include <time.h> struct noeud { int num; float val; struct noeud * sg; struct noeud * sd; } ; typedef struct noeud noeud; typedef struct noeud * arbre; void afficharbre (arbre) ; arbre ajout (arbre a, int v, float x) { arbre new; int rande; if (! a) { new = (arbre) malloc (sizeof (noeud)); new->num = v; new->val = x; new->sg = (arbre) 0; new->sd = (arbre) 0; return new; } rande = rand (); printf(" insere %d en %d avec %2d\n", v, a->num, rande %10); if (rande & 0x01) { /* on le met à gauche*/ if (! (a->sg)) { /* s’il ny a pas de fils gauche */ a->sg = (arbre) malloc (sizeof (noeud)); a->sg->num = v; a->sg->val = x; a->sg->sg = (arbre) 0; a->sg->sd = (arbre) 0; return a; } a->sg = ajout(a->sg, v, x); return a; } /* on le met donc a droite*/ if (! (a->sd)) { /* s’il ny a pas de fils droit */ a->sd = (arbre) malloc (sizeof (noeud)); a->sd->num = v; a->sd->val = x; a->sd->sg = (arbre) 0; a->sd->sd = (arbre) 0; return a; } a->sd = ajout(a->sd, v, x); return a; } arbre creation (int n) { arbre a; float x, y; x = 1.5; y = 0.21; a = (arbre) 0; /* srand(time(NULL)); */ while (n--) { a = ajout (a, n, x); printf("\n"); x += y; y += 0.06; if (x > 3.0 || x < -2.0) { y = - y; } } return a; } void afficharbre (arbre a) { if (a) { afficharbre (a->sg); printf("%d %3.2f ", a->num, a->val); afficharbre (a->sd); } } void blancs (int n) { while (n--) printf(" "); } void voisarbre (arbre a, int nbb) { if (a) { voisarbre (a->sg, nbb + 1); blancs (nbb); printf(" %2d %d %3.2f\n", nbb, a->num, a->val); voisarbre (a->sd, nbb + 1); } } int main () { int n; arbre a, b; n = 20; a = creation (n); afficharbre (a); printf("\n\n"); voisarbre (a,0); }

      Vous pouvez maintenant :
      1. Chercher le nombre de noeuds d’un tel arbre.
      2. Faire une fonction qui renvoie 1 si une valeur appartient à l’arbre.
      3. Faire une fonction qui renvoie le noeud dont la valeur est le second paramètre.
      4. Faire une fonction qui renvoie la profondeur d’un certain noeud dans l’arbre.
      5. Faire une fonction qui range l’arbre, c’est-à-dire que pour tout sommet, ses successeurs droits ont des valeurs plus petites et tous ses successeurs gauches ont des valeurs supérieures ou égales.

   2. Arbres binaires
      

   typedef struct paire { int num; float val; } paire_t; typedef struct arbrebv { int nbn; paire_t * vec; } arbrebv_t; void afficharbrevec (arbrebv_t, int) ; arbrebv_t creeretremplir (int n) { /* n est le nombre de noeuds */ arbrebv_t a; int i, nbs, nbcases, num; float x, y; x = 1.5; y = 0.21; nbs = n; nbcases = (n << 1) + 1; num = nbcases; a.nbn = n; a.vec = malloc (nbcases * sizeof(paire_t)); assert (a.vec); for (i = 0; i < nbs; i++) { a.vec[i].num = num; a.vec[i].val = x; if (i & 0x01) num++; else num -= 3; x += y; y += 0.06; if (x > 3.0 || x < -2.0) y = - y; } for (i = nbs; i < nbcases; i++) { a.vec[i].num = INT_MIN; a.vec[i].val = 0.0; } return a; } void afficharbrevec (arbrebv_t a, int noeud) { int i; if (noeud > a.nbn) return; i = (noeud << 1) + 1; afficharbrevec ( a, i) ; printf("%5d %5.3f\n", a.vec[noeud].num, a.vec[noeud].val); afficharbrevec ( a, i+1) ; }

   Vous devez faire les mêmes exercices avec cette structure et l‘arbre rempli ainsi.
   3. Arbres n-aires
      Voici une déclaration (en l’occurence le fichier header) :

      #include <stdio.h> #include <stdlib.h> #define NBN 4 struct noeud { int nb; float val; struct noeud * fils [NBN]; } ; typedef struct noeud noeud; typedef struct noeud * arbre; typedef unsigned int uint; arbre consarb (int); arbre addarb (int, arbre); void afficharbre (arbre); void afficharb (arbre, uint); uint occur (int, arbre), occurv (float, arbre);

      Puis une fonction permettant de remplir un tel arbre, ici, simplement quadratique.

      #include "arb.h" float calcul (int n) { static float v = 1.0; switch (n%3) { case 0: v += 0.5; break; case 1: v += 0.5; break; case 2: v = 1.0; } return v; } arbre consarb (int n) { arbre racine, a; int i, nn; if (!n) { return NULL; } nn = n; racine = (arbre) malloc (sizeof(noeud)); racine->nb = nn; racine->val = calcul(n); for (i=0; i < NBN; i++) racine->fils[i] = NULL; while (--nn) { racine = addarb (nn, racine); } nn = n; while (--nn) { racine = addarb (nn, racine); } return racine; } arbre addarb (int n, arbre a) { arbre crt; int i, j; for (i = 0; i < NBN; i++) { if (! a->fils[i]) { crt = (arbre) malloc (sizeof(noeud)); // crt = (noeud) malloc (sizeof(noeud)); a->fils[i] = crt; crt = a->fils[i]; crt->nb = n; crt->val = calcul (n); for (j = 0; j < NBN; j++) crt->fils[j] = NULL; return a; } } a->fils[0] = addarb(n, a->fils[0]); return a; } uint yest (int n, arbre a) { uint nbf, i, k; if (! a) return (uint) 0; if (n == a->nb) return (uint) 1; for (i = 0; i < NBN ; i++) if (yest (n, a->fils[i])) return (uint) 1; return (uint) 0; }

3. Graphes
   
   1. Les différentes structures
      
      • matrice
      • matrice compacte par triplet
      • matrice compacte par vecteur
      • pour chaque sommet
        • vecteur de successeurs
        • liste de successeurs
      • structure brins
   2. Exemple simple de graphe
      Nous installons une fonction pour tester les parcours de graphe vus en cours :

      struct graph { int nbn; int * v; } ; typedef struct graph graph_t;

      int voir (graph_t g, int i, int j) { if (i < 0 || i >= g.nbn) return -1; if (j < 0 || j >= g.nbn) return -1; return *(g.v + j * g.nbn + i); } void placer (graph_t g, int i, int j, int val) { if (i < 0 || i >= g.nbn) return ; if (j < 0 || j >= g.nbn) return ; *(g.v + j * g.nbn + i) = val; }

      graph_t construire (int nb) { graph_t g; int nbcarre, i, num; float taux, v; nbcarre = nb * nb; g.nbn = nb; g.v = (int *) malloc (nbcarre * sizeof(int)); assert (g.v); memset (g.v, 0, (size_t) nbcarre * sizeof(int)); srand(time(NULL)); taux = 0.25; num = nb / 10; while (num > 1) { num /= 5; taux /= 3.0; } for (i = 0; i < nbcarre; i++) { v = (float) rand () / RAND_MAX; num = v > taux ? 0 : 1; *(g.v + i) = num; } return g; }

   3. Seconde structure
      
      Voici une structure de graphe (vecteur de successeurs) dans laquelle chaque noeud a au plus trois successeurs :

      #include <stdio.h> #include <stdlib.h> #include <assert.h> #define MAX 5 struct noeud { int n; int h; float l; float surf; struct noeud * suc [3]; } ; typedef struct noeud noeud; typedef struct noeud * tas; tas creenoeud (int nb) { tas t; t = (tas) malloc (sizeof(noeud)); assert(t); t->n = nb; t->h = nb + 4; t->l = 11.0 - (float) ((t->h) << 1); if (t->l < 0) t->l *= -1.0; t->suc[0] = (tas) 0; t->suc[1] = (tas) 0; t->suc[2] = (tas) 0; t->surf = 0.0; return t; } tas creetas () { tas t[5]; int i; for (i = 0; i < 5; i++) { t[i] = creenoeud (i); } t[0]->suc[0] = t[4]; t[0]->suc[1] = (tas) 0; t[0]->suc[2] = t[2]; t[1]->suc[0] = t[0]; t[1]->suc[2] = (tas) 0; t[1]->suc[1] = t[3]; t[2]->suc[0] = (tas) 0; t[2]->suc[1] = (tas) 0; t[2]->suc[2] = t[4]; t[3]->suc[0] = (tas) 0; t[3]->suc[1] = t[0]; t[3]->suc[2] = t[2]; t[4]->suc[0] = t[2]; t[4]->suc[1] = t[3]; t[4]->suc[2] = t[1]; return t[0]; } void goaffichetas (tas t, char boo [MAX]) { if (!t) return; if (boo [t->n]) return; printf(" %d \t %d \t %f \t%f \n", t->n, t->h, t->l, t->surf); printf(" %d \t %d", (int) ((long long int) t % 10000), (int) ((long long int) t->suc[0] % 10000)); printf(" %d \t %d \n", (int) ((long long int) t->suc[1] % 10000), (int) ((long long int) t->suc[2] % 10000)); boo[t->n] = 1; goaffichetas(t->suc[0], boo); goaffichetas(t->suc[1], boo); goaffichetas(t->suc[2], boo); } void affichetas (tas t) { char boo [MAX]; int i; for (i = 0; i < MAX; i++) boo[i] = 0; goaffichetas (t, boo); } float absf (float x) { if (x < 0.0) return - x; return x; } void remplirsurf (tas t) { if (! t) return; if (t->surf != 0.0) return; t->surf = t->h * t->l; remplirsurf (t->suc[0]); remplirsurf (t->suc[1]); remplirsurf (t->suc[2]); } int main () { tas t; t = creetas (); affichetas(t); printf("\n\n"); remplirsurf(t); affichetas(t); }

      Une fois que remplirsurf a été utilisée, que se passe-t-il si on écrit une fonction pour chercher un élément dans le graphe et transcrivant directement la fonction remplirsurf (c'est-à-dire en en recopiant le canevas) ?
   4. Nouveaux exemples
      1. Tableau complet
         On voit ici une façon de créer un graphe avec un tableau plutôt vide, surtout quand le graphe est "grand".

         #include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> #include <assert.h> typedef short unsigned Shu; struct graphe { int nbs; Shu * tab; } ; typedef struct graphe graphe; graphe creegraphe (int nbs) { Shu i, j, max, num; float v, taux; graphe g; g.nbs = nbs; max = nbs * nbs; taux = 25.0; num = nbs / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.tab = (Shu *) malloc (max * sizeof(Shu)); assert(g.tab); memset(g.tab, 0, max); srand(time(NULL)); for (num = 0, i = 0; i < nbs; i++) for (j = 0; j < nbs; j++) { v = (float) rand () / RAND_MAX; g.tab[num++] = v < taux ? 1 : 0; } return g; } void voirgraf (graphe g) { Shu i, j, nb, num; nb = g.nbs; printf("Graphe\n"); for (i = 0, num = 0; i < nb; i++) { for (j = 0; j < nb; j++) printf("%c ", g.tab[num++]? '1' : ' '); printf("\n"); } } Shu nbnonnuls (graphe g) { Shu i, j, nb, num, total; nb = g.nbs; total = 0; printf("Graphe\n"); for (i = 0, num = 0; i < nb; i++) { for (j = 0; j < nb; j++) total += g.tab[num++]; } return total; } int main () { graphe g; int nb; Shu to; nb = 10; g = creegraphe (nb); voirgraf(g); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); nb = 50; g = creegraphe (nb); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); nb = 500; g = creegraphe (nb); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); } /*taux 0.25 Graphe 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Graphe Pour 10 il y a 25 cases non vides soit 25.000000 % taux 0.0833333 Graphe Pour 50 il y a 212 cases non vides soit 8.480000 % taux 0.00925926 Graphe Pour 500 il y a 2333 cases non vides soit 0.933200 % */

         Voici une nouvelle version avec un poids pour les arêtes :

         graphe creegraphe (int nbs) { Shu i, j, max, num; float v, taux; graphe g; g.nbs = nbs; max = nbs * nbs; taux = 25.0; num = nbs / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.tab = (Shu *) malloc (max * sizeof(Shu)); memset(g.tab, 0, max); srand(time(NULL)); for (num = 0, i = 0; i < nbs; i++) for (j = 0; j < nbs; j++) { v = (float) rand () / RAND_MAX; g.tab[num++] = v < taux ? (Shu) (v * 1000.) : 0; } return g; }

      2. Matrice compacte par triplets (ou paires)
         

         La principale méthode consiste à ne pas conserver les 0, donc à conserver par exemple des triplets (départ, arrivée, poids) (ou encore (i,j,arête)).

         Si le graphe n‘est pas pondéré, une simple paire suffit.

         Nous avons donc une structure triplet et un vecteur de triplets.

         struct triplet { int i; int j; float poids; } ; typedef struct triplet triple_t; struct gramaco { int nbs; /* nombre de sommets*/ int nba; /* nombre d aretes*/ triple * ares; /* vecteur d aretes*/ } typedef struct gramaco gramaco_t;

         Dans cette structure, si les triplets sont bien rangés par i croissants, on voit qu‘on a des successions de triplets à première valeur identique, ce qui nous conduit à la seconde structure.
      3. Matrice compacte par vecteur
         Pour chaque sommet i on va avoir un vecteur des sommets j auxquels il est lié.

         typedef short unsigned Shu; typedef struct noeud { int nbs; /* nombre de successeurs*/ int * succ; /* vecteur de successeurs */ float * poids; /* poids de chacune des arêtes */ } noeud_t; typedef struct grafmc { int nbs; noeud_t * node; /* vecteur des noeuds*/ } grafmc_t;

      4. Vecteur de successeurs
         Pour chaque sommet on conserve un vecteur de ses successeurs. Vous avez déjà un exemple ci-dessus, mais si on veut faire plus général (non limitation de l’arité) :

         /* nombre maximal de noeuds */ /* il faut un vecteur de tous les noeuds */ typedef struct legraf { int nbn; ptnoeud * vecnode; } legraf_t; /* structure d’un noeud */ struct noeud { int num; int nbs; struct noeud * * succ; float * poids; }; /* succ est un vecteur de pointeurs, un pointeur par successeur*/ /* poids est un vecteur de poids, un poids par successeur*/ /* si le graphe est non pondéré, on peut enlever poids*/ typedef struct noeud noeud; typedef struct noeud * ptnoeud;

      5. liste de successeurs
         Pour chaque sommet on conserve une liste de ses successeurs.

         #define MAX 1000 /* nombre maximal de noeuds */ /* il faut un tableau de tous les noeuds */ struct lesnoeuds { int vu; ptnoeud ne; }; typedef struct lesnoeuds legraphe [MAX]; /* structure d’un noeud */ struct noeud { int num; struct aretes * next; }; typedef struct noeud noeud; typedef struct noeud * ptnoeud; /* structure de liste de successeurs */ struct aretes { ptnoeud pt; float poids; struct aretes * suiv; } ; typedef struct aretes aretes; typedef struct aretes * ptarete;

      6. Brins
         Dernière structure présentée : le système à brins, tiré de Cori 1973.
         Principe de base, une arête n est séparée en deux parties, le brin -n et le brin +n. Un sommet est associé à un de ses brins, le "premier brin".
         Chaque brin est associé à un brin suivant (en général en tournant autour du sommet) et au numéro du sommet associé.
         Exemple :
         Sommets : 0, 1, 2, 3 et 4
         arêtes : a1: 0->3, a2: 1->2, a3: 4->1, a4: 4->0, a5: 0->1,
         Le tableau des premiers brins sera :
         noeud :0  1  2  3   4  
         brin  :-1 -2 +2 +1 -3
         Tableau des brins :
         

         -5  -4  -3  -2  -1  0  +1  +2  +3  +4  +5
         0   4   4   1   0   0  3   2   1   0   1
         +4 -3  -4  +5  -5   0  +1  +2  -2  -1  +3
         Il ne reste plus qu’à donner une représentation informatique et à
         faire tourner les programmes.
         
         
         struct strand {
           Shu node;
           short next;
         };
         typedef struct strand strand;
         struct strandgraph {
           Shu nbs;
           Shu nbstr;
           short * node; /* first strand*/
           strand * nxt;/* node and next strand*/
         } ;
         typedef struct strandgraph strgr;
         
         
         Vous pouvez maintenant utiliser la fonction de création d’un graphe
         (matrice) pondéré, creegraphe pour faire les 20 fonctions de
         passage d'une structure à l'autre : de matrice à matrice
         compacte, de brins à liste de successeurs, etc.
         
         
         TP du 25/10/23
         Nous avons maintenant 6 structures de graphe :
         La matrice complète qui a déjà été vue,
         
         
           
         la matrice compacte par triplets,
           
         la matrice compacte par vecteurs,
           
         la structure avec pour chaque noeud son vecteur de successeurs,
           
         la structure avec pour chaque noeud sa liste de successeurs,
           
         la structure à brins.
             
         
         Soit n votre numéro d‘étudiant modulo 5, auquel vous avez
         ajouté 1 (c‘est une valeur entre 1 et 5). Vous devez avec la structure
         n ci-dessus :
         
           
         adapter la fonction de création de graphe creegraphe
               (voir ci-dessus) pour la structure n.
           
         faire une fonction qui cherche s‘il y a un chemin entre deux
             sommets donnés.
           
         faire une fonction qui renvoie un chemin entre deux sommets
             donnés.
         
         
         
         
         
         
         
         Dernière mise à jour : 26/10/2023 (9h)