Plateforme de traitement de graphes

non-orientés, connexes

[ Conseils de programmation | Structure de données | Entrées en fichier | Files acces | Exemple d'execution ]

Conseils de programmation

1. Return Manquant et retour non intercepté

Paramètrer votre compilateur de manière à faire apparaître tous les warning possible. Pour ma part la cause la plus importante de bug est issu de l'oubli de return dans une fonction typée. Exemple:

G AllocInitG(G g, int n)

{

g= allocContent(g,n);

g.n=n;

g.m=0;

g.nbcol=0;

g=initContent (g);

}

Le problème est alors que de l'extèrieur de la fonction les modifications apportées par AllocInitG sont invisibles.... D'autre part il y a aussi les appels:

fscanf(fp,"%d",&n);

AllocInitG(g,n);

fscanf(fp,"%d",&som);

il faut alors

fscanf(fp,"%d",&n);

g=AllocInitG(g,n);

fscanf(fp,"%d",&som);

sinon la aussi (mais d'une manière différente) il peut exister des modifications réalisées qui ne seront visibles. J'ai employé 'il peut exister' au lieu de aucune car les modifications réalisées sur des variables globales seront bien sur visibles...

 

Pour rendre visible ces erreurs potentielles (il y a des cas ou l'on doit programmer de cette façon), dans CW 2.0 on trouve la fenêtre suivante:

2. Allocation, désallocation

La fonction free() permet de désallouer (libérer) des espaces auparavent allouer par malloc ou calloc. Un free sur un pointeur NULL ne fait rien, ie ne plante pas. Mais il faut toujours prendre garde de libérer uniquement ce que l'on a alloué. Les erreurs les plus courantes consistent dans une boucle de libération d'une liste chainée de réaliser :

for(p=tete; p !=NULL; p=p->suiv)

free(p)

Correction

for(p=tete; p !=NULL; p=q)

{

q=p->suiv;

free(p);

}

 

3. fprint sous MacOS(<=8.1)

Quand vous écrivez dans un fichier à l'aide d'un programmeen C (par fprintf par exemple), prenez garde que celui-ci ne soit pas déjà ouvert (ie dans une fenêtre par exemple). Car dans ce cas votre programme ne pourra pas le MODIFIER. Concrètement cela se traduit par un fichier qui devrait être transformé et qui au final ne le sera pas...

Structure de données

La structure de données que l'on a choisie est redondante, on s'explique. Elle est pauvre en performance mémoire mais riche en vitesse dans certain cas. Par exemple cette structure est particulièrement adaptée aux algorithmes solliciantant la liste des voisins d'un sommet. Dans cette perspective la liste des voisins d'un sommet est immédiatement connue, il s'agit de réaliser un parcours linéaire standart de liste chainée. Cette structure peut être vue de la manière suivante:

son formalisme en C est définit dans struct.h.

D'autre part pour certains algorithmes cette structure peut paraître trop complexe. Par exemple dans le cas où le nombre des voisins de tous les sommets reste invariants. Dans un pareil cas la liste dynamique horyzontale est mal adaptée car plus délicate à manipuler qu'un vecteur (alloué dynamique par bloc: (int *) malloc (taille *sizeof(int))) par exemple.

En revanche pour des algorithmes tel que le nombre des voisins de tous les sommets n'est pas invariants, cette structure, en tous cas pour la mémoire, est plus économique. Ce qui permet théoriquement de pouvoir affronter des instances de problèmes plus grandes.

D'autres part d'un point de vue purement pédagogique, cette structure étant basées fortement sur les pointeurs et les manipulations d'adresse, il me semble être un bon exercice; dans la mesure où l'on sait bien que c'est précisement içi la difficulté du C.

Entrées en fichier

Afin de proposer une grande souplesse d'utilisation de cette plateforme d'algorithme de graphes, l'idée est de stocker les graphes dans un fichier fixé au nom de graph.txt.

On propose deux formalismes de descriptions de graphes dans ce fichier. Ces deux formalismes ont une partie commune, on la présente. Dans tous les cas ces formalismes peuvent être améliorés par exemple de manière à accepter plusieurs graphes dans un seul fichier.

Exemple de graphe dans graph.txt

6

1 3 4 5 6

2 3 4 5 6

3 2 1 2

-1

Convention:

Le fichier contient un seul graphe.

Le fichier commence par le nombre de sommet du graphe (içi 6)

Ensuite par ligne on présente le numéro du sommet (exemple 1) suivie de son degré (3) et de la liste de ces voisins (les voisins de 1 sont les sommet 4, 5 et 6). Le degré sert uniquement pour le fichier; ie il permet de savoir à la lecture de celui-ci, quand on passe à la description du voisinage d'un autre sommet. Exemple: 1 3 4 5 6, 3 chiffres après le 3, on décrit le voisinage du sommet 2.

Une fois le graphe totalement décrit on écrit -1

Deux formalismes:

Les deux formalismes se distinguent de la manière suivante:

Le graphe est décrit de manière symètrique ou non. Le graphe précédent est décrit de manière non-symétrique. Cette dernière représentation est plus économe en espace, mais parfois plus délicate quand elle est produite à la main.

Si il est décrit de maniuère symètrique alors le graphe précédent doit être présenté dans graph.txt de la manière suivante:

6

1 3 4 5 6 3

2 3 4 5 6 3

3 2 1 2

4 2 1 2

5 2 1 2

6 2 2 1

-1

On peut voir l'implémentation de ces deux formalismes: symètrique et non-symétrique dans les fonctions respectivements:

G getGraphInFileSymetric(G g)

G getGraphInFileNoSymetric(G g)

écritent dans le fichier io.c

Files access

(image map)

Exemple d'execution

Un fichier graph.txt

Le fichier issu de mon a.out

Philippe Rolland-04/98