L'objectif est de calculer un ensemble dominant pour un graphe $G$ avec un algorithme distribué dans le modèle LOCAL. Un ensemble dominant pour $G$ est un sous-ensemble de sommets $S$ de $G$ ayant la propriété que tout sommet est soit dans $S$ soit voisin d'un sommet de $S$. Généralement, on cherche à calculer un ensemble dominant avec le plus petit nombre possible de sommets, et on note $\gamma(G)$ ce minimum. Si $G$ est une étoile (un arbre de profondeur 1), alors $\gamma(G) = 1$. Si $G$ est un chemin à $n$ sommets, $\gamma(G) = \lceil{n/3}\rceil$. Malheureusement, c'est un problème très difficile à résoudre (NP-difficile), et on se contente d'algorithme d'approximation.
L'objectif ici va être d'implémenter deux algorithmes distribués: un pour les arbres (TREE) et un pour des graphes les graphes planaires-extérieurs (OUTER). Les graphes planaires-extérieurs (outer-planar en Anglais) sont tous les graphes qu'il est possible de dessiner sur le plan sans avoir de croisement d'arête de sorte que tous les sommets sont situés sur le bord de la face extérieure. Les arbres sont des cas particuliers de graphes planaires-extérieurs puisqu'on peut faire le tour de l'arbre et visiter tous ces sommets en suivant le bord de la face extérieure. Une grille $2\times k$ est aussi planaires-extérieurs, mais pas une grille $3\times k$ avec $k\ge 3$.
Ces deux algorithmes sont particulièrement simples à énoncer. Malheureusement, ils ne sont pas formellement énoncés comme un algorithme distribués ... Il va falloir réfléchir un peu pour l'implémentation !
Ces deux algorithmes s'appliquent sur n'importe quel graphe. Mais, ils ont cependant la propriété suivante: (1) si $G$ est un arbre, alors TREE produira une 3-approximation, c'est-à-dire un ensemble dominant $S$ tel que $|S| \le 3 \cdot \gamma(G)$; et (2) si $G$ est planaire-extérieur, alors OUTER produira une 5-approximation. On peut montrer que les facteurs $3$ et $5$ sont les meilleurs possibles pour tout algorithme distribué LOCAL utilisant un nombre constant de rondes pour les arbres et les planaires-extérieurs.
Vous devez créer un projet avec une class Main et une class DomSet 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 DomSet que vous allez devoir éditer. À la fin de l'algorithme, il faudra visualiser, en coloriant différemment les sommets (=rouge), ceux qui appartiennent à l'ensemble dominant $S$ sélectionné par l'algorithme.
Comme vous avez plusieurs algorithmes à programmer (deux), il vous est suggéré de changer la variable globale version dans Main() et de faire un switch(version){ case 1: ...; case 2: ...; } dans les méthodes de class DomSet de façon à pouvoir facilement tester vos algorithmes.
Tester vos algorithmes sur les fichiers de graphes disponibles sur la page du cours. En particulier, il y des exemples d'arbres (grille-1x7, grille-1x23, tree1, tree2) et de graphes planaires-extérieurs (grille-2x7, outer1, outer2). Vous pourrez par exemple constater que l'agorithme TREE sélectionne presque tous les sommets d'un chemin à $n$ sommets, alors que le minimum dans ce cas est $\lceil{n/3}\rceil$ comme on l'a vu précédemment. Et pour le graphe outer2, vous pourrez constater que OUTER sélectionne presque tous les sommets, alors que dans ce cas le minimum est d'environ $n/5$.
Comme vous l'aurez peut-être constaté, l'algorithme TREE est correct seulement si toutes les composantes connexes de $G$ comportent plus de deux sommets. En particulier, les sommets isolés (ceux de degré 0) qui devraient être dans tout ensemble dominant, ne sont pas dans l'ensemble renvoyé par TREE. Comme extension, nous vous demandons de modifier votre algorithme de façon à ce qu'il fonctionne dans tous les cas, tout en préservant le facteur d'approximation, c'est-à-dire que sélectionner tous les sommets n'est pas la solution ! Améliorez OUTER en évitant, autant que possible, de sélectionner les sommets de degré 1.
IMPORTANT. À la fin de la séance (ou avant) vous devrez m'envoyer votre fichier DomSet.java par email à gavoille@labri.fr, en précisant vos noms si vous êtes en binôme. Il est important de ne surtout pas m'envoyer de fichier compressé ou une archive de votre projet. Le correcteur veut uniquement le .java !
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(800,600); // fenêtre de w x h pixels
T.setDefaultNodeModel(DomSet.class); // algo des sommets = DomSet
String s = T.getFileManager().read("..."); // lecture du fichier
T.getSerializer().importFromString(T,s); // construction du graphe
T.shuffleNodeIds(); // permutation aléatoire des IDs dans [0,n[
// version de l'algorithme:
// = 1 -> arbre
// = 2 -> planaire-extérieur
DomSet.version = 1;
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 DomSet devrait ressembler à ceci:
import io.jbotsim.core.Node;
public class DomSet extends Node {
public static int version; // version de l'algorithme
@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,...