Algorithme de coloration pour les grilles

Consignes pour le TP noté

Lors de ce TP individuel qui va être évalué vous pourrez bien sûr utiliser vos notes de cours et aussi les notes de cours disponibles via la page du cours. Le problème de la coloration est traité au chapitre 7 à partir de la page 101. Vous pouvez également ré-utiliser votre code du TP de décembre et des aides en lignes sur JBotSim ou Java si nécessaire. Mais vous ne pouvez pas, bien évidemment, communiquer sous une quelconque forme avec vos camarades.

À la fin du TP, il faudra envoyer par courriel vos contributions à gavoille@labri.fr contenant deux fichiers sources .java: celui contenant le Main et celui contenant l'algorithme distribué, la classe qui étend la class Node.

Vous pouvez ajouter des commentaires au code source afin de préciser ce que vous voulez faire, voir ce que vous vouliez faire et que vous n'avez pas réussi à faire. Ne mettez pas de commentaires dans le coprs du courriel.

Il est important que votre code soit "fonctionnel", cela sera un élément de notation. J'entends par là qu'il compile et fasse quelque chose a priori sans erreur d'exécution. Bien sûr, il s'agit d'aller le plus loin possible dans le sujet, mais si une extension ne marche pas, commenter là tout simplement en expliquant où vous êtes arrêté, ce qu'il ne marche pas justement (vous pouvez très bien avoir des points sur une partie qui ne marche pas). Encore une fois, la partie non-commentée devra être fonctionnelle.

Principe général de l'algorithme

Il s'agit d'implémenter un algorithme de $(d+1)$-coloration pour un graphe quelconque de degré maximum $d$, valeur qui sera supposée être connu de tous les sommets, tout comme le nombre de sommets $n$. Pour cela on procède en plusieurs étapes, qu'il est préférable de réaliser dans cet ordre. Pensez tester chaque étapes au fur et à mesure.

