Si la mise à jour de la couleur d'un point ne dépend que de la couleur de ses voisins « surplombants », de densité supérieure, alors à paysage de densité donné et à graphe de voisinage donné on n'obtiendra qu'un seul coloriage : l'attribution des classes sera lui aussi indépendant de l'ordre des données. On peut rapprocher notre problème de plusieurs autres traités dans le domaine des algorithmes basés sur les graphes, comme les automates cellulaires, bien connus (l'état d'un nœud à l'instant t dépend de l'état de ses voisins à t-1), ou les graphes évoluants (les liens d'un nœud à l'instant t dépendent des liens de ses voisins à t-1), ces derniers utilisés dans le domaine de la robotique reconfigurable. Mais notre problème d'« automate de graphes » sur graphe évolutif ne semble pas avoir été abordé, à notre connaissance. 

## 3.3. Algorithme Incrémental Germen : Modifications **Locales** Des Voisinages, Des Densités Et Des Noyaux De Classes.

On construit progressivement et en la mettant constamment à jour une structure de donnée comportant pour chaque noeud la liste de ses voisins, sa densité, et son (ou ses) numéros de chef(s) de classe. A chaque arrivée d'un vecteur (nœud) nouveau, on calcule les changements de densité induits dans son 2-voisinage (il ne peut pas y en avoir ailleurs du fait de notre définition de la densité), puis les changements de chef(s) de classe induits. Pour ce faire, on met à jour et on parcourt itérativement la liste des nœuds susceptibles de changer de classe, compte tenu de la règle choisie pour l'extension des classes. Au pire cette liste peut comporter tous les documents antérieurs, mais elle ne peut que se vider (en pratique elle se stabilise autour de deux ou trois centaines d'éléments en moyenne quand le nombre d'éléments à classer dépasse un millier). 

_____ . Initialisation : le premier noeud de la séquence n'a aucun lien, a une densité nulle et son propre numéro comme chef de classe. 

LCC = Ø // LCC est la liste des listes de chef(s) de classe pour chaque nœud // 
. POUR chaque nouveau nœud : // changements de densité induits : // 
.calcul de ses 1- et 2-voisinages entrants et sortants, et des modifications de voisinages occasionnée par son arrivée ; d'où la liste LL des noeuds touchés par une création / suppr. /modif. de lien. .calcul de sa densité à partir de son 1-voisinage. 

.POUR tout noeud de LL, et tout noeud de son 1-voisinage : 
- nouveau calcul de sa densité fin POUR // changements de chef(s) de classe induits : // L = LL 
TANT QUE la liste L des noeuds susceptibles de changer d'état est non-vide : 
liste LS = Ø POUR chaque noeud de L trié par densité décroissante : 
~ appliquer la règle de changement de classe en fonction des classes des voisins entrants surplombants (données par LCC) et de leurs densités. ~ si changement : 
.mettre à jour LCC pour le nœud courant 
.déterminer les surplombés éventuels (dont le noeud courant est surplombant) ; .incrémenter la liste LS des surplombés. 

fin POUR 
L=LS 
fin TANT QUE 
Exemples de règles : 