algod
Class SommetNumProfondeur

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

class SommetNumProfondeur
extends SommetArbreCouvrant

Ajoute la fonctionnalité de numérotation en profondeur inversée de l'arbre couvrant.

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

Field Summary
protected  AlgoDMessageFIFO algoDMessageFIFO
          File d'attente des messages provenant d'autres sommets.
(package private)  int identElu
          Identifiant du sommet élu. -1 si pas encore élu.
protected  int identifiant
          Identifiant unique de ce sommet.
private  int identifiantProfondeur
          Nouvel identifiant après l'arbre couvrant, qui correspond à une numérotation en profondeur inversée.
(package private) static int nbMessagesArbreCouvrant
           
(package private) static int nbMessagesElection
           
(package private) static int nbMessagesNumProfondeur
           
(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
SommetNumProfondeur(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.
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 demarreNumProfondeur()
           
 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()
          Termine la méthode héritée de fin d'arbre couvrant pour démarrer la numérotation en profondeur.
protected  void finElection()
          Termine la méthode héritée de fin d'élection pour démarrer l'arbre couvrant.
protected  void finNumProfondeur()
           
 SommetVoisin getEnfant(int ident)
           
 SommetVoisin getEnfantAt(int num)
           
 int getIdentifiant()
          Accès à l'identifiant de ce sommet.
 int getIdentifiantProfondeur()
          Accés au nouvel identifiant après l'arbre couvrant, qui correspond à une numérotation en profondeur inversée.
 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 receptionIdentifiantProfondeur(int numVoisin, int idPr)
          Récepetion par un voisin de son identifiant profondeur.
private  void receptionSetIdentifiantProfondeur(int idPr)
          Réception de notre identifiant profondeur par notre 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

nbMessagesNumProfondeur

static int nbMessagesNumProfondeur

identifiantProfondeur

private int identifiantProfondeur
Nouvel identifiant après l'arbre couvrant, qui correspond à une numérotation en profondeur inversée.


nbMessagesArbreCouvrant

static int nbMessagesArbreCouvrant

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.


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

SommetNumProfondeur

public SommetNumProfondeur(int identifiant)
Method Detail

getIdentifiantProfondeur

public final int getIdentifiantProfondeur()
Accés au nouvel identifiant après l'arbre couvrant, qui correspond à une numérotation en profondeur inversée.


demarreNumProfondeur

public void demarreNumProfondeur()

finNumProfondeur

protected void finNumProfondeur()

finArbreCouvrant

protected final void finArbreCouvrant()
Termine la méthode héritée de fin d'arbre couvrant pour démarrer la numérotation en profondeur.

Overrides:
finArbreCouvrant in class SommetArbreCouvrant

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 SommetArbreCouvrant

receptionIdentifiantProfondeur

private void receptionIdentifiantProfondeur(int numVoisin,
                                            int idPr)
Récepetion par un voisin de son identifiant profondeur.


receptionSetIdentifiantProfondeur

private void receptionSetIdentifiantProfondeur(int idPr)
Réception de notre identifiant profondeur par notre père.


toString

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

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

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.

demarreArbreCouvrant

public void demarreArbreCouvrant()
A appeler pour démarrer l'algorithme distribué d'arbre couvrant à partir de ce sommet.
Ce sommet sera 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é.

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.