Représenter un graphe en machine

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.

Matrice d'adjacence
	A	B	C	D	E	F	d
A	0	1	1	0	0	0	2
B	1	0	1	0	0	0	2
C	1	1	0	1	0	0	3
D	0	0	1	0	1	1	3
E	0	0	0	1	0	1	2
F	0	0	0	1	1	0	2

Liste d'adjacence

A: : {B, C}
B: : {A, C}
C: : {A, B, D}
D: : {C, E, F}
E: : {D, F}
F: : {D, E}

Liste d'arêtes

(A, B)
(A, C)
(B, C)
(C, D)
(D, E)
(D, F)
(E, F)

Les trois écritures du graphe ci-dessus, calculées à partir des mêmes arêtes. La matrice est symétrique, parce que le graphe n'est pas orienté. Sa diagonale est nulle, parce qu'aucun sommet n'est son propre voisin. La somme d'une ligne donne le degré du sommet correspondant.

Les trois écritures contiennent exactement la même information : chacune se reconstruit à partir de n'importe laquelle des deux autres. Ce qui les sépare n'est pas ce qu'elles disent, mais ce qu'elles rendent facile.

Trois choses qui se lisent sur la matrice, et nulle part ailleurs

La symétrie. La case

(i, j)

et la case

(j, i)

portent la même valeur. C'est la traduction exacte de « l'arête n'a pas de sens », et cela se voit d'un coup d'œil là où il faudrait relire toute une liste d'arêtes.
La diagonale nulle. La case

(i, i)

demande « le sommet

i

est-il son propre voisin ». Un 1 sur la diagonale est une boucle ; un graphe simple n'en a aucune.
Les degrés, gratuitement. La somme d'une ligne compte les voisins du sommet : c'est son degré, sans parcourir quoi que ce soit. C'est la colonne d ajoutée à droite.

Un demi-tableau suffit, et pourtant on le stocke entier

Sur un graphe non orienté la moitié inférieure recopie la moitié supérieure : la moitié de la mémoire ne porte aucune information nouvelle. On la garde quand même, parce que tester A[i][j] sans se demander lequel de

i

j

est le plus grand vaut bien ce gâchis.
Sur les très grands graphes, en revanche, ce facteur 2 s'ajoute au

n^2

et la matrice devient inutilisable bien avant. C'est ce que chiffre la section suivante.

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 rapideon 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

Cinq arcs pondérés. Le sens compte : on va de A vers C, jamais l'inverse.

Et voici sa matrice. Elle se lit comme la précédente, à une différence près qui change tout.

Matrice d'adjacence
	B	C	D	d⁺
A	4	2	0	2
B	0	0	5	1
C	1	0	8	2
D	0	0	0	0
d⁻	2	1	2

La même information, en tableau. La case porte le poids, et non plus un simple 1. La matrice n'est pas symétrique : une flèche ne se lit que dans un sens. Sa diagonale est nulle, parce qu'aucun sommet n'est son propre voisin. La somme d'une ligne donne le degré sortant, celle d'une colonne le degré entrant.

Ce que l'orientation fait à la matrice

La symétrie disparaît. La case

(A, C)

vaut 2 et la case

(C, A)

est vide : c'est exactement ce que veut dire « on ne peut pas revenir ». Sur un graphe non orienté, la moitié de la matrice était redondante ; ici, chaque moitié porte une information différente.
Il y a désormais deux degrés. Les cases remplies d'une ligne comptent les arcs qui partent, c'est le degré sortant

d^+

 ; celles d'une colonne comptent ceux qui arrivent, c'est le degré entrant

d^-

. La figure affiche les deux, en marge droite et en bas. Attention à ne pas additionner les poids : un degré compte des arcs, il ne les pèse pas.
Chercher les prédécesseurs coûte cher. Lire une ligne est immédiat, lire une colonne oblige à descendre toute la matrice. C'est pour cela qu'un algorithme qui remonte les arcs, comme la recherche d'un plus court chemin à rebours, construit d'abord le graphe inverse plutôt que de payer ce parcours à chaque fois.

Repérer une source et un puits sans réfléchir

Une ligne vide désigne un sommet d'où rien ne part : un puits, ici

D

. Une colonne vide désigne un sommet où rien n'arrive : une source, ici

A

. Ces deux lectures serviront directement au tri topologique du chapitre sur les graphes orientés, dont c'est le point de départ.

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)

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

Compter 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 on veut la multiplier.
Liste d'arêtes quand l'algorithme balaie les arêtes sans jamais chercher un voisinage.
Écrire les deux sens pour une arête non orientée, ou passe par une fonction d'ajout qui le fait pour soi.
Vérifier la symétrie et la diagonale après toute construction depuis un fichier.
Garder le graphe inverse si l'algorithme a besoin des prédécesseurs.

Synthèse

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.

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

Synthèse

Mettre en pratique

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