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. Le graphe croix-n25
est un bon example. 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
d'identifiants ou de couleurs. (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.
Donc 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é (en fait
jusqu'à ce que la fenêtre soit fermée). 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 les
survolant 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 sous JBotSim
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,... (=0 au 1er appel de OnClock())
// liste des voisins (ne devrait pas être utilisée)
getNeighbors();
getNeighbors()[0]; // 1er voisin de la liste