Algorithme de coloration pour les grilles
et au-delà

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 étape au fur et à mesure.

• Étape 1. Calcul de $n$ et de $d$, qui sera à faire dans le Main après la génération/chargement du graphe, de manière séquentielle et globale donc. Cette étape est déjà programmée pour vous. Vous n'avez rien à faire. Les deux variables sont les deux seules à être globales, toutes les autres doivent être locales à chaque sommet, donc à définir dans ColoringNode.
• É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. Pour faire simple, on supposera que le graphe ne change pas au cours de l'exécution, notamment que les voisins d'un sommets ne changent plus une fois que démarre l'algorithme distribué.
• É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 définie par l'entier $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'efficacité des l'étapes 5 et 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. Pour cela servez-vous des topologies fournies en exemples qui sont à placer dans le répertoire du projet. Il est aussi possible de spécifier le chemin complet au fichier dans la méthode .read(...).

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.

La class Main de JBotSim devrait ressembler à ceci:

import io.jbotsim.core.Topology;
import io.jbotsim.core.Node;
import io.jbotsim.ui.JTopology;
import io.jbotsim.ui.JViewer;

public class Main {
  public static int n; // n = nombre de sommets
  public static int d; // d = degré maximum du graphe

  public static void main(String[] args) {

    Topology T = new Topology(680,540); // fenêtre de w x h pixels
    T.setDefaultNodeModel(ColoringNode.class); // algo des sommets = ColoringNode
    String s = T.getFileManager().read("grille-2x7"); // lecture du fichier
    T.getSerializer().importFromString(T,s); // initialisation du graphe
    T.shuffleNodeIds(); // permutation des IDs dans [0,n[

    // initialisation de n et de d
    n = T.getNodes().size();
    d = 0;
    for (Node v : T.getNodes())
      d = Math.max(d,v.getNeighbors().size());
    System.out.println("n="+n+", d="+d);

    // fixe n et d pour tous les sommets
    ColoringNode.n = n;
    ColoringNode.d = d;

    JTopology J = new JTopology(T);
    new JViewer(J);  // dessine la topologie
    T.start();       // démarre l'aglorithme
    T.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 avec telle ou telle étape afin de les comparer. Si possible affichez sur une ligne ces nombres 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

Il est important que l'algorithme soit distribué, évidemment. La seule partie "non distribuée" concerne l'étape 1 et le calcul de $n$ et $d$, ce qui est déjà fait dans la class Main. Toutes les autres étapes doivent impérativement être distribuées. Vous ne devez pas utiliser d'autres variables globales qui pourraient servir à communiquer autrement que par des messages, ce qui reviendrais à "tricher". En particulier, vous n'avez pas le droit d'utiliser les méthodes du type getNeighbors() basée sur la topologie. En effet, elles font appellent au graphe qui est une donnée globale. Pour récupérer les voisins et implémenter l'étape 2, il faudra les stocker explicitement à l'issu de la réception d'un premier message par exemple.

Les étapes 2 et suivantes 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() {...}. On récupère les messages envoyés avec send() ou sendAll() grâce à getMailBox(). Au départ l'algorithme pourra commencer par initialiser certaines variables locales au sommet, comme sa couleur, en surchargeant onStart() {...}, sans oublier d'émettre un premier message, sans quoi rien ne se passera.

Vous n'avez pas à connaître plus profondément les subtilités du simulateur. Donc à part les méthodes déjà citées, vous n'aurez à utiliser que les routines comme setColor, .getColorAt(), .getID() et éventuellement getTime().

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

public class ColoringNode extends Node {

  public static int n, d; // constantes communes à tous les sommets

  @Override // au départ
  public void onStart() {
    setColor(Color.getColorAt(getID())); // couleur = ID
    ...
    // ne pas oublier d'envoyer un premier message
  }

  @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.

FIN.