Algorithme de 3-coloration distribuée

Principe général

Il s'agit d'implémenter l'algorithme de coloration présenté dans le cours/TD. Il fonctionne sous l'hypothèse que chaque sommet connaît n ainsi qu'un de ses voisins, appelé parent.

 → 

3-Coloration distribuée d'un anneau.

Implémentation avec JBotSim

On définit une classe ColoringNode qui hérite de Node. Cette classe contiendra notre algorithme. Pour l'instant, son comportement est très simple : chaque noeud choisit une couleur au démarrage, qui correspond à son identifiant.

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

public class ColoringNode extends Node {
    public Node parent; // défini dans Main()

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

Notre classe comporte aussi un champs parent, que l'on utilisera pour définir la 1-orientation à partir de laquelle on souhaite travailler (cela sera fait en dehors de l'algorithme). Ci-dessous la méthode Main(), qui effectue les traitements suivants:

1. Créer une topologie en anneau formée ici de n=11 noeuds de type ColoringNode.

2. Permuter aléatoirement les identifiants des sommets sur lesquels se base l'algorithme

3. Faire pointer la variable parent de chaque noeud sur le noeud suivant selon le sens des aiguilles d'une montre.

4. Dessiner ces liens de parentées à l'aide d'un LinkPainter dont le code est fourni ici: JParentLinkPainter.java (classe à sauvegarder et à copier dans votre projet en ajoutant une classe à > scr).

5. Mettre en pause la topologie aussitôt dès qu'elle démarre, cela qui permet d'exécuter votre algorithme pas-à-pas.

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 final static int n = 11;
    public static void main(String[] args) {

    Topology tp = new Topology();
    tp.setDefaultNodeModel(ColoringNode.class); // algo des noeuds = ColoringNode
    TopologyGenerators.generateRing(tp, n); // topologie = cycle à n noeuds
    tp.disableWireless(); // pour avoir un vrai anneau pour tout n
    tp.shuffleNodeIds(); // permutation des IDs dans [0,n[

    for (int i = 0; i<n; i++){ // pour chaque noeuds
        ColoringNode u = (ColoringNode) tp.getNodes().get(i); // u = noeuds i
        u.setLocation(u.getX()+250, u.getY()+100); // décaler sa position
        u.parent = tp.getNodes().get((i+1) % n); // son parent
    }

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

Exercices

Q1. Implémenter la fonction private static int posDiff(int x, int y){...} calculant posdiff(x,y), ainsi qu'une fonction private static int log2ceil(int k){...} renvoyant ceil(log_2(k)).

Q2. Implémenter l'algorithme COLOR6.

Q3. Améliorer l'algorithme pour obtenir un 3-coloration pour l'anneau. Pensez à utiliser une variable state permettant de gérer la phase finale pour passer de 6 à 3 couleurs.

Q4. Améliorer l'algorithme pour une version deux fois plus rapide pour l'anneau.

Q5. Raffiner la phase finale de l'algorithme afin d'éliminer les couleurs 5 et 4 en une seule ronde.

Q6 (extra). Etendre l'algorithme pour les 1-orientations avec la procédure SHIFTDOWN.

Q7 (extra). Etendre l'algorithme au cas général avec une D-orientation et une (D+1)-coloration.