algod
Class SommetArbreCouvrant

java.lang.Object
  |
  +--java.lang.Thread
        |
        +--algod.SommetAbstract
              |
              +--algod.SommetIO
                    |
                    +--algod.SommetElection
                          |
                          +--algod.SommetArbreCouvrant
All Implemented Interfaces:
java.lang.Runnable
Direct Known Subclasses:
SommetNumProfondeur

class SommetArbreCouvrant
extends SommetElection

Implémente un arbre couvrant de la composante connexe d'un sommet.

Version:
1.0
Author:
Alexandre Alapetite, Brice Andujar, Gregory Gontier

Field Summary
protected  AlgoDMessageFIFO algoDMessageFIFO
          File d'attente des messages provenant d'autres sommets.
private static int CVR_PARENT_UNKNOWN
          Valeur indiquant que le sommet ne connait pas encore son père.
private static int CVR_RACINE
          Valeur indiquant que le sommet est racine de l'arbre couvrant.
private  java.util.Vector enfants
          Tableau des enfants SommetInterface de ce sommet pour un arbre couvrant.
(package private)  int identElu
          Identifiant du sommet élu. -1 si pas encore élu.
protected  int identifiant
          Identifiant unique de ce sommet.
(package private) static int nbMessagesArbreCouvrant
           
(package private) static int nbMessagesElection
           
private  int nbReponsesEnfantsRestantes
          Nombre de réponses d'enfants potentiels restantes.
private  int nbReponsesFiniRestantes
          Nombre de réponses restantes indiquant que l'algo d'arbre couvrant est terminé.
(package private)  int numVoisinParent
          Numéro du voisin qui fait parent.
protected  int poids
          Poids de ce noeud de l'arbre recouvrant, c'est-à-dire le nombre de sommets enfants et petit-enfants, etc...
(package private)  IntVector poidsEnfants
          Tableau stoquant les poids des différents enfants.
(package private) static int rndDelaiTransmission
           
(package private)  IntVector route
          Tableau indiquant, pour les sommets supposés du graphe, le voisin qui relaie la communication.
static boolean verbose
          Indique si un texte doit apparaître lors de certaines actions comme l'envoit de messages.
 
Fields inherited from class java.lang.Thread
MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY
 
Constructor Summary
SommetArbreCouvrant(int identifiant)
           
 
Method Summary
(package private)  void acteCandidature()
          Démarre un acte de candidature.
(package private)  void affiche(java.lang.String texte)
          Affiche du texte sur la sortie standard.
(package private)  void afficheErreur(java.lang.String texte)
          Affiche du texte sur la sortie standard.
private  void ajoutEnfant(SommetVoisin unSommet)
          Ajoute un enfant à ce sommet.
protected  int ajoutVoisin(AlgoDMessageFIFO aAlgoDMessageFIFO, int aIdentifiant)
          Ajoute un voisin à ce sommet.
protected  int ajoutVoisin(SommetVoisin unSommet)
          Ajoute un voisin à ce sommet.
(package private)  void attend(long millis)
          Attend un certain nombre de millisecondes.
 void demarreArbreCouvrant()
          A appeler pour démarrer l'algorithme distribué d'arbre couvrant à partir de ce sommet.
