Le graphe en tant que type abstrait

Dans cette section, nous allons examiner deux façons de considérer un graphe comme un type abstrait. Différents types abstraits induisent différents algorithmes. Chacun des deux types abstraits correspond en fait à une définition de graphe du chapitre 4.

D'habitude, les algorithmes qui manipulent des graphes permettent aussi de les modifier (rajouter ou supprimer un sommet ou une arête). Dans ce livre, dans le but de simplifier les algorithmes, nous n'autorisons pas ce genre de modifications.

Le premier type abstrait que nous allons considérer met en avant les arêtes. Pour cette raison, nous allons l'appeler le type abstrait centré-arêtes. Il contient les opérations suivantes :

• à partir d'un graphe $G$, récupérer le nombre de ses sommets (on suppose les sommets numérotés $0, 1, \ldots, \vert V(G)\vert -1$),
• à partir d'un graphe $G$, récupérer le nombre de ses arêtes (on suppose les arêtes numérotées $0, 1, \ldots, \vert E(G)\vert -1$),
• à partir d'un graphe $G$ et d'un entier $i$, $0 \le i < \vert V(G)\vert$, récupérer le sommet numéro $i$ du graphe,
• à partir d'un graphe $G$ et d'un entier $i$, $0 \le i < \vert E(G)\vert$, récupérer l'arête numéro $i$ du graphe,
• à partir d'une arête d'un graphe et d'un entier $i \in \{0, 1\}$ , récupérer la première ou la deuxième extrémité de l'arête.
• marquer un sommet,
• démarquer un sommet,
• déterminer si un sommet est marqué,
• marquer une arête,
• démarquer une arête,
• déterminer si une arête est marquée.

Les quatre premières opérations sont nécessaires pour qu'on puisse énumérer tous les sommets et toutes les arêtes. La cinquième opération correspond à la fonction $\phi$ de la définition 4.1. Les autres opérations existent pour qu'il soit possible de parcourir les sommets et les arêtes du graphe et pour pouvoir déterminer si un sommet (ou une arête) a déjà été parcouru.

Les opérations du type centré-arêtes seront notées de la manière suivante (la tradition est d'utiliser l'anglais) :

NB_NODES(G)
NB_EDGES(G)
NODE(G, i)
EDGE(G, i)
EDGE_END(e, i)
MARK_NODE(s)

UNMARK_NODE(s)
NODE_MARKED(s)
MARK_EDGE(e)
UNMARK_EDGE(e)
EDGE_MARKED(e)

Le deuxième type abstrait que nous allons considérer est similaire au premier. Mais cette fois-ci, ce sont les sommets qui sont au centre du type. En conséquence, nous allons l'appeler le type abstrait centré-sommets. En voici les opérations :

• à partir d'un graphe $G$, récupérer le nombre de sommets (on suppose que les sommets sont numérotés $0$, $1, \ldots, \vert V(G)\vert -1$),
• à partir d'un graphe et un entier $i$, $0 \le i < \vert V(G)\vert$, récupérer le sommet numéro $i$ du graphe,
• à partir d'un sommet $s$, récupérer le nombre d'arêtes ayant $s$ comme l'une de ses extrémités,
• à partir d'un sommet $s$ et d'un entier $i$, récupérer l'arête numéro $i$ ayant $s$ comme l'une de ses extrémités,
• à partir d'un sommet et d'une arête incidente à ce sommet, récupérer le sommet à l'autre extrémité de l'arête,
• marquer un sommet,
• démarquer un sommet,
• déterminer si un sommet est marqué,
• marquer une arête,
• démarquer une arête,
• déterminer si une arête est marquée.

Les opérations du type centré-sommets seront notées de la manière suivante :

NB_NODES(G)
NODE(G, i)
NB_EDGES(s)
EDGE(s, i)
FOLLOW_EDGE(s, e)
MARK_NODE(s)

UNMARK_NODE(s)
NODE_MARKED(s)
MARK_EDGE(e)
UNMARK_EDGE(e)
EDGE_MARKED(e)