Algorithme de détection de C3 et C4

Principe général de l'algorithme

Il s'agit d'implémenter l'algorithme vu en cours et disponible sur les notes de cours sur la page de cours. On rappelle qu'il comporte 3 phases. Les deux premières sont des rondes classiques alors que la troisième correspond à l'envoi d'un ensemble d'identifiants.

Ce que vous devez faire

Vous devez créer un projet avec une class Main et une class DetecC34 qui étend la class Node, l'algorithme distribué à proprement parler (voir les deux aperçus de code ci-après). C'est surtout le code de DetectC34 que vous allez devoir éditer. À la fin de l'algorithme, il faudra visualiser en coloriant différemment les sommets lors des différentes sorties possibles, à minima ceux avec leur variable detect=true et ceux avec detect=false. Mais il sera intéressant de distinguer les autres cas: sommets qui sont bleus (variable b=true) ou rouges (b=false) à la fin de la ronde 1, sommet qui détecte un C4, un C3, ou de manière indéterminée un C3 ou un C4. Il faudra bien sûr tester votre algorithme sur plusieurs topologies. Pour ce faire, vous pourrez: (1) commenter les trois lignes du Main après T.setDefaultNodeModel(), (2) éditer un graphe particulier (avec des parties plus ou moins denses), (3) le sauvegarder dans un fichier pour pouvoir le charger avec T.getFileManager().read("...").

Quelques points de vigilance

  • L'algorithme doit fonctionner selon le modèle CONGEST, c'est-à-dire en mode synchrone où chaque message est de taille limité. Typiquement, chaque message devrait comporter au plus un identifiant ou une couleur, mais surtout pas une liste de messages. (Dans le modèle LOCAL, on aurait par contre le droit de le faire.) La troisième phase devra donc être composée de plusieurs rondes (autant de rondes que la taille de l'ensemble à transmettre). Vous pourrez détecter la fin de transmission de l'ensemble complet avec un message de fin spécial ou en communiquant d'abord la longueur de la liste.
  • N'ouliez pas que l'on programme des algorithmes distribués, et donc que pour lire une information détenue d'un voisin v un sommet u doit recevoir un message émis par v. Par exemple, le sommet u n'a pas le droit d'accéder à son voisin v via getNeighbors(), puis d'accéder à v.getID(). Dit autrement, la méthode getNeighbors() est interdite. Pour calculer son degré, un sommet u devra recevoir des messages de tous ces voisins et les compter.
  • Le simulateur, fonctionne par évènements. Pour le modèle LOCAL ou CONGEST, ce sont les évènements onStart() et onClock() qui nous intéressent. Il ne faut pas en utiliser d'autres, notamment OnMessage() qui permet de gérer les algorithmes asynchrones, ce qui n'est pas le cas des modèles LOCAL et CONGEST.
  • Avec le simulateur, l'algorithme ne s'arrête pas tout seul. Cela vient du fait que l'horloge synchrone, et donc l'évènement onClock(), est éternellement appelé. Il convient donc dans cette méthode de prévoir une variable, disons status, permettant d'indiquer de ne plus rien faire lorsque le sommet a terminer l'algorithme. Cette variable peut également servir à gérer les différentes phases de l'algorithme.
  • Pour visualiser les différentes phases et le débuggage, pensez à modifier la couleur des sommets. Il est aussi possible de faire des sorties sur la console avec System.out.println(), mais tous les sommets le feront. Pensez alors à afficher leur ID et le numéro de ronde pour distinguer les sorties. Bien sûr un if (getID() == 18 && getTime() == 2) System.out.println("...") est une autre solution possible. L'ID des sommets est disponible en survolant le sommet avec la souris.
  • La convention d'une ronde JBotSim est différente de celle utilisée dans le cours. Les messages récupérés/reçus lors d'un évènement onClock() sont ceux qui ont été envoyés à la ronde précédente. Ainsi, une ronde standard consiste d'abord par lire les messages émis à la ronde précédente (voir ci-dessous l'aide), de les traiter, et de terminer par les envois de messages (pour la ronde suivante). Il convient aussi d'envoyer le premier message dans onStart() qui est appelé une seule fois au démarrage de l'algorithme sans quoi rien ne se passera.

    Pour le dire autrement, si $S_i$, $R_i$ et $C_i$ représentent les opérations d'envoi ($S_i$), de réception ($R_i$) et de calcul ($C_i$) pour la ronde $i$ de l'algorithme distribué $A$, le cours va représenter la sucession des rondes de $A$ selon le découpage: $S_1/R_1/C_1$ - $S_2/R_2/C_2$ - $S_3/R_3/C_3$ - ... alors qu'en JBotSim, c'est plutôt: $S_1$ dans onStart(), puis le découpage $R_1/C_1/S_2$ - $R_2/C_2/S_3$ - $R_3/C_3/S_4$ - ... à chaque évènement onClock(). Notez bien que c'est la même chose puisque dans les deux cas les opérations seront effectuées dans l'ordre: $S_1/R_1/C_1/S_2/R_2/C_2/S_3/R_3/C_3/...$

    • Votre class Main devrait ressembler à ceci: 

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

public class Main {

    public static void main(String[] args) {

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

        DetectC34.n = T.getNodes().size(); // calcule n pour tous les sommets

        JTopology J = new JTopology(T);
        new JViewer(J);  // dessine la topologie
        T.start();       // démarre l'algorithme
        T.pause();       // mode pas-à-pas (clic-droit dans l'interface)
    }
}

    Votre class DetectC34 devrait ressembler à ceci: 

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

public class DetectC34 extends Node {

    public static int n; // constante commune à tous les sommets

    @Override // au départ
    public void onStart() {
        ;;;
        // ne pas oublier d'envoyer un premier message
    }

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

}

    Aide rapide sur JBotSim: 

    // colorie le sommet courant
setColor(Color.getColorAt(getID())); // colorie selon l'ID
setColor(Color.red);  // colorie en rouge
setColor(Color.bleu); // colorie en bleu

// envoie un message
send(Node, Message);

// envoie son ID à tous ses voisins
int x = getID();
sendAll(new Message(x));

// lecture des messages dans onClock()
for (Message m : getMailbox()) { // pour chaque msg émis à la ronde précédente
  y = (int) m.getContent();      // le contenu du msg m
  Node v = m.getSender();        // l'émetteur du msg m
  ;;;
  }

// donne le numéro courant de la ronde
getTime(); // = 0,1,2,...

// liste des voisins (ne devrait pas être utilisée)
getNeighbors();
getNeighbors()[0]; // 1er voisin de la liste