Discussion :

[louisandrex]

Bonjour à tous,

Je travaille sur des graph codés en matrice d'adjacence. Le but de la fonction qui me pose est problème est le suivant :
"créer, à partir d'un fichier texte représentant une matrice d'adjacence, le graph correspondant"

Dans ma structure de graph, je possède un champ "mat" qui est un tableau de tableau dont la case mat[i][j] est le poids du sommet i vers le sommet j. On utilise la constante INT_MAX pour symboliser que i et j ne sont pas liés directement. Le champ nbVertices est tel que la matrice soit de dimension nbVertices*nbVertices. Plus tard dans mon programme, il s'avère que nbVertices=n, le nombre de lignes utiles à la création de la matrice.

Voici un exemple de fichier texte correspondant à la matrice d'adjacence d'un graph :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
0	12	i	i	i	15	20	i
i	0	21	i	i	i	i	i
i	i	0	i	3	i	i	19
i	i	7	0	i	i	i	7
i	i	i	13	0	i	i	14
i	i	i	i	28	0	4	i
i	i	i	i	18	i	0	45
i	i	i	i	i	i	i	0

C'est une matrice 8x8, le document comporte 9 lignes (la dernière est vide). Dans les fichiers textes, deux sommets ne sont pas liés si un "i" est indiqué (pour rappeler "infini" et donc INT_MAX).

Je dois donc créer une fonction qui lit un document comme celui ci-dessus et renvoie le graph associé (avec le champ tableau mat correctement construit).

Voici ce que je propose :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
T_graphMD * fileToGraph(const char * filename) {
	FILE* fpAdj=fopen(filename,"r");
 
	CHECK_IF(fpAdj, NULL, "fopen fileToGraph");
 
	// pour connaître la taille de la matrice, on compte le nombre de lignes dans fpAdj
	unsigned int n=nbLignes(filename);
	T_graphMD *g=newGraphMD(n);
	int i=0,j=0;
	char c;
 
	// il faut maintenant remplir le Graph
	while (c != EOF) {
		c=fgetc(fpAdj);
		if isdigit(c) {
		fseek(fpAdj,-1,ftell(fpAdj));
		fscanf(fpAdj,"%d",&g->mat[i][j++]);
		}
		else if (c=='\n') {
			j=0;
			i++;
		}
		else if (c=='i') {
			j++;
		}
	}
 
	// On vérifie :
	for (i=0;i<g->nbVertices;i++) {
		for (j=0;j<g->nbVertices;j++) {
			printf("g->mat[%d][%d]=%d\n",i,j,g->mat[i][j]);
		}
	}
 
	fclose(fpAdj);
 
	return g;
}

Quelques détails : T_graphMD est la structure considérée de graph, l'un de ses champs est "mat" et c'est ce qui nous intéresse ici.
La fonction nbLignes renvoie le nombre de lignes d'un document diminué de 1. Dans notre exemple ci-dessus : elle renvoie 8.
Je sais que la fonction fseek() est peu pratique si on ne lit pas le texte en binaire et en effet le programme que je vous propose ne fonctionne pas.
La fonction newGraph(int n) produit un graph dont la matrice de dimension n*n du champ mat contient uniquement des MAX_INT, c'est pour cela que je n'y touche pas lorsque le caractère lu est "i".

J'ai réussi cependant à écrire un programme pour un document texte contenant uniquement des nombres compris entre 0 et 9 et des "i". Cela ne répond cependant que partiellement à la question puisque la matrice est censée contenir éventuellement des nombres plus grands que 9.

J'ai essayé d'avoir recours à des fscanf, notamment avec "%d" : je suis embêté parce que cela plante lorsqu'un "i" est dans la matrice et pour le premier terme de ma matrice, si j'ai un "10", alors le fscanf me renvoie un 0. Par exemple avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
T_graphMD * fileToGraph(const char * filename) {
	FILE* fpAdj=fopen(filename,"r");
 
	CHECK_IF(fpAdj, NULL, "fopen fileToGraph");
 
	// pour connaître la taille de la matrice, on compte le nombre de lignes dans fpAdj
	unsigned int n=nbLignes(filename);
	T_graphMD *g=newGraphMD(n);
	int i=0,j=0;
	char c;
 
	// il faut maintenant remplir le Graph
	while (c != EOF) {
		c=fgetc(fpAdj);
		if isdigit(c) {
		fscanf(fpAdj,"%d",&g->mat[i][j++]);
		}
		else if (c=='\n') {
			j=0;
			i++;
		}
		else if (c=='i') {
			j++;
		}
	}
 
	// On vérifie :
	for (i=0;i<g->nbVertices;i++) {
		for (j=0;j<g->nbVertices;j++) {
			printf("g->mat[%d][%d]=%d\n",i,j,g->mat[i][j]);
		}
	}
 
	fclose(fpAdj);
 
	return g;
}

Je teste ce programme avec cette matrice :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
10	9	3	i
i	0	2	i
i	i	0	4
i	1	i	0

Et j'obtiens une matrice pour le champ mat du graph renvoyé, qui n'est évidemment pas correcte :

Voici donc ma question : comment récupérer et remplir ma matrice à partir d'un document texte sans avoir besoin de retourner en arrière d'un caractère après avoir testé si ledit caractère est un chiffre ou non (évitant ainsi d'utiliser fseek() ) ?

Je vous remercie beaucoup pour votre aide : j'ai passé un temps fou sur ce programme, à tenter et retenter différentes méthodes mais qui n'ont pas su régler le problème des "i" lus par un fscanf avec le format "%d". J'ai également remarqué que tout effectuer avec un fgetc() n'est pas possible (sauf dans le cas où les nombres sont compris en 0 et 9), puisque sinon je mets un chiffre par case, ce qui ne va pas dans le cas général.

Je réitère mes remerciements et vous souhaite une agréable journée,
louisandrex.

[dalfab]

Bonjour,

Ça n'est pas "peu pratique" d'utiliser fseek() dans un fichier texte, c'est "interdit" à part quelques cas particuliers. En tout cas il faudrait au moins y passer les bons paramètres et tu n'as pas compris à quoi sert le troisième. La doc de fseek().
Un moyen simple de reculer d'un caractère c'est la fonction ungetc().

La fonction getc() ne retourne pas un char mais un int. Le char est trop petit pour contenir les 256 caractères + le EOF.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
   ...
   int  c;
   for (;;) {
      do {        // il faut peut être aussi sauter d'éventuels espaces
         c = fgetc( fpAdj );
      } while ( c == ' '  ||  c == '\t' );
      if ( c == EOF )
         break;                 // la fin a été atteinte
      if ( isdigit( c ) ) {
         ungetc( fpAdj, c );    // reculer du caractère déjà lu
         fscanf( fpAdj, "%d", &g->mat[i][j++] );
      }
      ...

[louisandrex]

Bonjour et merci,
Je ne m'étais pas beaucoup renseigné sur fseek() (seulement un seul article) et je n'avais pas compris à quel point son usage était proscrit dans la plupart des cas.
Votre indication sur la fonction ungetc() m'a été très utile, cela fonctionne désormais avec la boucle ainsi modifiée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	while (c != EOF) {
		c=fgetc(fpAdj);
		if isdigit(c) {
			ungetc(c, fpAdj);
			fscanf(fpAdj,"%d",&g->mat[i][j++]);
		}
		else if (c=='\n') {
			j=0;
			i++;
		}
		else if (c=='i') {
			j++;
		}
	}

Merci encore et bonne soirée!