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

Le graphe du chapitre précédent : six sommets, sept arêtes.

Les trois représentations

La liste d'adjacence donne, pour chaque sommet, la liste de ses voisins. En Python, c'est un dictionnaire qui associe à chaque sommet la liste de ses voisins, {sommet: [voisins]} : c'est la convention de tout ce parcours.

La matrice d'adjacence est un tableau $n \times n$ où $A[i][j] = 1$ si l'arête $\{i, j\}$ existe, 0 sinon. Les opérations qu'on lui applique, produit et puissances, sont celles du chapitre de mathématiques sur les matrices.

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 la même information, à un détail près : un sommet isolé, sans aucune arête, n'apparaît dans aucune ligne d'une liste d'arêtes, et il faut alors garder à part la liste des sommets. La matrice (une ligne de zéros) et la liste d'adjacence (une liste vide) le conservent. À cette réserve près, 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 voient sur la matrice d'un coup d'œil

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, par une somme. La somme d'une ligne compte les voisins du sommet : c'est son degré, la colonne ajoutée à droite de la figure. Cette somme lit toute la ligne, soit

n

cases ; la liste d'adjacence, elle, donne le degré sans rien lire, par la longueur de la liste des voisins, len(adjacence[u]).

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, ce n'est pas ce facteur 2 qui pose problème, mais le

n^2

lui-même : la section suivante le chiffre.

Ce que chacune coûte

Les coûts s'écrivent avec la notation $O$ , qui dit comment le temps ou la mémoire grandit avec la taille du graphe, sans compter de secondes : $O(n + m)$ signifie « au plus proportionnel à $n + m$  », et $\Theta(n + m)$ , qu'emploie le chapitre suivant, « exactement de cet ordre, ni plus ni moins ». Le chapitre sur la complexité les définit ; ici, il suffit de lire un coût en $n^2$ comme un coût qui quadruple quand le nombre de sommets double, et un coût en $n + m$ comme un coût qui double quand les sommets et les arêtes doublent.

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

Le $O(1)$ d'un set est une moyenne : c'est une table de hachage, rapide en pratique, sans garantie dans le pire cas.

La ligne décisive est la deuxième. Presque 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 voisins, quelques centaines tout au plus, 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 : chaque compte range ses 200 relations, soit

200 \times 10^9 = 2 \times 10^{11}

entrées. Chaque amitié y est écrite deux fois, une fois chez chacun des deux comptes : c'est bien

2m

pour

m = 10^{11}

amitiés, comme le veut le lemme des poignées de main. Environ un téraoctet et demi à huit octets par entrée, réparti sur un ensemble de machines. C'est ce que font les vrais systèmes.

main.py

Sortie

>_ Prêt à exécuter…

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 chemins de longueur exactement $k$ entre les sommets $i$ et $j$ .

Ces chemins peuvent repasser par un sommet ou par une arête : C A C D est l'un des cinq chemins de longueur 3 qui vont de C à D.

La raison est simple à voir sur $A^2$ . Le coefficient $(i, j)$ vaut $\sum_{w} A[i][w] \times A[w][j]$ , et chaque terme de cette somme vaut 1 exactement quand $w$ est à la fois voisin de $i$ et voisin de $j$ , c'est-à-dire quand il y a un chemin $i \to w \to j$ . La somme compte donc ces chemins.

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 chemins fermés 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 qui se démontre en deux lignes, et qui compte les triangles d'un réseau sans jamais les chercher.

Vérification rapideon peut se reprendre

1.Un réseau social d'un milliard de comptes, 200 relations chacun. Pour afficher rapidement les amis d'un compte, quelle représentation ?

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

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 associe à chaque voisin son poids : elle devient un dictionnaire de dictionnaires, {sommet: {voisin: poids}}. Il faut alors décider ce que vaut une case sans arc : 0 convient tant qu'aucun poids n'est nul, mais un trajet gratuit s'y confondrait avec une absence de trajet ; les calculs de plus court chemin y mettent plutôt l'infini.

Graphe orienté et pondéré4 sommets, 5 arcs

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. Le degré sortant compte les cases non nulles d'une ligne, le degré entrant celles d'une colonne : la somme des poids n'est pas un degré.

Ce que l'orientation fait à la matrice.

La symétrie disparaît. La case $(A, C)$ vaut 2 et la case $(C, A)$ vaut 0 : 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 non nulles d'une ligne comptent les arcs qui partent, c'est le degré sortant $\deg^+$  ; celles d'une colonne comptent ceux qui arrivent, c'est le degré entrant $\deg^-$ . 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, mais pas dans la matrice. Dans la matrice, les successeurs d'un sommet se lisent sur sa ligne, ses prédécesseurs dans sa colonne : $n$ cases dans les deux cas. C'est la liste d'adjacence qui est asymétrique : elle range les successeurs de chaque sommet, et trouver ses prédécesseurs oblige à parcourir toutes les listes, en $O(n + m)$ . C'est pour cela qu'un algorithme qui a besoin des prédécesseurs, comme le tri topologique du chapitre 6, qui compte les arcs entrants de chaque sommet, les calcule une fois pour toutes au départ, ou construit 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 de zéros désigne un sommet d'où rien ne part : un puits, ici

D

. Une colonne de zéros 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…

Les conventions de ce parcours. Un graphe sans poids : un dictionnaire qui associe à chaque sommet la liste de ses voisins, {sommet: [voisins]}, ou de ses successeurs s'il est orienté, sans jamais y inscrire deux fois la même arête.
Un graphe pondéré : un dictionnaire de dictionnaires, {sommet: {voisin: poids}}.
Le dictionnaire qui retient, pour chaque sommet, celui par lequel on l'a atteint : parent.

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.
Inscrire deux fois la même arête. Une liste Python accepte les doublons : lire deux fois la même ligne d'un fichier ajoute l'arête une seconde fois, sans erreur, et fausse ensuite tous les degrés. Quand les données peuvent en contenir, des ensembles set de voisins les absorbent, et rendent en prime le test « v est-il voisin de u ? » immédiat, en

O(1)

en moyenne au lieu de

O(\deg(u))

Vérification rapideon peut se reprendre

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

Mettre en pratique

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 une dizaine de 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 au plus six.

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 chemins de longueur 2 allant de $i$ à $i$ , c'est-à-dire les allers-retours $i \to w \to i$ . Il y en a exactement un par voisin $w$ .

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 (chapitre 4), 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. Le revers : un sommet sans arête, un poste débranché ou une station fermée, disparaît du fichier, sauf à le lister à part.

Les voisins sont rangés dans des listes Python. Quand faut-il leur préférer des ensembles ?

Parcourir les voisins coûte la même chose dans les deux cas, $O(\deg(u))$  : c'est ce que font presque tous les algorithmes de ce parcours, et la liste, qui garde l'ordre, y suffit.

Le test d'appartenance v in adjacence[u] coûte en revanche $O(\deg(u))$ sur une liste, contre $O(1)$ en moyenne sur un set. Sur un algorithme qui fait ce test dans une boucle interne, cela transforme un $O(n + m)$ en quelque chose de nettement plus lent, sans que rien ne le signale. Le cas le plus courant n'est d'ailleurs pas la liste des voisins, mais l'ensemble des sommets déjà vus d'un parcours : rangé dans une liste, chacun de ses tests coûte $O(n)$ , et le parcours du chapitre 3 passe de $O(n + m)$ à $O(n \times m)$ .

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. Un set les écarte d'office.

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

Mettre en pratique

Dans la bibliothèque d'exercices

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