projetliste/graphemat.c at main · douaa0/projetliste · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graphemat.h"

//mettre tous les champs à faux
static void razMarque(GrapheMat* graphe){
	int i;
	for(i=0; i<graphe->n; i++){
		graphe->marque[i] = faux;
	}
}

//allocation de graphe
GrapheMat* creerGrapheMat (int nMax, int value){
	GrapheMat* graphe = (GrapheMat*) malloc (sizeof(GrapheMat));
	graphe->n = 0;
	graphe->nMax = nMax;
	graphe->value = value;
	graphe->nomS = (NomSom*) malloc (sizeof(NomSom) *nMax);
	graphe->marque = (booleen*) malloc (sizeof(booleen) *nMax);
	graphe->element = (int*) malloc (sizeof(int) *nMax*nMax);
	graphe->valeur = (int*) malloc (sizeof(int) *nMax*nMax);

	int i;
	int j;
	for(i=0; i<nMax; i++){
		for(j=0; j<nMax; j++){
			graphe->element [i*nMax+j] = faux;
			graphe->valeur [i*nMax+j] = INFINI;
		}
	}
	razMarque(graphe);

	return graphe;
}

//desallocation d'un graphe
void detruireGraphe (GrapheMat* graphe){
	free(graphe->nomS);
	free(graphe->marque);
	free(graphe->element);
	free(graphe->valeur);
	free(graphe);
}

//fournit le rang dans le tableau nomS du nom
static int rang (GrapheMat* graphe, NomSom nom){
	int i=0;
	booleen trouve = faux;
	while((i<graphe->n) && !trouve){
		trouve = strcmp(graphe->nomS[i], nom)==0;
		if(!trouve) i++;
	}
	return trouve ? i : -1;
}

//insertion d'un sommet dans un graphe
void ajouterUnSommet (GrapheMat* graphe, NomSom nom){
	if(rang(graphe, nom) == -1){
		if(graphe->n < graphe->nMax){
			strcpy(graphe->nomS[graphe->n++], nom);
		} else {
			printf("\nNombre de sommets > %d\n", graphe->nMax);
		}
	} else {
		printf("\n%d deja defini\n", nom);
	}
}

//insertion d'un arc dans un  graphe,
    //somD est de depart, somA d'arrive
void ajouterUnArc (GrapheMat* graphe,
                   NomSom somD, NomSom somA, int cout){
	int nMax = graphe->nMax;
	int rd = rang(graphe, somD);
	int rg = rang(graphe, somA);
	graphe->element[rd*nMax+rg]=vrai; //rd*nMax+rg pour se positionner dans la matrice
	graphe->valeur[rd*nMax+rg]=cout;
}

//ecriture d'un graphe
void ecrireGraphe (GrapheMat* graphe){
	int nMax=graphe->nMax;
	int i;
	int j;
	for(i=0; i<graphe->n; i++){
		printf("%s",graphe->nomS[i]);
	}
	printf(";\n");
	for(i=0; i<graphe->n; i++){
		printf("\n%s", graphe->nomS[i]);
		for(j=0; j<graphe->n; j++){
			if(graphe->element[i*nMax+j] == vrai){
				printf("%s", graphe->nomS[j]);
				if(graphe->value){
					printf("%d", graphe->valeur[i*nMax+j]);
				}
			}
		}
		printf(";");
	}
}

//function profondeur
static void profondeur(GrapheMat* graphe, int numSommet){
	int nMax = graphe->nMax;
	graphe->marque[numSommet] = vrai;
	printf("%s\n", graphe->nomS[numSommet]);
	int i;
	for(i=0; i<graphe->n; i++){
		if((graphe->element[numSommet*nMax+i] == vrai)
            && !graphe->marque[i]){
			profondeur(graphe, i);
		}
	}
}

//parcours en profondeur d'un graphe
void parcoursProfond (GrapheMat* graphe){
	razMarque(graphe);
	int i;
	for(i=0; i<graphe->n; i++){
		if(!graphe->marque[i]){
			profondeur(graphe, i);
		}
	}
}