Construction distribuée d'un arbre couvrant

Principe général

Étant donné un réseau et un noeud racine sélectionné, il est très facile de construire un arbre couvrant de manière distribuée. Le noeud de départ envoie un message à tous ses voisins. Puis l'algorithme est comme suit : si un noeud qui n'est pas encore dans l'arbre reçoit un message, il choisit l'émetteur de ce message comme parent, puis envoie à son tour un message à ses voisins. Cette propagation va ainsi définir un arbre qui couvre tous les noeuds du réseau (illustration ci-dessous).

wireless network  →  spanning tree

Construction d'un arbre couvrant dans un réseau.

Travail à effectuer :

Copier l'algorithme de broadcast vu précédemment dans une nouvelle classe TreeNodeV1. Pour chaque question, nous vous conseillons de créer une nouvelle version de votre fichier.

  1. Adapter le code pour construire un arbre couvrant, tel que lorsqu'un noeud est informé par un noeud voisin, il choisit ce voisin comme parent. On pourra utiliser un champ parent de type Node pour mémoriser le noeud parent.
    Visualisation: Une fois le noeud parent connu, vous pouvez utiliser la méthode getCommonLinkWith() pour obtenir le lien qui vous relie à lui, et la méthode setWidth() sur ce dernier pour mettre l'arête en gras.
  2. Faites maintenant en sorte que les noeuds apprennent la liste de leurs enfants dans l'arbre. Vous pouvez utiliser un champ children de type ArrayList. Vous pouvez utiliser des messages de différents types en utilisant des flags (voir un exemple d'utilisation dans l'exercice 3 de la feuille de td). Il est aussi possible d'envoyer un message à un seul noeud voisin plutôt qu'à tous en utilisant la bonne méthode.
  3. Faites maintenant en sorte que les noeuds détectent le fait qu'ils n'auront pas d'enfants dans l'arbre. Vous pouvez utiliser getTime() pour connaître le numéro de ronde actuelle. Vous pouvez surcharger onClock() pour exécuter un code spécifique à chaque ronde (la méthode sera appelée juste après la réception des messages envoyés à la ronde précédente).
  4. Faites en sorte que la racine détecte lorsque la construction de l'arbre est terminée.
  5. Faites en sorte que la racine apprenne le nombre de noeuds total dans le réseau. Notez que le contenu des messages peut être n'importe quel type d'objet.
  6. (Bonus) La racine doit informer chaque noeud du nombre de noeuds total.