L'objectif de ce sujet est de charger un graphe à partir d'un fichier, d'en calculer quelques invariants topologiques (composantes connexes, genre) ; le graphe sera tout d'abord d'un type simple, puisqu'il sera inscrit sur une grille rectangulaire, puis en passant au graphe d'adjacence de ses composantes connexes, on se ramènera à l'étude d'une structure de graphe quelconque.
21 ===================== =.=.=.=.=.=.=.=.=.=.= =.=.=.=.=.=.=.=.=.=.. =.=...............=== ....===============.= =====...............= =...................= =.=================.= =.=...............=.= =.=.=============.=.= =.=.=.=.=.=.=.=.=.=.= =.=.=============.=.= =.=...............=.= =.================..= =..................== ===================..représente un graphe (non connexe) sur les couleurs = et . et où 21 correspond à la largeur de la grille (au nombre de sommets par lignes).
Il s'agit tout d'abord de représenter un tel graphe en mémoire. Pour cela, on considère le tableau de struct suivant, que l'on enrichira au fur et à mesure des besoins du sujet :
#define N 100
struct {
/* Couleur de l'intersection. */
int couleur;
} grille[N][N];
/* On impose nb_cols<N. */
int nb_cols,nb_lignes;
Écrire une procédure
void charger(char *fichier);
qui charge un fichier dont le chemin d'accès est passé en argument et
vérifie le format du fichier : le nombre de lignes est limité par
la constante N ; le nombre de colonnes doit être
identique sur toutes les lignes, être indiqué sur la première ligne du
fichier, et ne pas dépasser N. On utilisera les
fonctions fopen(), fscanf(), getc(),
feof() et fclose() de la librairie standard.
Écrire ensuite une procédure
void afficher(void);
pour réaliser l'affichage de la grille chargée en mémoire
(c'est-à-dire essentiellement reconstituer le texte lu dans le
fichier), par exemple :
Il y a 16 lignes et 21 colonnes. ===================== =.=.=.=.=.=.=.=.=.=.= =.=.=.=.=.=.=.=.=.=.. =.=...............=== ....===============.= =====...............= =...................= =.=================.= =.=...............=.= =.=.=============.=.= =.=.=.=.=.=.=.=.=.=.= =.=.=============.=.= =.=...............=.= =.================..= =..................== ===================..
On prendra soin, après chaque appel système (opération sur les fichiers ou la mémoire) de vérifier la valeur de retour, et le cas échéant de quitter le programme en faisant apparaître un message d'erreur approprié.
Voici quelques exemples de fichiers bien formatés sur lesquels valider vos procédures : Essai2, Essai3, Composantes, Graphe, Probleme, Laby40, Laby80.
#define N 100
enum { FALSE=0, TRUE };
/* Deux cellules de la grille rectangulaire qui se touchent par un cote
correspondent a une arete si et seulement si elles ont meme couleur.
*/
struct {
/* Couleur de l'intersection. */
int couleur;
/* Composante connexe. */
int composante;
/* Marque utilisee pour les parcours de graphe
et pour reperer le chemin vers la sortie.
*/
int marque;
} grille[N][N];
/* On impose nb_cols<N. */
int nb_cols,nb_lignes,nb_composantes;
enum { NN, SS, EE, OO };
/* Tailles des composantes. */
int taille[N*N];
Le champ marque est mis à FALSE tant que
le sommet n'a pas encore été considéré dans le parcours du graphe,
puis à TRUE pour indiquer qu'il a déjà été considéré.
Écrire une procédure
void p_profondeur(int i,int j,int dir);
qui parcoure le graphe à partir de l'intersection (i,j)
en provenant de la direction indiquée par dir, puis une
provenant
void decomp_composantes(void);
qui l'utilise donner à chaque intersection son numéro de composante
connexe. Écrire enfin les procédures
void afficher_composantes(void);
void afficher_tailles_composantes(void);
pour afficher la grille colorée par les numéros de composantes (et non
les couleurs d'origine) et pour afficher les tailles des composantes
connexes. On produira par exemple l'affichage :
Il y a 14 composantes. aaaaaaaaaaaaaaaaaaaaa abababababababababaca abababababababababacc ababbbbbbbbbbbbbbbaaa bbbbaaaaaaaaaaaaaaada aaaaaddddddddddddddda addddddddddddddddddda adeeeeeeeeeeeeeeeeeda adefffffffffffffffeda adefgggggggggggggfeda adefghgigjgkglgmgfeda adefgggggggggggggfeda adefffffffffffffffeda adeeeeeeeeeeeeeeeedda addddddddddddddddddaa aaaaaaaaaaaaaaaaaaann
enum { FALSE=0, TRUE, WAY };
de façon que TRUE indique un sommet déjà considéré mais
non retenu pour le chemin, et WAY un sommet déjà
considéré et retenu pour le chemin.
Écrire une fonction
int chemin_rec(int ia,int ja,int ib,int jb,int dir);
qui parcoure le graphe à partir de
l'intersection (ia,ja) en provenant de la direction
indiquée par dir, et répond TRUE s'il y a un
chemin qui atteint (ib,jb) en ne suivant que des
cellules de la même couleur que (ia,ja). Puis écrire
une fonction
int chemin(int ia,int ja,int ib,int jb);
qui initialise les champs marque avant d'appeler
chemin_rec. On fera saisir les coordonnées des deux
extrémités en utilisant la fonction scanf() de la
librairie standard. Écrire enfin la procédure
void afficher_chemin(char ch);
pour afficher la grille colorée par la couleur à chaque intersection,
sauf sur les intersections du chemin où le caractère ch
sera utilisé. On obtiendra par exemple l'affichage :
(i_entree,j_entree,i_sortie,j_sortie) : (3,2,15,15) ==XXXXXXXXXXXXXXXXX== =.X.=.=.=.=.=.=.=.X.= =.X.=.=.=.=.=.=.=.X.. =.X...............X== ....XXXXXXXXXXXXXXX.= XXXXX...............= X...................= X.=================.= X.=...............=.= X.=.=============.=.= X.=.=.=.=.=.=.=.=.=.= X.=.=============.=.= X.=...............=.= X.================..= X..................== XXXXXXXXXXXXXXXX===..
On étend encore la structure de marquage par
enum { FALSE=0, TRUE, WAY, LIBERTY };
de façon que TRUE indique un sommet déjà considéré mais
non reconnue comme liberté, et WAY un sommet déjà
considéré et reconnue comme une liberté. (La marque WAY
n'est plus utilisée dans cette partie.)
Écrire les fonctions
int libertes_rec(int i,int j,char lib,int dir);
int libertes(int ia,int ja,char lib);
qui par un parcours en profondeur d'abord comptent le nombre de
libertés de couleur lib de la composante connexe
contenant le sommet (i,j), puis une procédure d'affichage
void afficher_libertes(char lib);
pour afficher la grille colorée par la couleur à chaque intersection,
sauf sur les intersections du chemin où le caractère lib
sera utilisé. On obtiendra par exemple l'affichage :
(i,j,`liberte') : (15,15,`.') Composante `a', couleur `=', taille 107, 96 libertes `.' ===================== =+=+=+=+=+=+=+=+=+=+= =+=+=+=+=+=+=+=+=+=++ =+=+++++++++++++++=== ++++===============+= =====+++++++++++++++= =++++..............+= =+=================+= =+=...............=+= =+=.=============.=+= =+=.=.=.=.=.=.=.=.=+= =+=.=============.=+= =+=...............=+= =+================.+= =++++++++++++++++++== ===================++(ici, les libertés sont repérées par des `+').
Ce graphe ayant a priori une structure plannaire mais générale, on introduit une nouvelle structure de données pour les graphes généraux.
/* Le graphe reduit sera stocke dans une structure dynamique. */
typedef struct graphe {
int composante;
struct liste_graphes *voisins;
} *Graphe;
typedef struct liste_graphes {
Graphe graphe;
struct liste_graphes *suivant;
} *Liste;
Liste composantes;
Écrire les constructeurs
Graphe new_Graphe(int c,Liste v);
Liste new_Liste(Graphe g,Liste s);
en prenant soin de tester les valeurs en retour
de malloc().
Écrire une fonction de recherche d'un Graphe dont le champ composantes est un entier k (qui renvoie NULL si aucun graphe n'est trouvé dans la liste) et une fonction d'insertion d'une composante k dans la liste l triée par numéros croissants de composantes, le cas échéant en créant une nouvelle composante (au départ sans voisin). Les signatures de ces fonctions (récursives) seront :
Graphe recherche_composante(int k,Liste l);
Liste insere_composante(int k,Liste l);
La fonction d'insertion renverra la liste éventuellement modifiée.
Écrire une procédure
void reduction(void);
qui balaie la grille en créant le graphe d'adjacence voulu, puis une
procédure d'affichage
void afficher_graphe_reduit(Liste l);
qui pour chaque composante connexe affiche la suite de ses voisins.
Pour par exemple les composantes connexes
aaaaaaaaaaaaaaaaaaaaa abababababababababaca abababababababababacc ababbbbbbbbbbbbbbbaaa bbbbaaaaaaaaaaaaaaada aaaaaddddddddddddddda addddddddddddddddddda adeeeeeeeeeeeeeeeeeda adefffffffffffffffeda adefgggggggggggggfeda adefghgigjgkglgmgfeda adefgggggggggggggfeda adefffffffffffffffeda adeeeeeeeeeeeeeeeedda addddddddddddddddddaa aaaaaaaaaaaaaaaaaaannon obtiendra l'affichage
a -> b c d n b -> a c -> a d -> a e e -> d f f -> e g g -> f h i j k l m h -> g i -> g j -> g k -> g l -> g m -> g n -> a
/* On suppose que pl!=NULL. */
Graphe recherche_et_insere_composante(int k,Liste *pl);
qui, au lieu de renvoyer la liste éventuellement modifiée, renverra le
Graphe trouvé ou créé, après avoir éventuellement modifié la
liste *pl par le biais du pointeur pl (un
pointeur sur un pointeur !). Modifier reduction en
conséquence.