Représenter un graphe en machine

Où on va

Un graphe au tableau est un dessin ; en mémoire, c'est une structure de données, et il y en a trois. Le choix n'est pas une question de goût : sur un réseau social d'un milliard de comptes, l'une des trois est matériellement impossible, et sur un petit graphe dense, une autre permet des calculs que les deux autres ne savent pas faire. Ce chapitre montre les trois, ce qu'elles coûtent, et ce que chacune rend facile.

Le même graphe, trois écritures

Prenons ce graphe et écrivons-le trois fois.

Graphe non orienté6 sommets, 7 arêtes

Les trois représentations

La liste d'adjacence donne, pour chaque sommet, la liste de ses voisins. En Python, un dictionnaire de set.

La matrice d'adjacence est un tableau $n \times n$ où $A[i][j] = 1$ si l'arête $\{i, j\}$ existe, 0 sinon.

La liste d'arêtes est la simple liste des paires.

Liste d'adjacence          Matrice d'adjacence         Liste d'arêtes
A : {B, C}                     A B C D E F             (A,B) (A,C) (B,C)
B : {A, C}                 A [ 0 1 1 0 0 0 ]           (C,D) (D,E) (D,F)
C : {A, B, D}              B [ 1 0 1 0 0 0 ]           (E,F)
D : {C, E, F}              C [ 1 1 0 1 0 0 ]
E : {D, F}                 D [ 0 0 1 0 1 1 ]
F : {D, E}                 E [ 0 0 0 1 0 1 ]
                           F [ 0 0 0 1 1 0 ]

Trois remarques se lisent directement sur la matrice. Elle est symétrique, parce que le graphe n'est pas orienté. Sa diagonale est nulle, parce qu'il n'y a pas de boucle. Et la somme d'une ligne donne le degré du sommet correspondant.

Ce que chacune coûte

Opération	Liste d'adjacence	Matrice	Liste d'arêtes
$u$ et $v$ sont-ils voisins ?	$O(1)$ avec un `set`	$O(1)$	$O(m)$
Parcourir les voisins de $u$	$O(d(u))$	$O(n)$	$O(m)$
Ajouter une arête	$O(1)$	$O(1)$	$O(1)$
Supprimer une arête	$O(1)$	$O(1)$	$O(m)$
Mémoire	$O(n + m)$	$O(n^2)$	$O(m)$

La ligne décisive est la deuxième. Tous les algorithmes de ce module passent leur temps à demander « qui sont les voisins de ce sommet ». Avec une liste d'adjacence, la réponse coûte le degré du sommet ; avec une matrice, elle coûte $n$ , qu'il y ait deux voisins ou aucun, car il faut lire toute la ligne.

Creux ou dense

Un graphe est creux quand $m$ est de l'ordre de $n$ , dense quand $m$ approche son maximum $\frac{n(n-1)}{2}$ .

Comment choisir, en une règle

Les graphes réels sont presque toujours creux : réseaux sociaux, routes, dépendances entre modules, chevauchements de tâches. Chaque sommet n'a que quelques dizaines de voisins, quel que soit le nombre total de sommets.
Pour un graphe creux, la liste d'adjacence gagne sur les deux tableaux à la fois : moins de mémoire et parcours plus rapide. C'est le choix par défaut.
La matrice ne se justifie que sur un graphe dense, sur de très petits graphes, ou quand on veut exploiter ses propriétés algébriques.

L'ordre de grandeur qui tranche

Un réseau social de $10^9$ comptes, chacun ayant environ 200 relations.
Matrice : $(10^9)^2 = 10^{18}$ cases. Même à un bit par case, cela fait plus de cent mille téraoctets. Impossible, et pas approximativement : impossible.
Liste d'adjacence : $2 \times 200 \times 10^9 = 4 \times 10^{11}$ entrées. Quelques téraoctets, réparties sur un ensemble de machines. C'est ce que font les vrais systèmes.

main.py

Sortie

>_ Prêt à exécuter…

Vérification rapidesans note, on peut se reprendre

1.Un réseau social d'un milliard de comptes, 200 relations chacun. Quelle représentation ?

2.Avec une matrice d'adjacence, parcourir les voisins d'un sommet coûte…

3.Sur un graphe non orienté sans boucle, la matrice d'adjacence est…

Ce que la matrice sait faire toute seule

La matrice a un pouvoir que les deux autres représentations n'ont pas : elle se multiplie.

Le théorème des puissances

Le coefficient $(i, j)$ de $A^k$ donne le nombre de chaînes de longueur exactement $k$ entre les sommets $i$ et $j$ .

La raison est simple à voir sur $A^2$ . Le coefficient $(i, j)$ vaut $\sum_k A[i][k] \times A[k][j]$ , et chaque terme de cette somme vaut 1 exactement quand $k$ est à la fois voisin de $i$ et voisin de $j$ , c'est-à-dire quand il y a une chaîne $i \to k \to j$ . La somme compte donc ces chaînes.

main.py

Sortie

>_ Prêt à exécuter…

Compter les triangles sans les chercher

La trace de $A^3$, la somme de sa diagonale, compte les chaînes fermées de longueur 3. Chaque triangle en produit six : trois sommets de départ possibles, deux sens de parcours.
Le nombre de triangles vaut donc $\frac{\operatorname{trace}(A^3)}{6}$. C'est un résultat qu'on démontre en deux lignes et qui impressionne beaucoup en devoir.

Orienté, pondéré : les mêmes structures, adaptées

