Solutions du TD-8, Graphes

Tout d'abord, précisons un peu le comportement de javac par rapport aux dépendances entre fichiers. Ce compilateur ``suit'' le dépendances entre fichiers au premier niveau, c'est à dire que, dans le cas de ces dépendances :
La commande javac A.java n'entraîne que la vérification de B.class par rapport à B.java. Toutefois, si on donne l'option ``-depend'', alors l'ensemble des dépendances est vérifié. Ce qui peut prendre du temps.

L'approche de ce TD utilise des fichiers de dépendances fabriqués par ailleurs (avant compilation). Cette appproche amène des recompilations plus rapides, en cas de changement de quelques fichiers seulement, car il n'est plus utile de relire tous les fichiers pour en extraire toutes les dépendances. Inconvénient : il faut faire attention à maintenir les dépendances à jour. La plupart des compilateurs sous Unix fournissent une option ou un utilitaire spécifique, qui extrait les dépendances des fichiers sources. Ces dépendances sont ensuite utlisées par l'utilitaire Unix make, indispensable au développement de programmes qui comprennent plus que quelques fichiers sources.

1  Dépendances simple

Étaient données les classes StringList, StringSet et Graphe.

La solution est une classe Make, vraiment simple. Elle comporte essentiellement une méthode topo, qui effectue un parcours en profondeur d'abord. 
  static void topo(String x, StringSet visite) {
    if (visite.mem(x))
      return ;
    visite.add(x);

    for (StringList l = make.getSucc(x) ; l != null ; l = l.suivant)
      topo(l.cont,visite);
    System.out.println("javac " + x + ".java") ;
  }
Par rapport aux transparents, on note une modification cosmétique les sommets visités sont enregistrés dans l'ensemble de chaînes visite, tandis que les transparents utilisent un tableau de booléens indexé par les numéros des sommets. Au fond c'est pareil.

Sur le fond, on note que la commande ``javac x.java'', est émise après le parcours de tous les successeurs du sommet étiqueté par x. Soit, à condition que le graphe ne contienne pas de cycle, après compilation de toutes les classes dont x dépend.

2  Recompilation

La solution est une classe TimeMake, plus compliquée, mais qui utlise le même algorithme que la classe Make. La différence est que la recompilation n'est ici pas sytématique, il y a deux conséquences :
  1. La méthode topo renvoie un booléen qui signale si le parcours du sous-graphe a donné lieu à au moins une recompilation ou non. 
      static boolean topo(String x, StringSet visite, StringSet changed) {
    if (visite.mem(x))
      return changed.mem(x) ;
    visite.add(x);

    // Passer aux voisins
    boolean r = false ;
    for (StringList l = make.getSucc(x) ; l != null ; l = l.suivant)
      r = topo(l.cont, visite, changed) || r;

    r = r || testFiles(x) ;
    if (r) {
      changed.add(x) ;
      System.out.println("javac " + x + ".java") ;      
    }
    return r ;
  }
    On notera, que dans le cas où x appartient à visite, cela signifie que le sommet d'étiquette x a été vu. Si le graphe ne comporte pas de cycle, cela entraîne que le sous-graphe issu de x a été complètement visité et que le cas de x est réglé. Le souvenir de ce traitement est sauvé dans l'argument changed qui est l'ensemble des classes recompilées.

    On notera aussi que dans l'expression ``topo(l.cont,...) || r'' l'appel récursif a toujours lieu, ce ne serait pas le cas pour l'expression r || topo(l.cont,...).

  2. Indépendamment des dépendances d'une classe x, sa recompilation est initiée par un test sur les fichiers x.java et x.class : 
    /* Renvoie true si x.class est inexistant ou plus à jour */
  static boolean testFiles(String x) {
    File fjava = new File (x + ".java") ;
    File fclass = new File (x + ".class") ;
    if (! fjava.exists()) {
      System.err.println ("Don't know how to make ``" + x + ".java''") ;
      System.exit(-1) ;
    }
    if (fclass.exists ())
      return fjava.lastModified() > fclass.lastModified() ;
    else
      return true ;
  }

3  Composantes fortement connexes

3.1  Algorithme naïf

Ça se corse un peu avec cette classe FullMake, qui n'utilise pas l'algorithme efficace.

Essentiellement le programme calcule le graphe imake, inverse du graphe des dépendances make. Puis lance un parcours récursif du graphe qui, pour chaque sommet, calcule sa composante fortement connexe selon la formule triviale.

Un effort est fait pour ne pas recalculer plus d'une fois les composantes fortement connexes (utlisation de l'ensemble incfc).

Les méthodes inverse et calculeVisite on été ajoutées à la classe Graphe, pour réaliser respectivement la construction du graphe inverse et le calcul des sommets atteignables à partir d'un sommet passé en argument. On notera que cette dernière méthode est le parcours en profondeur d'abord le plus dépouillé possible.

3.2  Algorithme de Tarjan

La solution est le source Tarjan, avec les piles Stack et les environnements Env.

La classe Stack implémente la piles par un tableau et un indice sp. La taille de ce tableau croît automatiquement si nécessaire (méthode check).

La classe Env est particulièrement concise car elle utlise la classe Hashtable du package java.util. Ceci impose de transformer les scalaires int en objets de la classe Integer (car les tables de hachage de la librairie Java contiennent des objets). Ceci impose aussi une conversion de type dans la méthode get, car les tables de hachage de la librairies peuvent contenir n'importe quel objet.

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