protected  void demarreElection()
           
 void destroy()
          Arrête le thread et nettoie ses structures et moyens de communication.
 void envoyerAEnfant(char typeMessage, java.lang.String contenu, int identSommetSource, int numEnfant)
          Envoie un message à un enfant.
 void envoyerAPere(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message au père de ce sommet dans l'arbre couvrant.
(package private)  void envoyerASommet(char typeMessage, java.lang.String contenu, int identSommetSource, SommetVoisin sommetVoisin)
           
(package private)  void envoyerASommet(char typeMessage, java.lang.String contenu, int identSommetSource, SommetVoisin sommetVoisin, int identSommetDestination)
           
protected  void envoyerATousVoisins(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message à tous les voisins.
protected  void envoyerATousVoisinsSauf(char typeMessage, java.lang.String contenu, int identSommetSource, int numVoisin)
          Envoie un message à tous les voisins sauf un.
 void envoyerAuxEnfants(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message aux enfants de ce sommet dans l'arbre couvrant.
protected  void envoyerAVoisin(char typeMessage, java.lang.String contenu, int identSommetSource, int numVoisin)
           
protected  void envoyerAVoisin(char typeMessage, java.lang.String contenu, int identSommetSource, int numVoisin, int identSommetDestination)
          Envoie un message de type typeMessage, provenant du sommet identSommetSource que l'on achemine par le voisin numVoisin pour le sommet identSommetDestination.
protected  void finArbreCouvrant()
          Méthode invoquée lorsque l'algorithme d'arbre couvrant est terminé.
protected  void finElection()
          Termine la méthode héritée de fin d'élection pour démarrer l'arbre couvrant.
 SommetVoisin getEnfant(int ident)
           
 SommetVoisin getEnfantAt(int num)
           
 int getIdentifiant()
          Accès à l'identifiant de ce sommet.
 SommetVoisin getPere()
          Accés au père de ce sommet.
 SommetVoisin getVoisin(int ident)
           
 SommetVoisin getVoisinAt(int num)
           
 int indexOfEnfant(int ident)
           
protected  void initialisationElection(int nbSomm)
           
 boolean isElu()
          Retourne si ce sommet est l'élu de son groupe.
 boolean isFeuille()
          Indique si ce sommet est une feuille de l'arbre couvrant.
 boolean isFilsDe(int idPere)
          Indique si ce sommet est un fils du sommet de cet identifiant.
 boolean isFini()
          Indique que le sommet n'a plus de message à traiter dans la file d'attente.
 boolean isRacine()
          Indique si ce sommet est la racine de l'arbre couvrant.
 boolean isVoisin(int ident)
          Teste si un sommet est voisin de celui-ci.
 int nbEnfants()
           
 int nbVoisins()
           
 int numOfVoisin(int ident)
           
private  void receptionArbreFini(int numEnfant, int SousPoids)
          Réception par un enfant que les sous-arbre de cet enfant est terminé.
private  void receptionEnfantNON()
          Reception d'un enfant pas d'accord.
private  void receptionEnfantOUI(int numVoisin)
          Reception d'un enfant d'accord.
private  void receptionParent(int numVoisin)
          Reception d'une candidature de père.
 void recevoir(AlgoDMessage adm)
          Ajoute un message provenant d'un autre sommet à la file des messages.
(package private)  void sonnerie()
          Fait un beep
 java.lang.String toString()
          Informations sur ce sommet.
protected  void traiteReception(AlgoDMessage adm, int numVoisin)
          Appelle les méthodes appropriées en fonction du message à traiter aprés un parsage éventuel.
 
Methods inherited from class java.lang.Thread
activeCount, checkAccess, countStackFrames, currentThread, dumpStack, enumerate, getContextClassLoader, getName, getPriority, getThreadGroup, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, resume, run, setContextClassLoader, setDaemon, setName, setPriority, sleep, sleep, start, stop, stop, suspend, yield
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

nbMessagesArbreCouvrant

static int nbMessagesArbreCouvrant

CVR_RACINE

private static final int CVR_RACINE
Valeur indiquant que le sommet est racine de l'arbre couvrant.

See Also:
numVoisinParent, Constant Field Values

CVR_PARENT_UNKNOWN

private static final int CVR_PARENT_UNKNOWN
Valeur indiquant que le sommet ne connait pas encore son père.

See Also:
numVoisinParent, Constant Field Values

enfants

private java.util.Vector enfants
Tableau des enfants SommetInterface de ce sommet pour un arbre couvrant.

See Also:
SommetAbstract.voisins, SommetVoisin

numVoisinParent

int numVoisinParent
Numéro du voisin qui fait parent.


poids

protected int poids
Poids de ce noeud de l'arbre recouvrant, c'est-à-dire le nombre de sommets enfants et petit-enfants, etc...


poidsEnfants

IntVector poidsEnfants
Tableau stoquant les poids des différents enfants. Utilisé pour renuméroter les sommets.


nbReponsesEnfantsRestantes

private int nbReponsesEnfantsRestantes
Nombre de réponses d'enfants potentiels restantes.


nbReponsesFiniRestantes

private int nbReponsesFiniRestantes
Nombre de réponses restantes indiquant que l'algo d'arbre couvrant est terminé.


nbMessagesElection

static int nbMessagesElection

route

IntVector route
Tableau indiquant, pour les sommets supposés du graphe, le voisin qui relaie la communication.


identElu

int identElu
Identifiant du sommet élu. -1 si pas encore élu.

See Also:
SommetElection.maxIdent, SommetElection.maxNbVoisins

rndDelaiTransmission

static int rndDelaiTransmission

algoDMessageFIFO

protected AlgoDMessageFIFO algoDMessageFIFO
File d'attente des messages provenant d'autres sommets.


verbose

public static boolean verbose
Indique si un texte doit apparaître lors de certaines actions comme l'envoit de messages.


identifiant

protected final int identifiant
Identifiant unique de ce sommet.

Constructor Detail

SommetArbreCouvrant

public SommetArbreCouvrant(int identifiant)
Method Detail

destroy

public void destroy()
Description copied from class: SommetAbstract
Arrête le thread et nettoie ses structures et moyens de communication.
Attention, les autres threads ne sont pas prévenus de sa destruction.

Overrides:
destroy in class SommetElection

isRacine

public final boolean isRacine()
Indique si ce sommet est la racine de l'arbre couvrant.


isFeuille

public final boolean isFeuille()
Indique si ce sommet est une feuille de l'arbre couvrant.


isFilsDe

public final boolean isFilsDe(int idPere)
Indique si ce sommet est un fils du sommet de cet identifiant.


nbEnfants

public final int nbEnfants()
Returns:
le nombre d'enfants de ce sommet dans l'arbre couvrant.

getEnfantAt

public final SommetVoisin getEnfantAt(int num)
Parameters:
num - le numéro de l'enfant auquel on veut avoir accés.
Returns:
le num-ième enfant.

getPere

public final SommetVoisin getPere()
Accés au père de ce sommet.


getEnfant

public final SommetVoisin getEnfant(int ident)
Parameters:
ident - l'identifiant du sommet enfant auquel on veut avoir accés.
Returns:
l'enfant de l'identifiant ident, null sinon.

indexOfEnfant

public int indexOfEnfant(int ident)
Parameters:
ident - l'identifiant du sommet enfant auquel on veut avoir accés.
Returns:
le numéro d'enfant de ce sommet voisin, -1 s'il n'est pas enfant.

ajoutEnfant

private void ajoutEnfant(SommetVoisin unSommet)
Ajoute un enfant à ce sommet.


demarreArbreCouvrant

public void demarreArbreCouvrant()
A appeler pour démarrer l'algorithme distribué d'arbre couvrant à partir de ce sommet.
Ce sommet sera racine.


finArbreCouvrant

protected void finArbreCouvrant()
Méthode invoquée lorsque l'algorithme d'arbre couvrant est terminé.
Ce sommet est racine.


finElection

protected final void finElection()
Termine la méthode héritée de fin d'élection pour démarrer l'arbre couvrant.

Overrides:
finElection in class SommetElection

envoyerAPere

public void envoyerAPere(char typeMessage,
                         java.lang.String contenu,
                         int identSommetSource)
Envoie un message au père de ce sommet dans l'arbre couvrant.


envoyerAuxEnfants

public void envoyerAuxEnfants(char typeMessage,
                              java.lang.String contenu,
                              int identSommetSource)
Envoie un message aux enfants de ce sommet dans l'arbre couvrant.


envoyerAEnfant

public void envoyerAEnfant(char typeMessage,
                           java.lang.String contenu,
                           int identSommetSource,
                           int numEnfant)
Envoie un message à un enfant.

Parameters:
numEnfant - le n° de l'enfant voisin à qui ce message est destiné.

traiteReception

protected void traiteReception(AlgoDMessage adm,
                               int numVoisin)
Description copied from class: SommetIO
Appelle les méthodes appropriées en fonction du message à traiter aprés un parsage éventuel.

Overrides:
traiteReception in class SommetElection

receptionParent

private void receptionParent(int numVoisin)
Reception d'une candidature de père.


receptionEnfantOUI

private void receptionEnfantOUI(int numVoisin)
Reception d'un enfant d'accord.


receptionEnfantNON

private void receptionEnfantNON()
Reception d'un enfant pas d'accord.


receptionArbreFini

private void receptionArbreFini(int numEnfant,
                                int SousPoids)
Réception par un enfant que les sous-arbre de cet enfant est terminé.


toString

public java.lang.String toString()
Description copied from class: SommetAbstract
Informations sur ce sommet.

Overrides:
toString in class SommetElection
Returns:
un texte sur une ligne décrivant de sommet.

initialisationElection

protected void initialisationElection(int nbSomm)

ajoutVoisin

protected int ajoutVoisin(SommetVoisin unSommet)
Description copied from class: SommetAbstract
Ajoute un voisin à ce sommet.
Ne met pas à jour les algorithmes déjà effectués.

Overrides:
ajoutVoisin in class SommetAbstract

isElu

public final boolean isElu()
Retourne si ce sommet est l'élu de son groupe.


demarreElection

protected void demarreElection()

acteCandidature

final void acteCandidature()
Démarre un acte de candidature.


envoyerASommet

final void envoyerASommet(char typeMessage,
                          java.lang.String contenu,
                          int identSommetSource,
                          SommetVoisin sommetVoisin,
                          int identSommetDestination)

envoyerASommet

final void envoyerASommet(char typeMessage,
                          java.lang.String contenu,
                          int identSommetSource,
                          SommetVoisin sommetVoisin)

envoyerAVoisin

protected final void envoyerAVoisin(char typeMessage,
                                    java.lang.String contenu,
                                    int identSommetSource,
                                    int numVoisin,
                                    int identSommetDestination)
Envoie un message de type typeMessage, provenant du sommet identSommetSource que l'on achemine par le voisin numVoisin pour le sommet identSommetDestination.


envoyerAVoisin

protected final void envoyerAVoisin(char typeMessage,
                                    java.lang.String contenu,
                                    int identSommetSource,
                                    int numVoisin)

envoyerATousVoisins

protected final void envoyerATousVoisins(char typeMessage,
                                         java.lang.String contenu,
                                         int identSommetSource)
Envoie un message à tous les voisins.


envoyerATousVoisinsSauf

protected final void envoyerATousVoisinsSauf(char typeMessage,
                                             java.lang.String contenu,
                                             int identSommetSource,
                                             int numVoisin)
Envoie un message à tous les voisins sauf un.

Parameters:
numVoisin - le numéro du voisin à ignorer (pas son identifiant).

isFini

public final boolean isFini()
Indique que le sommet n'a plus de message à traiter dans la file d'attente.


recevoir

public final void recevoir(AlgoDMessage adm)
Ajoute un message provenant d'un autre sommet à la file des messages.
La file FIFO est déjà synchronized.

See Also:
SommetIO.algoDMessageFIFO

getIdentifiant

public final int getIdentifiant()
Accès à l'identifiant de ce sommet.


isVoisin

public final boolean isVoisin(int ident)
Teste si un sommet est voisin de celui-ci.

Parameters:
ident - identifiant du sommet potentiellement voisin de celui-ci.
Returns:
si le sommet de cet identifiant est voisin de ce sommet.

getVoisinAt

public final SommetVoisin getVoisinAt(int num)
Parameters:
num - le numéro du voisin auquel on veut avoir accés.
Returns:
le num-ième voisin.

getVoisin

public final SommetVoisin getVoisin(int ident)
Parameters:
ident - l'identifiant du voisin auquel on veut avoir accés.
Returns:
le voisin de l'identifiant ident, null sinon.

numOfVoisin

public final int numOfVoisin(int ident)
Parameters:
ident - l'identifiant d'un sommet voisin de ce sommet.
Returns:
le numéro du voisin de cet identifiant, -1 s'il n'y a pas de voisin avec cet identifiant.

nbVoisins

public final int nbVoisins()
Returns:
le nombre de sommets voisins de celui-ci.

ajoutVoisin

protected final int ajoutVoisin(AlgoDMessageFIFO aAlgoDMessageFIFO,
                                int aIdentifiant)
Ajoute un voisin à ce sommet.
Ne met pas à jour les algorithmes déjà effectués.


affiche

void affiche(java.lang.String texte)
Affiche du texte sur la sortie standard.


afficheErreur

void afficheErreur(java.lang.String texte)
Affiche du texte sur la sortie standard.


sonnerie

void sonnerie()
Fait un beep


attend

final void attend(long millis)
Attend un certain nombre de millisecondes.