TD-8, graphes
Programmes Prenom.Nom.c à déposer par ftp sur poly en /users/profs/maranget/TD-8.
1 Lecture et sauvegarde d'un graphe
Les exercices de cette semaine se feront à l'aide de la représentation
des graphes par leur matrice d'adjacence.
Or, il est bien plus commode pour un être humain de donner un graphe en
spécifiant la liste des successeurs de chaque sommet.
On vous demande donc d'écrire un programme qui lit un graphe sous la
forme de listes de successeurs et le sauve sous forme d'une matrice
d'adjacence dans un fichier de nom graphe.
Donc, considérons un graphe pris au hasard, par exemple :
On le rentrera par une procédure à peu près similaire à celle-ci :
nombre de sommets : 5
1 : 3 4 2 0
2 : 0
3 : 4 5 0
4 : 2 5 0
5 : 2 0
À la fin de l'exécution du programme, le contenu du fichier graphe
ressemblera à ceci :
5
0 1 1 1 0
0 0 0 0 0
0 0 0 1 1
0 1 0 0 1
0 1 0 0 0
Voici quelques points de programmation pour vous aider.
- Le type des graphes sera le suivant :
#define NMAX 32
typedef struct {
int n; /* avec 0 <= n <= NMAX */
int mat[NMAX][NMAX];
} Graph;
- Pour ouvrir un fichier on utilise la fonction de
bibiothèque
fopen
.
SYNOPSIS
#include <stdio.h>
FILE *fopen(char *path, char *mode);
DESCRIPTION
The fopen function opens the file whose name is the string
pointed to by path and associates a stream with it.
The argument mode points to a string beginning with one of
the following sequences (Additional characters may follow
these sequences.):
r Open text file for reading. The stream is posi-
tioned at the beginning of the file.
w Truncate file to zero length or create text file
for writing. The stream is positioned at the
beginning of the file.
....
RETURN VALUES
Upon successful completion fopen returns a FILE pointer.
Otherwise, NULL is returned.
- Soit une variable
fp
dont la déclaration est
FILE *fp
(autrement dit fp
est un pointeur vers la représentation
en C d'un fichier).
-
Si
fp
pointe vers un fichier ouvert en écriture, on peut écrire
un entier i par fprintf(fp,"%d",i)
.
- Si
fp
pointe vers un fichier ouvert en lecture, on peut lire
un entier et le ranger dans une variable i par
fscanf(fp,"%d",&i)
. (Cette indication servira pour l'exercice
suivant.)
- Une fois que l'on a finit d'écrire ou de lire dans un
fichier
fp
, il faut le
fermer par l'appel de fonction de bibliothèque fclose(fp)
.
Une solution apparaîtra en tab.txt.
2 Tri topologique
Le tri topologique d'un graphe produit la liste des sommets d'un
graphe dans un ordre tel qu'un sommet est affiché avant tous ceux qui
peuvent être atteints à partir de lui.
Par exemple dans le cas du graphe déjà dessiné, un tri topologique
possible est :
1 3 4 5 2
Pour nous fixer un peu les idées,
supposons que ce graphe représente les contraintes sur certaines
tâches, c'est à dire que, par exemple, la tâche numéro 3 doit être
effectuée avant les tâches 4 et 5, mais après la tâche 1.
Alors, le tri topologique fournit un ordonancement des tâches qui est
compatible avec leurs dépendances.
Votre programme lira le graphe contenu dans le fichier de nom graphe et effectuera un tri topologique de ce graphe.
Plus précisément :
-
Les sommets
seront affichés dans l'ordre inverse de celui du tri topologique
(c'est légèrement plus facile).
En effet, pour trouver un premier sommet de cette
liste inverse, il suffit de trouver une ligne de la matrice
d'adjacence qui ne contient que des zéros. Vous exploiterez cette
remarque pour produire le tri topologique inverse complet.
(Pour trouver le premier sommet du tri topologique, il suffit de
trouver une colonne de la matrice qui ne contient que des zéros.)
- Dans le cas où le graphe contient un cycle, le
tri topologique n'est pas possible. Votre programme devra identifier
ce cas et le signaler.
Pour tester un peu plus votre programme, voici un autre graphe à
21 sommets. Ce graphe
représente les dépendances entre les chapitres d'un célebrissime
ouvrage d'informatique fondamentale (cf. le poly, page 181).
Au lieu de rentrer vous-même ce graphe, vous pouvez utiliser le
fichier graphe.txt.
Voici un tri topologique inverse possible pour ce graphe :
12 13 20 21 17 16 15 19 10 9 8 7 6 14 11 18 1 5 4 3 2
Note : votre programme, s'il ressemble à la
solution, sera en
O(n2). Il existe un tri topologique en O(n), mais il faut alors
utiliser la représentation des graphes par listes de successeurs.
3 Composantes fortement connexes
Considérons un graphe cette fois cyclique :
En raison du cycle entre les sommets 3, 4 et 5, il n'est plus
possible d'effectuer le tri topologique.
On définit ensuite la relation de connexité forte entre les sommets
d'un graphe G: deux sommets i et j sont fortements connexes
s'ils sont égaux ou s'il
existe un chemin de i vers j et un chemin de j vers i.
Cette relation est naturellement une relation d'équivalence et on
appelle ``composantes fortements connexes'' ses classes
d'équivalences. Les composantes fortement connexes sont en quelque
sorte les cycles du graphe.
Les composantes fortement connexes de G peuvent être calculées
relativement facilement à partir de la fermeture transitive G* du
graphe G. En effet et par définition, deux sommets de G sont fortement
connexes, si et seulement si il sont reliés par deux arcs réciproques
de G*.
On demande donc d'écrire un programme qui :
-
lit un graphe G contenus dans le fichier graphe.
- calcule G* en utilisant par exemple la méthode de Warshall
(voir le cours),
- calcule en les affichant les composantes fortement connexes de G.
Pour ce faire, on calculera un tableau
int r[NMAX]
, tel que
r[i] == r[j]
, si et seulement si i et j sont
fortements connexes.
Dans le cas de notre graphe, on obtiendra :
1
2
3 4 5
Note : votre programme, s'il ressemble à la
solution, sera en
O(n3). Il existe un algorithme en O(n), mais il est réellement
très astucieux.
Ce document a été traduit de LATEX par
HEVEA.