Structures mutables, union-find et percolation

par Philippe Chassignet

Introduction

Dans ce TD, nous allons définir et manipuler des structures mutables et en particulier la structure dite « union - find » vue en cours. L'application proposée consiste à simuler des phénomènes de percolation.

On considère des grilles carrées formées de nxn cellules. Chaque cellule peut être fermée ou ouverte et on suppose qu'un fluide peut circuler entre les cellules ouvertes adjacentes. On considère ici la 4-connexité où deux cellules sont dites adjacentes si et seulement si elles ont un côté en commun. On dit que deux cellules ouvertes communiquent s'il existe entre elles un chemin passant par une suite de cellules ouvertes adjacentes.
On distingue des cellules ouvertes particulières que l'on va appeler respectivement entrée et sortie (sur les illustrations ce sont les cellules situées respectivement sur la ligne du haut et sur la ligne du bas de la grille). On veut déterminer si, pour une grille donnée, une circulation de fluide peut s'établir entre l'entrée et la sortie, autrement dit s'il existe au moins une cellule d'entrée et une cellule de sortie qui communiquent.
La figure ci-dessous illustre deux exemples de grilles possibles.

Sur cette figure, on a distingué :

en noir, les cellules fermées ; on dira que ces cellules sont dans l'état BLOCKED,
en blanc, les cellules ouvertes qui ne communiquent ni avec l'entrée ni avec la sortie ; on dira que ces cellules sont dans l'état OPEN,
en jaune, les cellules ouvertes qui communiquent uniquement avec l'entrée ; on dira que ces cellules sont dans l'état INPUT,
en rouge, les cellules ouvertes qui communiquent uniquement avec la sortie ; on dira que ces cellules sont dans l'état OUTPUT,
en orange, les cellules ouvertes qui communiquent avec l'entrée et la sortie ; on dira que ces cellules sont dans l'état PERCOLATING,

La seule différence entre les deux grilles illustrées, est l'ouverture d'une cellule qui établit la communication entre une composante qui communiquait uniquement avec l'entrée et une autre composante qui communiquait uniquement avec la sortie.

Une question importante en physique est : étant donnée la probabilité p (uniforme) qu'une cellule soit ouverte (autrement dit la densité des cellules ouvertes), quelle est la probabilité d'observer une percolation ? Il n'existe pas de solution analytique à ce problème, mais on sait qu'il existe un seuil pour p, en dessous duquel la probabilité de percolation est proche de 0 et au dessus duquel la probabilité de percolation est proche de 1. Une expérimentation simple consiste, partant d'une grille dont toutes les cellules sont fermées, à itérer l'ouverture aléatoire de cellules, une à une, jusqu'à atteindre la percolation et à retenir le nombre de cellules alors ouvertes. Une moyenne sur un grand nombre de telles expériences donne une estimation de p.

Pour y parvenir, on notera deux problèmes informatiques :

gérer efficacement les fusions de composantes au fur et à mesure de l'ouverture des cellules. On va utiliser pour cela la structure dite « union - find ».
éviter la répétition d'allocations de mémoire coûteuses. On va utiliser pour cela des structures mutables.

Préparation

Pour commencer, suivant la procédure habituelle,

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

Définition d'une cellule

Codage de l'état d'une cellule

Le fichier State.java contient la définition d'un type énuméré (enum en java) pour coder les états possibles d'une cellule.
L'état d'une cellule sera mutable, mais les seules mutations autorisées seront celles indiquées par les arcs orientés de ce graphe (notez que cela définit une relation d'ordre partiel, on dira que A ≥ B ssi il y a un arc de B vers A dans ce graphe) :

Écrivez dans la classe StateOperation une méthode :

public static boolean allowTransition(State from, State to)

qui renvoie true si et seulement si la mutation de l'état from à l'état to est autorisée (c'est-à-dire qu'il y a un arc de from à to dans le graphe) et qui renvoie false sinon.
On peut tester l'égalité par == (et !=), par exemple, if(from==State.BLOCKED)... et on peut aussi utiliser les constructions de la forme switch(from) { case BLOCKED: ...}.

La méthode test1a de la classe Test permet de vérifier le bon fonctionnement de allowTransition. Son exécution doit afficher le résultat :

 T T T T T
 F T T T T
 F F T F T
 F F F T T
 F F F F T

Lors de la mise en communication de deux composantes, d'état respectif state1 et state2, l'état de la composante résultante peut être défini comme le plus petit majorant de state1 et state2 (on a défini un treillis).
Écrivez dans StateOperation une méthode :

public static State fusion(State state1, State state2)

qui renvoie l'état résultant. La méthode test1b de la classe Test permet de vérifier le bon fonctionnement de fusion. Son exécution doit afficher le résultat :

      BLOCKED         OPEN        INPUT       OUTPUT  PERCOLATING
         OPEN         OPEN        INPUT       OUTPUT  PERCOLATING
        INPUT        INPUT        INPUT  PERCOLATING  PERCOLATING
       OUTPUT       OUTPUT  PERCOLATING       OUTPUT  PERCOLATING
  PERCOLATING  PERCOLATING  PERCOLATING  PERCOLATING  PERCOLATING

Déposez StateOperation.java.

L'objet cellule

Complétez la classe Cell qui définit une cellule. Pour l'instant, une cellule est définie seulement par son état qui sera un champ mutable mais privé et accessible seulement par les 3 méthodes d'objet :

  public State getState()
  public void setState(State newState)
  public void reset()

À sa construction, une cellule est dans l'état BLOCKED. La méthode getState renvoie l'état courant de la cellule. La méthode setState doit vérifier que la transition de l'état courant vers newState est autorisée ; si oui setState réalise cette transition ; dans le cas contraire, elle doit lancer une IllegalArgumentException avec un message explicite. La méthode reset permet de remettre une cellule dans l'état BLOCKED (permettant ainsi ce qui est en général interdit par setState).

La méthode test2 de la classe Test permet de vérifier quelques traits de cette spécification.
Important : Ce test utilise la construction assert de Java et vous devez passer l'option -ea à la machine virtuelle (dans Eclipse, via l'onglet VM Arguments de la configuration de lancement). Le test est correct s'il s'affiche :