Pour un graphe orienté, on ne remplit qu'un sens : la matrice cesse d'être symétrique, et la liste d'adjacence ne contient que les successeurs. Si l'algorithme a besoin des prédécesseurs, il faut construire aussi le graphe inverse.

Pour un graphe pondéré, la case de la matrice contient le poids au lieu de 1, et la liste d'adjacence stocke des paires (voisin, poids).

Graphe orienté et pondéré4 sommets, 5 arêtes

main.py

Sortie

>_ Prêt à exécuter…

Deux erreurs qui coûtent cher

Oublier la symétrie. Sur un graphe non orienté, ajouter l'arête {u, v} demande deux écritures dans la liste d'adjacence. En oublier une donne un graphe à demi orienté, et les parcours donnent alors des résultats incompréhensibles.
Utiliser une liste au lieu d'un ensemble. Avec une liste Python, tester l'appartenance coûte $O(d)$ au lieu de $O(1)$, et rien n'empêche d'insérer deux fois la même arête. Le set règle les deux problèmes d'un coup.

Exercices type

Quelle représentation pour un réseau routier de 200 000 carrefours ?

Liste d'adjacence.

Un carrefour a rarement plus de six routes, donc $m$ est de l'ordre de $6 \times 10^5$  : le graphe est très creux. La liste occupe quelques mégaoctets.

La matrice demanderait $(2 \times 10^5)^2 = 4 \times 10^{10}$ cases, soit des dizaines de gigaoctets pour stocker presque exclusivement des zéros. Et chaque recherche de voisins lirait 200 000 cases pour en trouver quatre.

Comment vérifier sur la matrice qu'un graphe est non orienté et sans boucle ?

Non orienté : la matrice doit être symétrique, c'est-à-dire $A[i][j] = A[j][i]$ pour toute paire.

Sans boucle : la diagonale doit être nulle, car $A[i][i] = 1$ signifierait une arête d'un sommet vers lui-même.

Ces deux contrôles se codent en deux boucles et servent de garde-fou après une lecture de fichier : une matrice non symétrique alors qu'on attendait un graphe non orienté signale presque toujours une arête ajoutée dans un seul sens.

Que vaut le coefficient $(i, i)$ de $A^2$, et pourquoi ?

Il vaut le degré du sommet $i$ .

Le coefficient $(i, i)$ de $A^2$ compte les chaînes de longueur 2 allant de $i$ à $i$ , c'est-à-dire les allers-retours $i \to k \to i$ . Il y en a exactement un par voisin $k$ .

Donc la diagonale de $A^2$ donne la suite des degrés, ce qui fournit au passage un contrôle de cohérence gratuit sur une matrice construite à la main.

Pourquoi une liste d'arêtes reste-t-elle utile malgré ses coûts ?

Parce que certains algorithmes ne demandent jamais « qui sont les voisins de $u$  », mais parcourent simplement toutes les arêtes.

C'est le cas de l'algorithme de Kruskal, qui trie les arêtes par poids croissant et les examine une par une : la liste d'arêtes est exactement la forme dont il a besoin.

C'est aussi le format d'échange le plus courant dans les fichiers, une ligne par arête, parce qu'il est compact et se lit sans connaître le nombre de sommets à l'avance.

Un graphe est stocké en liste d'adjacence avec des listes Python. Quel problème ?

Le test d'appartenance v in adjacence[u] coûte $O(d(u))$ sur une liste, contre $O(1)$ sur un set.

Sur un algorithme qui teste l'adjacence dans une boucle interne, cela transforme un $O(n + m)$ en quelque chose de nettement plus lent, sans que rien ne le signale.

Une liste autorise en outre les doublons : ajouter deux fois la même arête passe inaperçu et fausse ensuite tous les degrés. Le set interdit les deux erreurs.

La méthode

Compte l'ordre de grandeur de $n$ et de $m$ avant de choisir.
Liste d'adjacence par défaut, avec des set et non des listes.
Matrice seulement si le graphe est dense, minuscule, ou si tu veux la multiplier.
Liste d'arêtes quand l'algorithme balaie les arêtes sans jamais chercher un voisinage.
Écris les deux sens pour une arête non orientée, ou passe par une fonction d'ajout qui le fait pour toi.
Vérifie la symétrie et la diagonale après toute construction depuis un fichier.
Garde le graphe inverse si l'algorithme a besoin des prédécesseurs.

En résumé

Trois représentations : liste d'adjacence, matrice, liste d'arêtes.
La liste d'adjacence coûte $O(n + m)$ en mémoire et donne les voisins en $O(d(u))$ .
La matrice coûte $O(n^2)$ quel que soit le nombre d'arêtes.
Les graphes réels sont creux : la liste d'adjacence est le choix par défaut.
Sur un graphe non orienté, la matrice est symétrique et sa diagonale est nulle.
La somme d'une ligne de la matrice donne le degré du sommet.
Le coefficient $(i, j)$ de $A^k$ compte les chaînes de longueur $k$ .
La trace de $A^3$ vaut six fois le nombre de triangles.
Pour un graphe orienté, il faut parfois stocker aussi le graphe inverse.

Et ensuite ? Une fois le graphe en mémoire, la première chose qu'on veut en faire est de le parcourir. Le chapitre suivant présente les deux parcours fondamentaux, et tout ce qu'ils révèlent.

Représenter un graphe en machine

Ce que ce chapitre apporte

Le même graphe, trois écritures

Ce que chacune coûte

Ce que la matrice sait faire toute seule

Orienté, pondéré : les mêmes structures, adaptées

Exercices type

La méthode

En résumé

Orienté, pondéré : les mêmes structures, adaptées