La représentation la plus traditionnelle des graphes fait appel
à des
pointeurs (references en Caml), elle s'applique donc tout
naturellement
ici. Une image est soit Blanc, soit Noir, soit une liste de pointeurs vers
des images : ses fils. On y a ajouté une troisième
possibilité, Fantome (qui aurait pu s'appeler Provisoire),
pour les nuds
non-instanciés et dont on verra l'utilité plus loin.
type color = Blanc | Noir;;
type image = Fantome | Color of color | Node of (image ref)
list;;
Le triangle cité en exemple est alors :
let rec tr=Node [ref (Color Blanc); ref tr; ref (Color Noir); ref
tr];;
Ce type impose une bonne ma^trise de la différence entre
égalité physique (= =) et égalité structurelle (=)
avec les
références, si l'on ne veut pas aboutir à des comparaison
qui bouclent infiniment (tout du moins en Caml Light). Cela pose des
problèmes dès que l'on veut comparer deux nuds, en particulier, si l'on
veut savoir si un n
ud a déjà été
rencontré dans un algorithme, il faut impérativement utiliser
l'égalité physique sur l'objet, et non un test
d'égalité sur les références comme on le ferait avec
un langage classique.
Le gros défaut de ce type est que pour marquer les variables déjà rencontrées on crée une liste qu'on parcourt ensuite, ce qui qjoute un ordre de grandeur à la complexité des algorithme.