Skip to content
Snippets Groups Projects

Floquet nicolas graphe v01

Merged Floquet nicolas graphe v01
FLOQUET_NICOLAS_Graphe_v01 into master
Merged TP SDA requested to merge FLOQUET_NICOLAS_Graphe_v01 into master
Compare
and
9 files
+ 1113
− 1
Compare changes
  • Side-by-side
  • Inline
Files
9
pagerank/src/graphe.c 0 → 100644
+ 455
− 0
#include <stdio.h>
#include <stdlib.h>
#include "graphe.h"
/** Fonction qui crée un graphe vide qui sera stocké à l'adresse g déjà allouée
* @param g un pointeur vers un graphe alloué en mémoire
* @param n le nombre strictement positif de cases des tableaux du graphe
* @requires n > 0
* @return 0 si le graphe a été créé et -1 si n <= 0 et -2 s'il y a eu une erreur d'allocation
* O(n)
*/
int creer_graphe(graphe* g, int n) {
int i;
if(n <= 0) {
printf("Erreur paramètre creer_graphe, n <= 0\n");
return -1;
}
if(!(g->ligne = (int*) malloc(sizeof(int) * n))) {
printf("Erreur allocation creer_graphe, g->ligne\n");
return -2;
}
if(!(g->col = (int*) malloc(sizeof(int) * n))) {
printf("Erreur allocation creer_graphe, g->col\n");
free(g->ligne);
return -2;
}
g->max = n;
g->premierVide = 0;
for(i = 0; i < n; i++) {
g->ligne[i] = -1;
g->col[i] = -1;
}
return 0;
}
/** Libère la mémoire allouée dans un graphe, mais pas le graphe lui même (le pointeur donné en paramètre reste à libérer
* @param g un pointeur vers un graphe alloué en mémoire
*/
void graphe_detruire(graphe* g) {
if(g) {
free(g->ligne);
free(g->col);
}
}
/** Renvoie la taille maximale actuelle des tableaux du graphe g
* @param g un pointeur vers un graphe alloué en mémoire
* @return g->max un entier
* O(1)
*/
int graphe_get_max(graphe* g) {
return g->max;
}
/** Renvoie l'indice du premier (-1 -1) dans le graphe
* @param g un pointeur vers un graphe alloué en mémoire
* @return g->premierVide un entier
* O(1)
*/
int graphe_get_premier_vide(graphe* g) {
return g->premierVide;
}
/** Indique si un sommet est dans le graphe
* @param g un pointeur vers un graphe alloué en mémoire
* @param u un entier, le sommet dont on veut savoir s'il est dans le graphe
* @return 1 si le sommet est dans le graphe et 0 sinon
* O(n)
*/
int graphe_contains(graphe* g, int u) {
return (graphe_find(g, u) != -1);
}
/** Donne l'indice de la première occurence d'un sommet dans le graphe
* @param g un pointeur vers un graphe alloué en mémoire
* @param u un entier, le sommet dont on veut connaître l'indice dans le graphe
* @return l'indice de le sommet si il est dans le graphe et -1 sinon
* O(n)
*/
int graphe_find(graphe* g, int u) {
if(g && u >= 0 && u <= graphe_get_plus_grand_sommet(g)) {
int i;
for(i = 0; i < graphe_get_premier_vide(g); i++) {
if(g->ligne[i] == u || g->col[i] == u) {
return i;
}
}
}
return -1;
}
/** Renvoie le plus grand indice des sommets du graphe
* @param g un pointeur vers un graphe alloué en mémoire
* @return un entier
* O(n)
*/
int graphe_get_plus_grand_sommet(graphe* g) {
int i, tmp, res = -1;
if(g) {
for(i = 0; i < graphe_get_max(g); i++) {
tmp = max(g->ligne[i], g->col[i]);
if(tmp > res) {
res = tmp;
}
}
}
return res;
}
/** Ajoute une arête entre les sommets i et j du graphe
* @param g un pointeur vers un graphe alloué en mémoire
* @param i un des sommets de l'arête
* @param j un des sommets de l'arête
*/
void graphe_ajouter_arete(graphe* g, int i, int j) {
if(g) {
if(graphe_get_premier_vide(g) == graphe_get_max(g)) {
g->max *= 2;
g->ligne = realloc(g->ligne, g->max * sizeof(int));
g->col = realloc(g->col, g->max * sizeof(int));
for(int i = graphe_get_premier_vide(g); i < graphe_get_max(g); i++) {
g->ligne[i] = -1;
g->col[i] = -1;
}
}
g->ligne[graphe_get_premier_vide(g)] = i;
g->col[graphe_get_premier_vide(g)] = j;
g->premierVide++;
}
}
/** Supprime une arête entre les sommets i et j du graphe
* @param g un pointeur vers un graphe alloué en mémoire
* @param i un des sommets de l'arête
* @param j un des sommets de l'arête
* O(n)
*/
void graphe_supprimer_arete(graphe* g, int i, int j) {
if(g) {
int cpt, flag = 0;
for(cpt = 0; cpt < graphe_get_premier_vide(g); cpt++) {
if(flag) { //On a trouvé l'arête et on l'a enlevée, donc maintenant il suffit de décaler le reste d'une case à gauche
g->ligne[cpt] = g->ligne[cpt+1];
g->col[cpt] = g->col[cpt+1];
}
else if(g->ligne[cpt] == i && g->col[cpt] == j) {
flag = 1;
g->ligne[cpt] = g->ligne[cpt+1];
g->col[cpt] = g->col[cpt+1];
}
}
if(flag) {
g->premierVide--;
}
}
}
/** Retire un sommet du graphe, assure qu'aucun sommet n'a d'arête allant vers ce dernier et qu'aucune arête ne part de celui ci.
* Puis les sommets supérieurs sont renommés, ex : si x = 5, 6->5, 7->6 etc
* @param g un pointeur vers un graphe alloué en mémoire
* @param x le sommet à retirer
* O(n)
*/
void graphe_retirer_sommet(graphe* g, int x) {
if(g) {
int n = graphe_get_plus_grand_sommet(g), i;
if(x >= 0 && x < n) {
int nbCasesVides = 0, *casesVides = (int*) calloc(sizeof(int), graphe_get_max(g));
if(!casesVides) {
printf("Erreur allocation graphe_retirer_sommet (tableau casesVides)\n");
return;
}
for(i=0; i < graphe_get_max(g); i++) {
casesVides[i]--;
}
for(i=0; i < graphe_get_max(g); i++) {
if(g->ligne[i] == x || g->col[i] == x) { //Une arête part de x, ou arrive en x, on retire le sommet donc tout part
g->ligne[i] = -1;
g->col[i] = -1;
casesVides[nbCasesVides++] = i;
}
else { // Rien n'est supprimé, mais les indices des sommets > x sont décrémentés
if(g->ligne[i] > x) {
g->ligne[i]--;
}
if(g->col[i] > x) {
g->col[i]--;
}
}
}
g->premierVide -= nbCasesVides;
//Maintenant on a aucune trace du sommet x, mais plein de (-1 -1) où il était (ATTENTION ON PEUT ENCORE VOIR DES SOMMETS X, MAIS CE SONT LES ANCIENS SOMMETS X+1, CECI N'EST PAS UN BUG, NE PAS DÉBUGGER)
//Il faut retasser tout ça
for(i = graphe_get_max(g) - 1; i >= 0 && nbCasesVides; i--) {
if(g->ligne[i] != -1) { //Pas une case vide, donc on peut l'échanger avec une case vide
g->ligne[casesVides[nbCasesVides-1]] = g->ligne[i];
g->col[casesVides[nbCasesVides-1]] = g->col[i];
nbCasesVides--;
g->ligne[i] = -1;
g->col[i] = -1;
}
}
free(casesVides);
}
}
}
/** Indique si 2 sommets sont adjacents ou non, s'il existe une arête les reliant
* @param g un pointeur vers un graphe alloué en mémoire
* @param u un des sommets de l'arête
* @param v un des sommets de l'arête
* @return 1 si les sommets sont adjacents et 0 sinon
* O(n)
*/
int graphe_voisins(graphe* g, int u, int v) {
if(g) {
int max = graphe_get_plus_grand_sommet(g);
if(u >= 0 && v >= 0 && u <= max && v <= max) {
int i;
for(i = 0; i < graphe_get_premier_vide(g); i++) {
if(g->ligne[i] == u && g->col[i] == v) {
return 1;
}
if(g->ligne[i] == v && g->col[i] == u) {
return 1;
}
}
}
}
return 0;
}
/** Indique si 1 sommet est successeur d'un autre ou non
* @param g un pointeur vers un graphe alloué en mémoire
* @param u un des sommets de l'arête
* @param v un des sommets de l'arête
* @return 1 si v est un successeur de u et 0 sinon
* O(n)
*/
int graphe_est_succ(graphe* g, int u, int v) {
if(g) {
int max = graphe_get_plus_grand_sommet(g);
if(u >= 0 && v >= 0 && u <= max && v <= max) {
int i;
for(i = 0; i < graphe_get_premier_vide(g); i++) {
if(g->ligne[i] == u && g->col[i] == v) {
return 1;
}
}
}
}
return 0;
}
/** Affiche le graphe sous la forme d'une matrice d'adjacence
* @param g un pointeur vers un graphe alloué en mémoire
* O(n)
*/
void graphe_afficher(graphe* g) {
if(g) {
printf("Graphe à %d arêtes\n", graphe_get_premier_vide(g));
int lim = graphe_get_plus_grand_sommet(g)+1, i, v, w;
int* matrice = (int*) calloc(sizeof(int), lim * lim);
if(!matrice) {
printf("Erreur allocation graphe_afficher \n");
return;
}
for(i = 0; i < g->premierVide; i++) {
matrice[g->ligne[i] * lim + g->col[i]]++;
// pas dans les 2 sens matrice[g->col[i] * lim + g->ligne[i]]++;
}
/* matrice d'adjacence faite */
/* ligne indices colonnes */
printf("\t\t");
for(w = 0 ; w < lim ; w++) {
printf("%d\t", w);
}
printf("\n");
printf("\t\t");
for(w = 0 ; w < lim ; w++) {
printf("_\t");
}
printf("\n");
/* lignes de la matrice */
for(v = 0 ; v < lim ; v++) {
printf("%d\t|\t", v);
for(w = 0 ; w < lim ; w++) {
printf("%d\t", matrice[v * lim + w]);
}
printf("|\n");
}
printf("\t\t");
for(w = 0 ; w < lim ; w++) {
printf("_\t");
}
printf("\n");
free(matrice);
}
else {
printf("Erreur graphe_afficher Le graphe est NULL\n");
}
}
/** Affiche le graphe sous la forme des 2 tableaux le composant
* @param g un pointeur vers un graphe alloué en mémoire
* O(n)
*/
void graphe_afficher_tableaux(graphe* g) {
int i;
printf("\n======================");
printf("\nIndices\t\t");
for(i = 0; i < graphe_get_max(g); i++) {
printf("| %2d ", i);
}
printf("\n\nlignes :\t");
for(i = 0; i < graphe_get_max(g); i++) {
if(i < graphe_get_premier_vide(g)) {
printf("| %2d ", g->ligne[i]);
}
else { //Il ne devrait y avoir que des (-1)
printf("| (%d) ", g->ligne[i]);
}
}
printf("\ncolonnes :\t");
for(i = 0; i < graphe_get_max(g); i++) {
if(i < graphe_get_premier_vide(g)) {
printf("| %2d ", g->col[i]);
}
else { //Il ne devrait y avoir que des (-1)
printf("| (%d) ", g->col[i]);
}
}
printf("\n======================");
printf("\n\n");
}
/** Convertit un graphe au format DOT dans un fichier
* dot -Tpdf fichier.dot -o fichier.pdf
* @param g un graphe alloué en mémoire
* @param nomFichier, le nom du fichier où l'on veut écrire le graphe
* @return 0 si le graphe a bien été écris au format DOT,
* -1 s'il y a eu une erreur d'ouverture du fichier, et -2 sinon
* O(n)
*/
int graphe_ecrire_dot(graphe* g, char* nomFichier) {
if(g) {
int i, nbSommets = 0, n = graphe_get_premier_vide(g), sommetMax = graphe_get_plus_grand_sommet(g);
if(!n) {
printf("Erreur premier vide = 0, graphe vide graphe_ecrire_dot\n");
return -2;
}
/*
On utilise 2 tableaux pour avoir une liste des sommets dans le graphe.
Soit n = graphe_get_premier_vide(g), il y a au max 2n sommets différents
(Si tous les sommets dans le tableau des lignes sont distincts et pointent chacun vers un sommets distinct)
Donc c'est le nombre max de sommets dans le fichier DOT.
Et les valeurs des sommets sont entre 0 et graphe_get_plus_grand_sommet(g) inclus
*/
int* flagSommet = (int *) calloc(sizeof(int), sommetMax + 1);
/*
flagSommet[i] =
0 : sommet pas dans le graphe
1 : sommet dans le graphe, il faudra l'ajouter dans le fichier dot
Toutes les valeurs entières entre 0 et sommetMax inclus peuvent être dans le graphe
*/
if(!flagSommet) {
printf("Erreur allocation flagSommet graphe_ecrire_dot\n");
return -2;
}
int* listeSommets = (int *) calloc(sizeof(int), 2*n);
/*
listeSommets[i] :
-1 : sommet pas dans le graphe
>= 0 : sommet dans le graphe, il faudra l'ajouter dans le fichier dot
Il y a au max 2n sommets différents
*/
if(!listeSommets) {
printf("Erreur allocation listeSommets graphe_ecrire_dot\n");
free(flagSommet);
return -2;
}
for(i = 0; i < 2*n; i++) {
listeSommets[i]--; //-1 partout
}
FILE *f = fopen(nomFichier, "w");
if (!f) {
free(flagSommet);
free(listeSommets);
printf("Erreur ouverture fichier \"%s\"graphe_ecrire_dot\n", nomFichier);
return -1;
}
for(i = 0; i < n; i++) {
if(!flagSommet[g->ligne[i]]) { //g->ligne[i] valait 0, donc le sommet n'était pas découvert
flagSommet[g->ligne[i]] = 1;
listeSommets[nbSommets++] = g->ligne[i];
}
if(!flagSommet[g->col[i]]) { //g->col[i] valait 0, donc le sommet n'était pas découvert
flagSommet[g->col[i]] = 1;
listeSommets[nbSommets++] = g->col[i];
}
}
//Dans flagSommet, on a tous les flags indiquant si un sommet est dans le graphe ou non
//Dans listeSommets on a la liste des sommets distincts
fputs("graph {\n", f);
for(i = 0; i < nbSommets; i++) {
fprintf(f, "\t%d;\n", listeSommets[i]);
}
fputs("\n", f);
for(i = 0; i < n; i++) {
fprintf(f, "\t%d -- %d;\n", g->ligne[i], g->col[i]);
}
fputs("}\n", f);
free(flagSommet);
free(listeSommets);
fclose(f);
return 0;
}
printf("Erreur pagerank NULL graphe_ecrire_dot\n");
return -2;
}
/** Renvoie le maximum entre 2 entiers
* @param x un entier
* @param y un entier
* @return un entier, le plus grand des 2 paramètres
* O(1)
*/
int max(int x, int y) {
return (x > y) ? x : y;
}