TD-8, Graphes, tri topologique, composantes fortement connexes
|
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 :
-
Pour un graphe de dépendances donné, il peut y avoir plusieurs ordres
topologiques,
car les dépendances peuvent définir un ordre partiel.
- Le parcours du graphe des dépendances selon
Trémaux
(ou en profondeur d'abord) se fait selon un ordre topologique ou selon
l'inverse d'un ordre topologique, ne chipotons pas.
Le but des exercices qui suivent est de deviner les classes compilés par
javac dans diverses situations.
| 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 :
-
Un constructeur StringSet () qui renvoie l'ensemble vide.
- Une méthode :
boolean mem(String s)
pour tester si une chaîne appartient à l'ensemble ou pas.
- Une méthode :
void add(String x)
pour ajouter une chaîne à l'ensemble.
On notera que cette méthode travaille par effet de bord. C'est à dire
que si ``s'' est un ensemble et que l'on effectue
``s.add("coucou")'', la chaîne ``"coucou"'' est ajoutée
à l'ensemble ``s''.
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.
É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 :
-
Se
contenter d'un algorithme « naïf », qui utilise le graphe
inverse et la définition des composantes fortement connexes.
Cette méthode est recommandée, comme étant faisable dans le temps du TD.
Dans ce cas on profitera des
inter, union, etc. de la classe StringSet ;
ainsi que de la méthode elements qui renvoie la liste des
éléments d'un ensemble.
- Ou alors, utiliser l'algorithme linéaire de Tarjan, donné par
l'article distribué la semaine dernière (il reste des copies !)
et dans les transparents de la
petite
classe.
Il faudra alors écrire une classe des Piles de chaînes
(adapter les piles des arcs du le
TD-7) et une autre
des environnements (associations des chaînes aux entiers,
adapter les classes Counter
ou Counter du
TD-1).
Solution.
| Dernière modification :
2002-11-27 |
Ce document a été traduit de LATEX par
HEVEA.
