Gamma

Représentation d'un graphe par son application Gamma

Étudions, à partir de quelques exemples, la structure de données graphe (définie dans le fichier graphes.h). La figure 1 montre un graphe simple, ainsi qu'une représentation en mémoire de ce graphe sous forme d'application ``successeurs'' (notée gamma ou Γ ). Tous les champs de la structure graphe ne sont pas encore utilisés, seuls les champs utiles ici sont illustrés.


(a)	(b)

Figure 1: (a): un graphe simple; (b): une représentation en mémoire de ce graphe sous forme d'application Γ.

Notez qu'il est prévu de réserver pour les arcs du graphe plus de place que nécessaire (narc), ce qui permet de modifier un graphe en lui retirant ou en lui rajoutant des arcs (dans la limite de nmaxarc). Dans cet exemple, il reste de la place pour stocker deux arcs supplémentaires.

Les cellules de liste (de type cell) sont allouées en une seule fois à l'initialisation de la structure et stockées dans le tableau reserve, pour éviter des appels répétés (et coûteux) à la fonction système malloc ou new.