AA2024_Graphes

Jean-Jacques BOURDIN

E-mail :
jj NOSPAM @ up8.edu
(enlever le NO Spam)

Algorithmique Avancée 2024

Graphes

Présentation
Constantes et complexité
1. Calculs et mesures de complexité
2. Constantes
3. Exemple
De la Droite Discrète
1. Algorithme trivial
2. DDA et accélération
3. Mots de trace
4. Algorithme rapide
Graphes
1. Codages
2. Algorithmes
Compression
1. Rappels, champs de bits
2. Bases
3. Compression sans perte
4. Compression avec perte
5. Compression d'images
Modélisation, Illumination, Rendus
1. 2D/3D
2. Modélisation
3. Illumination
4. Lumière
5. Rendus, quelques effets
6. Rendus Expressifs
IA et jeux
2. Algorithmes

Projets

Graphes

Préparation

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 :

Chercher le nombre de noeuds d’un tel arbre.
Faire une fonction qui renvoie 1 si une valeur appartient à l’arbre.
Faire une fonction qui renvoie le noeud (son adresse) dont la valeur est le second paramètre.
Faire une fonction qui renvoie la profondeur d’un certain noeud dans l’arbre.
Faire une fonction qui renvoie 1 si on peut aller du sommet a (paramètre) au sommet b (paramètre).
Faire une fonction qui renvoie le chemin qui permet d‘aller du sommet a (paramètre) au sommet b (paramètre).

Arbres binaires en vecteur

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.
Puis vous trierez l‘arbre pour en faire un arbre binaire de recherche bien équilibré.

Arbres n-aires
Voici une déclaration (en l’occurence le fichier header) :

#include <stdio.h>
#include <stdlib.h>
#define NBN 4
typedef struct noeud {
  int nb;
  float val;
  struct noeud * fils [NBN];
} noeud_t;
typedef struct noeud * arbren_t;
typedef unsigned int uint;

arbren_t consarb (int);
arbren_t 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;
}

arbren_t consarb (int n) {
  arbren_t 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;
}

arbren_t addarb (int n, arbren_t a) {
  arbren_t crt;
  int i, j;

  for (i = 0; i < NBN; i++) {
	if (! a->fils[i]) {
	  crt = (arbren_t) 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, arbren_t 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;
}

Graphes

Les différentes structures
- matrice
- matrice compacte par triplet
- matrice compacte par vecteur
- pour chaque sommet
  - vecteur de successeurs
  - liste de successeurs
- structure brins

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

Avec cette structure, faites les fonctions suivantes :

Fonction qui compte le nombre d‘éléments que l‘on peut atteindre à partir d‘un sommet S (donné en argument).
Fonction qui trouve s‘il y a un chemin entre deux sommets donnés.
Fonction qui renvoie un chemin (s‘il existe) entre deux sommets donnés.
Fonction qui renvoie le nombre de parties connexes du graphe.

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) ?

Nouveaux exemples

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;
typedef struct graphe {
  int nbs;
  Shu * tab;
} graphe_t;

graphe_t creegraphe (int nbs) {
  Shu i, j, max, num;
  float v, taux;
  graphe_t 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_t 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_t 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_t 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 % 
*/

Attention sur certaines machines, limitées, vous aurez un "SegFault" à 500, voire à partir de 255.

Ce n‘est pas le programme qui est faux c‘est l‘utilisation de la mémoire qui peut être limitée.

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

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

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;

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;

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;

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 15/10/24

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 : 2 + (votre numéro d‘étudiant modulo 5) (c‘est une valeur entre 2 et 6). 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 : 15/10/2024 (17h)