Étape 1. Calcul de $n$ et de $d$, qui sera à faire dans le Main après la génération du graphe, de manière séquentielle donc.
Étape 2. Sélection des parents. Il s'agit de définir pour chaque sommet $u$ un vecteur de parents $(p_0,p_1,...,p_{d-1})$. Il faudra gérer le fait que $u$ n'est pas forcément de degré $d$ exactement, et donc que certains voisins $p_i$ ne sont pas définis.
Étape 3. Calcul parallèle d'une 6-coloration. Chaque parent $p_i$ induit dans le graphe une 1-orientation pour laquelle on itère la fonction pos_diff(x,y) entre les couleurs x de $u$ et y du parent de $u$ dans l'orientation considérée. Il est impératif de gérer correctement la couleur y dans le cas où ce parent n'existe pas. Bien évidemment, la couleur initiale de $u$ doit être initialisée à son identifiant.
Étape 4. Transformation du vecteur de 6-coloration en une seule couleur. Il s'agit de convertir le vecteur $C = (c_0,c_1,...,c_{d-1})$, où chaque $c_i \in [0,6[$ est la couleur de $u$ dans la 1-orientation induite par la $i$-ème relation de parenté, en une couleur unique de $[0,6^d[$. Une façon simple de le faire est d'associer à $u$ la couleur $c(u) = c_0 + 6 \cdot c_1 + 36 \cdot c_2 + \cdots = \sum_{i=0}^{d-1} 6^i \cdot c_i$. Programmez une fonction vector_to_color(C) pour cela. Notez bien que $c_i$ doit être défini pour que la formule ait un sens et que poser $c_i = 0$ dans ce cas n'est pas toujours la solution.
Étape 5. Réduction de palette. De manière classique comme vu en cours, on réduit progressivement la palette de $[0,6^d[$ à $[0,d+1[$ en supprimant chaque couleur $i\in [d+1,6^d[$. Pour cela seuls les sommets de couleur $i$ appliquent la fonction first_free(X) sur la liste X des couleurs des voisins de $u$. Vous pourrez programmer une fonction pour cela. Pour une implémentation efficace, pensez à trier la liste X.
Étape 6. Réduction rapide de palette. Cette étape est une amélioration de l'étape précédente. Elle est plus complexe mais diminue significativement le nombre de rondes de communications. Au lieu de prendre $6^d - (d+1)$ rondes, elle n'en prendra que $O(d^2)$. Le principe de cette étape est détaillé à la fin du sujet.

Ce que vous devez faire

L'objectif est d'aller le plus loin possible dans les étapes. Idéalement, on aimerait comparer l'étape 5 à l'étape 6. Si vous arrivez à l'étape 6 pour un graphe G quelconque, c'est parfait ! Mais, pour faire simple, vous pourrez commencer à programmer les différentes étapes en supposant que le graphe G est une grille $p\times q$ composée de $p$ lignes de $q$ sommets.

Commencez par considérer les grilles $1\times q$, qui ne sont autres que des chemins à $q$ sommets, pour différentes valeurs de $q$. Cela vous donnera des exemples de graphes pour le cas basic $d=2$. (Notez que vous avez résolu le cas $d=1$ lors du dernier TP.) Puis passez à des grilles $2\times q$ avec $q\ge 2$, pour le cas $d=3$. Enfin, passez aux grilles $p\times q$ avec $p,q \ge 3$ pour $d=4$. Notez que pour $d = 4$, l'étape 5 prend à elle seule $6^4 - 5 = 1\,291$ rondes, ce qui justifie l'amélioration avec l'étape 6.

Le Main de JBotSim devrait ressembler à ceci:

NB: Par rapport au TP de décembre, on n'utilisera pas le champs .parent des sommets, car il y a plus d'un parent, ni la flèche représentant l'orientation vers ce parent. Au passage on s'arrange pour que les IDs soient une permutation aléatoire de $[0,n[$.

import io.jbotsim.core.Topology;
import io.jbotsim.gen.basic.TopologyGenerators;
import io.jbotsim.ui.JTopology;
import io.jbotsim.ui.JViewer;

public class Main {
  public static int n;      // n = #nodes
  public static int d;      // d = degré maximum du graphe
  public static int p = 1;  // p = #lignes
  public static int q = 10; // q = #colonnes

  public static int parent(int u, int i){

    // Renvoie l'indice du i-ème voisin du sommet d'indice u d'une grille pxq
    // et -1 s'il n'existe pas. Il faut i = 0,1,2,3
    //
    //     2        indice u d'un sommet v = entier de [0,n[
    //     |        sommet v = ColoringNode v
    //  0--u--1     identifiant d'un sommet v = v.getID() = entier quelconque
    //     |        indice d'un sommet v = v.getTopology.getNodes().indexOf(v)
    //     3        sommet d'un sommet v d'indice u = tp.getNodes().get(u)

    if( i < 0 || i > 3 ) return -1;
    int x = (int)(u%p); // u -> (x,y)
    int y = (int)(u/q);
    if( i < 2 ) x += 2*i-1; // x-1 ou x+1
    if( i > 1 ) y += 2*i-1; // y-1 ou y+1
    if ( x >= 0 && x < q && y >= 0 && y < p ) return x+y*q; // (x',y') -> u'
    return -1;
    }

  public static void main(String[] args) {

    Topology tp = new Topology();
    tp.setDefaultNodeModel(ColoringNode.class); // algo des noeuds = ColoringNode
    TopologyGenerators.generateGrid(tp, q, p);  // topologie = grid pxq

    n = tp.getNodes().size();                   // calcul de n
    d = ...					// calcul de d à faire

    // ID aléatoires dans [0,n[
    int [] P = new int[n];
    for (int i = 0; i < n; i++) P[i] = i;             // P = {0,1,2,3,...,n-1}
    for (int i = 0; i < n; i++) {
      int j = i+(int)Math.floor(Math.random()*(n-i)); // choisit j dans [i..n[
      tp.getNodes().get(i).setID(P[j]);               // ID(i) = P[j]
      P[j] = P[i];                                    // "échange" P[i] et P[j] 
    }

    JTopology jtp = new JTopology(tp);
    new JViewer(jtp); // dessine la topologie
    tp.start();       // démarre l'aglorithme
    tp.pause();       // mode pas-à-pas
  }
}

Votre programme devra afficher, sur la console, le nombre de rondes qu'il a exécuté pour produire la $(d+1)$-coloration souhaitée. Si possible affichez sur une ligne ce nombre pour chaque sommet au format ID:#rondes comme par exemple: 0:27, 1:27, 2:27 .... Notez que les IDs ne s'afficheront pas forcément dans l'ordre cet ordre et qu'en principe le nombre de rondes devrait identique pour tous les sommets.

Implémentation de l'algorithme

L'étape 1 n'est pas distribuée et doit être implémentée dans le Main. Les autres définissent l'algorithme distribué à proprement parlé et doit étendre la classe Node. Comme nous considérons le modèle LOCAL, l'algorithme distribué devra être contenu dans la surcharge @Override onClock() {...}. Au départ l'algorithme pourra commencer par initialiser certaines variables locales au sommet, comme son degré et sa couleur, en surchargeant onStart() {...}, sans oublier d'émettre un premier message, sans quoi rien ne se passera.

import io.jbotsim.core.Color;
import io.jbotsim.core.Message;
import io.jbotsim.core.Node;

public class ColoringNode extends Node {

  // variables définies dans Main()
  public int n;
  public int d;

  @Override // au départ
  public void onStart() {
    setColor(Color.getColorAt(getID())); // couleur = ID
    ...
  }

  @Override // à chaque top horloge
  public void onClock() {
    ...
  }

}

Pensez à définir pour chaque sommet $u$ une variable (locale au sommet) permettant de savoir dans la méthode OnClock() à quelle étape se trouve $u$, notamment lorsqu'il a terminé.

L'étape 6: réduction rapide de palette

Cette étape généralise et remplace l'étape 5. On suppose qu'après l'étape 4, on a obtenu une $k$-coloration $c$, donc que pour tout sommet $u$, $c(u) \in [0,k[$. Plutôt que de supprimer chaque couleur une par une, avec un first_free(X) sur l'ensemble X des couleurs de ses voisins, on essaye de supprimer plusieurs couleurs simultanément. Soit $s$ le plus grand entier tel que $k \ge sd + s$, ce qui revient à dire que $s = \lfloor{k/(d+1)}\rfloor$. Les $s$ couleurs en fin de palette, plus précisément toutes celles de l'intervalle $[k-s,k[$, sont dîtes spéciales et vont être supprimées en une seule ronde comme ceci.

Pour un sommet $u$ de couleur spéciale, cette ronde consiste d'abord à calculer la liste $X$ des couleurs de ses voisins. Puis $u$ se recolorie avec un first_free($X \cup [0,rd[$) où $r$ est le rang de la couleur de $u$ parmi les couleurs spéciales. La couleur spéciale $k-s$ est de rang $0$, la couleur $k-s+1$ est de rang $1$, ... et la dernière couleur de la palette, $k-1$, est de rang $s-1$. De manière générale, $r = c(u)-(k-s) \in [0,s[$. On posera aussi $r=0$ dans le cas où $X$ ne contient aucune couleur spéciale, puisque dans ce cas aucun voisin de $u$ ne peut être en conflit en appliquant en parallèle un first_free. Notez que si $s=1$, et donc que $k < 2d+2$, cela revient à appliquer l'étape 5 en supprimant qu'une seule couleur à la fois.

Au final, l'étape 6 consiste à répèter cette réduction élémentaire, en réévaluant le nouveau $k \leftarrow k-s$ et le nouveau $s$, jusqu'à obtenir $k = d+1$. Notez qu'à l'instar de la variable $\ell$ dans l'algorithme 6COLOR du cours, à chaque ronde, les valeurs $k$ et $s$ doivent être identiques pour tous les sommets, faute de quoi des sommets voisins risqueraient d'appliquer des first_free() conflictuels à cause du rang de leurs couleurs qui dépend de ces deux valeurs.