algod
Class SommetColorationAsynch1

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

public class SommetColorationAsynch1
extends SommetColoration

Coloration avec parallélisme (colorations secondaires).

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) static boolean backtrack_optimise
          Utilise la méthode de backtrack optimisée : remontée au plus petit voisin plus grand que soi.
(package private)  BooleanVector booleanVector
          Table des couleurs utilisées par les voisins plus forts.
(package private) static boolean colorationAsynch1
          Utilisation de la coloration parallèle secondaire.
private  boolean coloreParJeton
          Indique si le sommet a une couleur officielle.
(package private)  int couleur
          Couleur de ce sommet pour les problèmes de coloration.
protected  int couleurMax
          Couleur maximum pour ce sommet.
(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 nbBackTrack
          Compteur de back-tracks.
(package private) static int nbBackTrack_SJ
          Nombre de back-tracks secondaires.
(package private) static int nbMessagesArbreCouvrant
           
(package private) static int nbMessagesColoration
          Compteur de messages pour la coloration.
(package private) static int nbMessagesColoration_SJ
          Nombre de messages pour la coloration secondaire.
(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.
(package private)  boolean voisinsTrackConnus
          Indique si le routage pour le back-track a déjà été recherché.
 
Fields inherited from class java.lang.Thread
MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY
 
Constructor Summary
SommetColorationAsynch1(int couleurMax, 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.
(package private)  void chercheRoutesBackTrack()
          Recherche les routes pour le back-track.
private  void colorationRattee_SJ()
           
private  void colorationRattee()
          On ne peut pas se colorer, on back-traque.
 void demarreArbreCouvrant()
          A appeler pour démarrer l'algorithme distribué d'arbre couvrant à partir de ce sommet.
protected  void demarreColoration()
           
protected  void demarreElection()
           
 void demarreNumProfondeur()
           
 void destroy()
          Arrête le thread et nettoie ses structures et moyens de communication.
(package private)  void envoyerABackTrack(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message au sommet précédent dans le backtrack.
(package private)  void envoyerABackTrackFini(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message de fin de back-track réussi.
 void envoyerAEnfant(char typeMessage, java.lang.String contenu, int identSommetSource, int numEnfant)
          Envoie un message à un enfant.
(package private)  void envoyerAEnfantsPasTrack(char typeMessage, java.lang.String contenu, int identSommetSource)
           
 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.
(package private)  void envoyerATrack(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message au sommet suivant dans le backtrack.
 void envoyerAuxEnfants(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message aux enfants de ce sommet dans l'arbre couvrant.
 void envoyerAuxFaibles(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message aux voisins plus faibles.
 void envoyerAuxForts(char typeMessage, java.lang.String contenu, int identSommetSource)
          Envoie un message aux voisins plus forts.
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 finColoration(boolean ok)
          Méthode invoquée lorsque l'algorithme de coloration est terminé.
protected  void finElection()
          Termine la méthode héritée de fin d'élection pour démarrer l'arbre couvrant.
protected  void finNumProfondeur()
          Termine la méthode héritée de numérotation en profondeur pour démarrer la coloration.
 int getCouleur()
          Accès à la couleur de ce sommet.
(package private)  int getCouleurMaxPossible()
           
 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 isCouleurOfficielle()
           
 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 receptionColoration_SJ(int numVoisin, int colore)
           
private  void receptionColoration(int numVoisin, int colore)
          Un voisin nous transmet sa nouvelle couleur.
private  void receptionDemarre_SJ(int identSource, int colore, int identDest)
           
private  void receptionDemarre(int identSource, int identDest)
          Un voisin (normalement notre père dans l'arbre couvrant), nous transmet sa couleur et nous demande de nous colorer.
private  void receptionNON_SJ(int identSource, int identDest)
           
private  void receptionNON(int identSource, int identDest)
           
private  void receptionOK_SJ(int identSource)
           
private  void receptionOK(int identSource)
          Le back-track s'est terminé et il est réussi.
 void recevoir(AlgoDMessage adm)
          Ajoute un message provenant d'un autre sommet à la file des messages.
(package private)  void setCouleursVoisinsSupp()
          Désactive les couleurs utilisées parmis les voisins d'identifiant supérieur.
(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

colorationAsynch1

static boolean colorationAsynch1
Utilisation de la coloration parallèle secondaire.


nbBackTrack_SJ

static int nbBackTrack_SJ
Nombre de back-tracks secondaires.


nbMessagesColoration_SJ

static int nbMessagesColoration_SJ
Nombre de messages pour la coloration secondaire.


coloreParJeton

private boolean coloreParJeton
Indique si le sommet a une couleur officielle.


nbBackTrack

static int nbBackTrack
Compteur de back-tracks.


nbMessagesColoration

static int nbMessagesColoration
Compteur de messages pour la coloration.


backtrack_optimise

static boolean backtrack_optimise
Utilise la méthode de backtrack optimisée : remontée au plus petit voisin plus grand que soi.


couleur

int couleur
Couleur de ce sommet pour les problèmes de coloration.


couleurMax

protected final int couleurMax
Couleur maximum pour ce sommet.


booleanVector

BooleanVector booleanVector
Table des couleurs utilisées par les voisins plus forts.


voisinsTrackConnus

boolean voisinsTrackConnus
Indique si le routage pour le back-track a déjà été recherché.


nbMessagesNumProfondeur

static int nbMessagesNumProfondeur

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

SommetColorationAsynch1

public SommetColorationAsynch1(int couleurMax,
                               int identifiant)
Method Detail

isCouleurOfficielle

public final boolean isCouleurOfficielle()

demarreColoration

protected void demarreColoration()
Overrides:
demarreColoration in class SommetColoration

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 SommetColoration

receptionColoration

private void receptionColoration(int numVoisin,
                                 int colore)
Un voisin nous transmet sa nouvelle couleur.


receptionColoration_SJ

private void receptionColoration_SJ(int numVoisin,
                                    int colore)

receptionOK

private void receptionOK(int identSource)
Le back-track s'est terminé et il est réussi.


receptionOK_SJ

private void receptionOK_SJ(int identSource)

receptionNON

private void receptionNON(int identSource,
                          int identDest)

receptionNON_SJ

private void receptionNON_SJ(int identSource,
                             int identDest)

receptionDemarre

private void receptionDemarre(int identSource,
                              int identDest)
Un voisin (normalement notre père dans l'arbre couvrant), nous transmet sa couleur et nous demande de nous colorer.


receptionDemarre_SJ

private void receptionDemarre_SJ(int identSource,
                                 int colore,
                                 int identDest)

colorationRattee

private void colorationRattee()
On ne peut pas se colorer, on back-traque.


colorationRattee_SJ

private void colorationRattee_SJ()

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 SommetArbreCouvrant

getCouleur

public final int getCouleur()
Accès à la couleur de ce sommet.


envoyerAuxForts

public final void envoyerAuxForts(char typeMessage,
                                  java.lang.String contenu,
                                  int identSommetSource)
Envoie un message aux voisins plus forts.


envoyerAuxFaibles

public final void envoyerAuxFaibles(char typeMessage,
                                    java.lang.String contenu,
                                    int identSommetSource)
Envoie un message aux voisins plus faibles.


finColoration

protected void finColoration(boolean ok)
Méthode invoquée lorsque l'algorithme de coloration est terminé.
Ce sommet est de couleur couleurMax.

See Also:
SommetColoration.couleurMax

finNumProfondeur

protected final void finNumProfondeur()
Termine la méthode héritée de numérotation en profondeur pour démarrer la coloration.

Overrides:
finNumProfondeur in class SommetNumProfondeur

getCouleurMaxPossible

int getCouleurMaxPossible()

setCouleursVoisinsSupp

void setCouleursVoisinsSupp()
Désactive les couleurs utilisées parmis les voisins d'identifiant supérieur.


chercheRoutesBackTrack

void chercheRoutesBackTrack()
Recherche les routes pour le back-track.


envoyerABackTrack

final void envoyerABackTrack(char typeMessage,
                             java.lang.String contenu,
                             int identSommetSource)
Envoie un message au sommet précédent dans le backtrack.


envoyerAEnfantsPasTrack

final void envoyerAEnfantsPasTrack(char typeMessage,
                                   java.lang.String contenu,
                                   int identSommetSource)

envoyerATrack

final void envoyerATrack(char typeMessage,
                         java.lang.String contenu,
                         int identSommetSource)
Envoie un message au sommet suivant dans le backtrack.


envoyerABackTrackFini

final void envoyerABackTrackFini(char typeMessage,
                                 java.lang.String contenu,
                                 int identSommetSource)
Envoie un message de fin de back-track réussi.


toString

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

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

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()

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

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.