TD-8, Graphes, tri topologique, composantes fortement connexes




Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-8

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

1 Dépendances dans la compilation
Dans la plupart des langages de programmation, lorsqu'un programme se compose de plusieurs fichiers, certains fichiers, pour être compilés peuvent avoir besoin du résultat de la compilation d'autres fichiers. Cela impose de compiler les fichiers dans un ordre compatible avec leurs dépendances.

En Java, c'est le compilateur javac qui effectue lui même ce travail. Supposons, pour simplifier que les fichiers contiennent toujours une unique classe homonyme, et qu'aucune classe n'est déjà compilée. Dans ce cadre, si la classe A utilise des objets de la classe B et que l'on souhaite compiler A, alors le compilateur javac compilera d'abord la classe B, puis la classe A.

On représentera les dépendances ainsi :
A: B
B: C D
C: D
Chaque classe étant suivie des classes dont elle dépend. La relation de dépendance s'exprime naturellement par un graphe.
Dans cet exemple, si on veut compiler A, alors il faut d'abord compiler D (car C en dépend), puis C (car B en dépend), puis B (car A en dépend) et enfin on peut compiler A. Ce que l'on peut représenter par la séquence de commandes :
javac D.java
javac C.java
javac B.java
javac A.java
Tout ordre compatible avec les dépendances du graphe est dit ordre topologique (du graphe) et sa production est un tri topologique. On remarquera : Le but des exercices qui suivent est de deviner les classes compilés par javac dans diverses situations.

2 Dépendances simples

2.1 Environnement de programmation
Nos graphes sont très semblables à ceux que nous avons déjà vus (encodage par les listes de successeurs), à l'exception des étiquettes des sommets qui sont des chaînes (le nom des classes). Nous fournissons trois classes, Graphe les graphes, StringSet (ensembles de chaînes) et StringList (listes de chaînes).

Parmi, les méthodes exportées par la classe Graphe on notera les suivantes : La classe StringSet exporte entre autres : Quant à la classe StringList, elle est on ne peut plus classique. En outre les trois classes données possèdent une méthode toString, utile pour mettre vos programmes au point.

Ne perdez pas de temps à lire le source de ces trois classes dont les méthodes font ce qu'on attend d'elles. Disons qu'elles utilisent largement la clé anglaise de la programmation : la table de hachage.

2.2 Ce qui est demandé
Écrivez une classe Make qui donne les compilations effectuées par javac dans le cas simple décrit à la section 1. La classe à compiler sera le premier argument de la ligne de commande et le fichier des dépendances sera lu sur l'entrés standard. Ainsi, avec les dépendances .a on obtiendra :
maranget@manche ~/TD/TD-8 > java Make A < .a
javac D.java
javac C.java
javac B.java
javac A.java
Essayez aussi la compilation de ``latexmain'' et de ``cutmain'' avec cet autre fichier de dépendances .depend. Vous devriez obtenir respectivement 41 et 11 commandes javac.

Un autre test consiste à compiler la classe Make elle même, à l'aide de ces dépendances .TD-8.

Solution.

3 Évitez les recompilations inutiles
Lorsque les fichiers .class sont déjà présents, le programme Make de la section précédente effectue des recompilations inutiles. En effet, si A.class existe et que la classe A ne dépend d'aucune autre, on ne doit recompiler A.java que si le fichier A.class est plus vieux que le fichier A.java.

Notez que l'on devra également, dans ce cas, (re-)compiler toutes les classes qui dépendent de A, pour vérifier qu'elles sont toujours compatible avec la nouvelle classe A. Notez encore, qu'inversement et pour la même raison, si A dépend d'au moins une classe qui doit être recompilée, alors il faut également recompiler A.java, même si A.class est à jour par rapport à A.java.

Pour tester les conditions sur les fichiers, on utilisera le constructeur File(String) et les méthodes exists et lastModified de la classe File du package java.io.

Ce programme est plus difficile à tester que le précédent car il ne fonctionne que si les fichiers ``.java'' existent. On pourra toute même faire :
maranget@manche ~/TD/TD-8 > touch StringSet.java
maranget@manche ~/TD/TD-8 > java TimeMake Make < .TD-8
javac StringSet.java
javac Graphe.java
javac Make.java
(La commande touch change la date de modification d'un fichier).

On encore mieux, effectuer réellement les (re-)compilations nécessaires :
maranget@manche ~/TD/TD-8 > touch StringSet.java
maranget@manche ~/TD/TD-8 > java TimeMake Make < .TD-8 | sh -x
+ javac StringSet.java
+ javac Graphe.java
+ javac Make.java
maranget@manche ~/TD/TD-8 > java TimeMake Make < .TD-8 | sh -x

(Le shell sh exécute les commandes, son option -x raconte ce qui se passe).

Vous remarquerez (en comparant avec touch StringSet.java ; javac -verbose Make.java) que, dans la même situation, javac ne recompile pas Graphe.java, j'en pense du mal, et vous ?

Solution.

4 Dépendances circulaires
Oublions les compilations réelles et revenons aux graphes de dépendance. On ajoute un arc au graphe de la section 1 (entre D et C). Soit :
A: B
B: C D
C: D
D: C
Ou encore :
Notre programme Make de la section 2 fonctionne toujours, ce qui est assez gonflé de sa part car, pour de telles dépendances, on ne peut ni compiler C avant D, ni compiler D avant C.

On supposera que nous disposons d'un compilateur javac hyper-intelligent qui compile simultanément C et D, sans plus se demander qui dépend de qui, par javac C.java D.java. On supposera aussi que le temps de compilation de ce javac croît abominablement avec le nombre de fichiers passés en argument (ce qui interdit de résoudre le problème par javac *.java). Et on recherchera toujours à compiler les classes dans l'ordre inverse de leur dépendances.

Réaliser le programme FullMake qui nourrit ce génial compilateur : Avec les dépendances .b, On obtiendra :
maranget@manche ~/TD/TD-8 > java FullMake A < .b
javac C.java D.java
javac B.java
javac A.java
Essayer aussi les dépendances .d.
Ça devrait donner :
maranget@manche ~/TD/TD-8 > java FullMake H < .d
javac E.java
javac F.java G.java
javac A.java B.java C.java D.java
javac H.java
maranget@manche ~/TD/TD-8 > java FullMake B < .d
javac E.java
javac F.java G.java
javac A.java B.java C.java D.java
Indication : Le programme FullMake indiquera les compilations, composante fortement connexe par composante fortement connexe et dans l'ordre des dépendances du graphe.

Pour calculer les composantes fortement connexes, on pourra : Solution.


Dernière modification : 2002-11-27

Ce document a été traduit de LATEX par HEVEA.