Introduction

Dans ce TD, nous allons implémenter un algorithme qui détermine les composantes fortement connexes d'un graphe orienté.

Pour commencer, suivant la procédure habituelle :

• créez un nouveau projet TD6
• téléchargez l'archive td6.zip
• ouvrez cette archive dans le répertoire src du projet TD6, puis rafraîchissez le projet dans Eclipse (touche "F5").

Pour vérifier que tout s'est bien installé, exécutez Test0.java. Vous devriez voir s'afficher le graphe ci-dessous.

Plusieurs classes (du paquetage par défaut) sont déjà fournies, mais la plupart concernent les affichages ou les tests. Seuls trois fichiers sont importants :

• Tree.java : une classe qui décrit un arbre, comme une racine et la forêt de ses sous-arbres,
• Forest.java : une classe qui décrit une forêt comme une liste d'arbres,
• GraphInterface.java : une interface qui décrit les deux seules fonctions que vous utiliserez pour manipuler des graphes. Il s'agit de graphes dont les sommets sont identifiés par des entiers. Ainsi, Iterable<Integer> allVertices>() permet de récupérer tous les sommets du graphe, et Iterable<Integer> successors(int vertex) renvoie la liste des successeurs d'un noeud du graphe. Notez que Java gère automatiquement les conversions entre Integer et int et qu'il est généralement possible de placer une valeur de l'un de ces deux types quand l'autre type est attendu.

Un arbre contient l'indice d'un sommet du graphe (root). Par ailleurs, vous pouvez observer que les définitions de Tree et Forest sont mutuellement récursives : un objet de la classe Tree possède une référence à une forêt, dans laquelle il stocke ses enfants, et un objet de la classe Forest possède une liste de références à des objets de la classe Tree.

Tout le code que vous aurez à écrire sera dans des méthodes statiques de la classe TD6 du paquetage par défaut.

C'est parti

Parcours en profondeur du graphe

Créez la classe TD6, et implémentez une méthode public static Forest computeForest(GraphInterface graph, Iterable<Integer> nodeSet, Set<Integer> visitedVertices) qui, en explorant le graphe à partir des noeuds stockés dans nodeSet, effectue un parcours en profondeur (Depth First Search - DFS) du graphe graph pour construire une forêt. La fonction s'appuiera sur l'ensemble de noeuds visités visitedVertices.
Pour un appel à computeForest devant calculer une forêt couvrante de tout le graphe, nodeSet sera l'ensemble des noeuds du graphe mais, dans d'autres cas, il s'agira d'un ensemble plus restreint. Au retour de computeForest, le contenu de nodeSet sera inchangé. Lors d'un appel initial, visitedVertices est normalement l'ensemble vide. Au retour de computeForest, visitedVertices sera augmenté de tous les noeuds visités durant cet appel. En particulier, tous les noeuds de nodeSet seront marqués visités. Notez que nodeSet peut contenir des noeuds préalablement visités qui, par conséquent, ne seront pas inclus dans la forêt qui est renvoyée par computeForest. Notez aussi que cette forêt peut contenir des noeuds qui ne sont pas dans nodeSet.

Comme les classes Forest et Tree sont mutuellement récursives, il pourra être utile d'écrire une fonction computeTree(...) à la signature bien choisie, et de faire en sorte que les fonctions computeForest(...) et computeTree(...) soient elles-mêmes mutuellement récursives (cad. s'appellent l'une l'autre).

Vous pourrez tester votre fonction en exécutant Test1.java. Vous devrez obtenir l'affichage suivant dans la console :

0
	7
		1
			2
				8
					9
						5
							3
			4
	6

Dans cet affichage, les noeuds alignés verticalement sont à la même profondeur, et l'ordre d'affichage correspond à l'ordre dans lequel les noeuds sont visités. Ainsi, le noeud 0 a pour descendants les noeuds 7 et 6 (visités dans cet ordre), et le noeud 1 a pour descendants les noeuds 2 et 4 (visités dans cet ordre). Le noeud 8 n'a qu'un descendant : le noeud 9. Ce genre d'affichage s'obtient facilement au moyen de deux fonctions mutuellement récursives.

Vous devrez également obtenir l'image suivante.

En commentant et décommentant les lignes appropriées dans Test1.java, vous pourrez tester votre fonction sur d'autres graphes et obtenir, par exemple, l'image suivante (la sortie console correspondante se trouve ici).

Déposez TD6.java.

Reverse post-order

Ajoutez à votre classe TD6 une fonction public static void computeReversePostOrder(LinkedList<Integer> list, Forest forest), qui énumère les sommets d'une forêt en reverse post-order et les stocke dans list. Ici aussi, il pourra être utile d'écrire une deuxième fonction, qui opère sur un arbre.

En exécutant Test2.java, la console devra afficher :

Reverse post-order:
0
6
7
1
4
2
8
9
5
3

Déposez TD6.java.

Inversion de graphe

Ajoutez maintenant dans votre classe TD6 une fonction public static GraphInterface reverseGraph(GraphInterface graph) qui renvoie l'inverse du graphe graph, c'est à dire une copie du graphe original, mais dans lequel les directions des arêtes sont inversées.

En testant avec Test3.java, vous pourrez vérifier que les deux graphes affichés sont inverses l'un de l'autre, comme sur les images ci-dessous.

Déposez TD6.java.

Calcul des composantes fortement connexes

Enfin, ajoutez dans votre classe TD6 une fonction public static Forest computeStronglyConnectedComponents(GraphInterface graph), qui calcule les composantes fortement connexes d'un graphe graph selon l'algorithme suivant :

• foret1 est la forêt résultant d'un parcours en profondeur du graphe graph en partant de tous les noeuds du graphe, dans un ordre quelconque
• reversedGraph est l'inverse du graphe graph
• rpo est le reverse post-order de foret1
• foret2 est la forêt résultant d'un parcours en profondeur du graphe reversedGraph en partant de tous les noeuds du graphe, selon l'ordre défini dans rpo

A la fin de cet algorithme, les arbres de foret2 sont les composantes fortement connexes du graphe graph.

En testant avec Test4.java, vous devrez obtenir les images ci-dessous (une couleur par composante fortement connexe - trois dans cet exemple). Ici aussi, vous pourrez tester avec les autres graphes proposés en commentaire dans le test, voire en construisant vos propres graphes.

Déposez TD6.java.