Probleme – Du tableau rectangulaire au tableau de départs

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 13 — Le modèle des graphes

Énoncé

On veut une représentation par listes d'adjacence qui occupe véritablement $Θ (n + m)$ , sans allocation dynamique.

Décrire la représentation par tableau de départs : deux tableaux plats.
Écrire l'accès aux voisins, et le comparer à celui du tableau rectangulaire.
Construire cette représentation à partir d'une liste d'arcs, en $Θ (n + m)$ .
Vérifier, et dire ce qu'elle interdit.

Corrigé

1. La représentation. On concatène toutes les listes d'adjacence dans un unique tableau arrivee de taille $m$ , et l'on retient dans depart l'indice où commence la liste de chaque sommet.


int depart[N_MAX + 1];   /* la liste de u occupe arrivee[depart[u] .. depart[u+1]-1] */
int arrivee[A_MAX];      /* les m arcs, groupés par sommet d'origine */

L'invariant tient en trois points :

depart est croissant, $depart [0] = 0$ et $depart [n] = m$ ;
les successeurs de $u$ sont exactement $arrivee [depart [u]]$ à $arrivee [depart [u + 1] - 1]$ ;
d'où $d^{+} (u) = depart [u + 1] - depart [u]$ , lisible en $O (1)$ .

La case $depart [n]$ n'est pas un détail : c'est une sentinelle qui évite un cas particulier pour le dernier sommet.

2. L'accès.


/* Parcourir les voisins de u. Complexité : Theta(d+(u)). */
for (int k = depart[u]; k < depart[u+1]; k = k + 1) {
    int v = arrivee[k];
    /* ... */
}

Mesuré sur le graphe du chapitre : $depart = [0, 2, 3, 3, 4]$ et $arrivee = [1, 2, 3, 2]$ . On lit les voisins de $0$ aux indices $0$ et $1$ — soit $1$ et $2$ —, ceux de $1$ à l'indice $2$ — soit $3$ —, et le sommet $2$ n'en a aucun, puisque $depart [2] = depart [3] = 3$ . Vérifié : ce sont exactement les listes que donne le tableau rectangulaire.

	tableau rectangulaire	tableau de départs
mémoire	$Θ (n \cdot d_{m a x})$	$Θ (n + m)$
parcourir les voisins de $u$	$Θ (d^{+} (u))$	$Θ (d^{+} (u))$
lire $d^{+} (u)$	$O (1)$	$O (1)$
ajouter un arc	$O (1)$	impossible sans tout décaler

3. La construction en $Θ (n + m)$ . On la fait en trois passes, sans jamais trier : c'est un tri par comptage déguisé.


/* Construit depart/arrivee à partir de mm arcs donnés par src[] et dst[].
   Précondition : 0 <= src[k], dst[k] < n pour tout k ; mm <= A_MAX.
   Complexité : Theta(n + mm) en temps, O(n) en mémoire supplémentaire. */
void construire(int n, int mm, const int src[], const int dst[]) {
    /* (a) COMPTER : depart[u+1] recevra d+(u). */
    for (int u = 0; u <= n; u = u + 1) { depart[u] = 0; }
    for (int k = 0; k < mm; k = k + 1) { depart[src[k] + 1] += 1; }
    /* (b) SOMMES PARTIELLES : depart[u] devient l'indice de début de u. */
    for (int u = 0; u < n; u = u + 1) { depart[u+1] += depart[u]; }
    /* (c) PLACER : un curseur par sommet, initialisé à son début. */
    int curseur[N_MAX];
    for (int u = 0; u < n; u = u + 1) { curseur[u] = depart[u]; }
    for (int k = 0; k < mm; k = k + 1) {
        arrivee[curseur[src[k]]] = dst[k];
        curseur[src[k]] += 1;
    }
}

Le décalage d'un cran en (a) — écrire dans $depart [u + 1]$ et non dans $depart [u]$ — est l'astuce qui permet à la passe (b) de transformer les comptes en indices de début par une simple somme partielle, sans tableau auxiliaire. C'est le motif du tri par comptage, et il vaut d'être reconnu : compter, cumuler, placer.

Correction : après (b), $depart [u] = \sum_{w < u} d^{+} (w)$ , qui est bien l'indice où doit commencer la liste de $u$ . En (c), le curseur de $u$ parcourt exactement les $d^{+} (u)$ cases qui lui sont réservées, donc aucune écriture ne déborde sur la liste d'un autre. Terminaison : trois boucles bornées. Complexité : $Θ (n)$ pour (a) et (b), $Θ (m)$ pour (c) — soit $Θ (n + m)$ , ce qu'on voulait.

4. Ce qu'elle interdit, et pourquoi on l'emploie quand même. Elle interdit l'ajout et le retrait d'arcs : insérer un voisin à $u$ demanderait de décaler tout arrivee au-delà, en $Θ (m)$ . C'est une représentation figée, à construire une fois et à lire ensuite.

Or c'est précisément le cas d'usage. Un réseau routier, un graphe du web, un réseau social sont lus des milliards de fois entre deux modifications ; on les reconstruit à intervalles, on ne les édite pas en place. En échange, on obtient trois choses que le tableau rectangulaire ne donne pas : la mémoire exacte $Θ (n + m)$ , sans marge de sécurité à deviner — et donc sans DEG_MAX arbitraire dont un sommet pourrait sortir ; des voisins contigus en mémoire, donc parcourus à pleine vitesse par le processeur ; et aucune allocation dynamique, donc aucune fuite possible.

C'est le format qu'emploient réellement les bibliothèques de calcul sur graphes et de matrices creuses, sous le nom de stockage par lignes comprimées. Le chapitre a raison de recommander le tableau rectangulaire pour l'épreuve écrite ; celui-ci est ce qu'on écrit quand $n$ dépasse le million.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.