Test 2 OK.

Déposez Cell.java.

Structure d'Union-Find

Pour simplifier, on va coder la structure d'union-find directement dans les objets de type Cell.

Ajoutez dans la classe Cell la méthode public static void union(Cell c1, Cell c2) qui réalise la fusion des composantes de c1 et c2. Vous aurez certainement à ajouter des champs qui doivent être privés et la méthode find qui peut être aussi privée car on ne l'utilisera pas en dehors de Cell.
Après un appel à union(c1, c2) :

les appels c1.getState() et c2.getState() doivent renvoyer la même valeur, définie comme le plus petit majorant des états respectifs de c1 et c2 avant l'appel à union,
une modification d'état réalisée par c1.setState(...) doit être visible par c2.getState() et vice et versa.

Immédiatement après un appel c.reset(), l'appel c.getState() doit renvoyer BLOCKED. Le comportement en interaction avec d'autres cellules n'est pas spécifié.
Une boucle faisant c.reset() pour chaque cellule c doit cependant réinitialiser correctement toute la structure, en faisant que chaque cellule soit de nouveau une composante indépendante.

Les méthodes test3a, test3b et test3c de la classe Test permettent de vérifier quelques traits de cette spécification. La méthode test3d permet aussi de vérifier que la structure union-find qui est construite possède les bonnes propriétés du point de vue algorithmique.

Déposez Cell.java.

Définition de la grille

La classe Grid

Complétez la classe Grid qui définit une grille comme un tableau de nxn cellules. Le constructeur prend la dimension n en paramètre et doit initialiser toute la structure. Une fois qu'une grille est construite, la seule opération permise depuis l'extérieur de la classe est la modification de l'état de ses cellules. En particulier, on ne doit pas pouvoir changer les dimensions du tableau ni remplacer une cellule par une autre. Vous devez utiliser au mieux les possibilités de déclaration en Java pour contraindre ce fonctionnement.

Écrivez les 3 méthodes d'objet :

  public int size()
  public Cell getCell(int i, int j)
  public void reset()

La méthode size renvoie la dimension de la grille. La méthode getCell renvoie la référence sur la cellule correspondante de la grille, permettant ainsi d'opérer sur cette cellule (on numérote naturellement à partir de 0). La méthode reset doit réinitialiser toutes les cellules de la grille.

La méthode test4 de la classe Test permet de vérifier le bon fonctionnement de ces méthodes en construisant 3 exemples de grilles et en affichant leur représentation graphique.

Déposez Grid.java.

Simulation de la percolation

Ouverture d'une cellule

Écrivez dans la classe Grid la méthode public Cell open(int i, int j) qui doit réaliser toutes les opérations requises lors de l'ouverture de la cellule située aux coordonnées (i,j) dans la grille. Cette méthode renvoie la référence à cette cellule car cela s'avère pratique pour la suite.
L'état initial de cette cellule est donné par la méthode getInitialOpenState de la grille qui permet notamment de définir où sont les cellules d'entrée et de sortie.
Cette cellule est alors considérée comme formant une composante à elle seule et il s'agit de réaliser les fusions avec les composantes des éventuelles cellules adjacentes.
Si vous en voyez l'utilité, vous pouvez ajouter dans la classe Cell la méthode suivante :

  public void unionIfNotBlocked(Cell c) {
    if (c.getState() != State.BLOCKED)
      union(this, c);
  }

Les méthodes test5a et test5b de la classe Test permettent de vérifier le bon fonctionnement de ces méthodes sur quelques exemples. Les deux appels à test5b qui sont donnés en exemple, produisent les illustrations de l'introduction.

Déposez Grid.java.

Construction d'un ordre aléatoire

Le déroulement d'une expérience va consister à ouvrir une à une et aléatoirement les cellules de la grille, jusqu'à atteindre un état de percolation. Pour de grandes grilles, il ne saurait être question d'utiliser une boucle du genre de celle de test5b, pour écrire :

  réinitialiser la grille
  tant que l'on n'a pas réalisé la percolation
    tirer aléatoirement une cellule
    si cette cellule est fermée, alors l'ouvrir ...

Même si un générateur pseudo-aléatoire congruentiel bien choisi permet de s'assurer de la terminaison de cette boucle, cela peut prendre un temps très long, le nombre de cellules testées pouvant être de l'ordre du carré du nombre de cellules dans la grille.

Il est préférable d'utiliser une structure auxiliaire référençant l'ensemble des cellules et d'écrire :

  réinitialiser la grille
  effectuer une permutation aléatoire de la structure auxiliaire
  tant que l'on n'a pas réalisé la percolation
    prendre la cellule suivante dans l'ordre donné par la structure auxiliaire
    cette cellule est nécessairement fermée, donc l'ouvrir ...

La forme la plus légère est d'utiliser un tableau contenant les entiers de 0 à n²-1 où chaque entier k code la position dans la grille qui est définie par i = k % n et j = k / n.

Écrivez un programme (une classe avec la méthode main) qui permet de mesurer expérimentalement une estimation du seuil de percolation pour des grilles relativement grandes, par exemple 1000x1000 (si vous voulez visualiser de telles grilles, il faut modifier la constante MAXSIZE dans DisplayPanel).
On doit obtenir une bonne estimation, de l'ordre de 0.593, en quelques secondes.

Déposez Percolation.java.