Représentation des Graphes

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La représentation n'est pas un détail d'implémentation

Un graphe est un objet abstrait : un ensemble de sommets et d'arêtes, rien de plus. Un ordinateur ne sait pas stocker un objet abstrait. Il stocke des octets, et le choix de ces octets décide, avant même la première ligne d'algorithme, de ce dont votre programme est capable.

L'affirmation est facile à énoncer et facile à sous-estimer, en voici donc la version la plus tranchante. Le parcours en largeur s'exécute en temps O(n + m) sur une liste d'adjacence et en temps O(n2) sur une matrice d'adjacence. Même algorithme, même graphe, même résultat. Seul le stockage change. Sur un graphe d'un million de sommets et cinquante millions d'arêtes, c'est la différence entre environ 51 millions d'opérations et environ mille milliards : un facteur d'à peu près 19,600. Aucun réglage de facteurs constants ne rattrape cela. La représentation était depuis le début la complexité asymptotique de l'algorithme.

La raison est simple une fois vue. Les deux versions de BFS font la même chose à chaque sommet : énumérer ses voisins. Une liste d'adjacence répond à « quels sont les voisins de v ? » en un temps proportionnel à leur nombre. Une matrice d'adjacence y répond en balayant une ligne entière de longueur n, composée en majorité de zéros. Sommé sur tous les sommets, la liste coûte 2m et la matrice coûte n2. C'est exactement l'observation sur laquelle Hopcroft et Tarjan ont bâti leurs algorithmes de graphes en temps linéaire au début des années 1970, et c'est pourquoi la liste d'adjacence est devenue le choix par défaut dans tous les cours d'algorithmique depuis.

Mais la liste d'adjacence n'est pas toujours la réponse, et la traiter comme le choix automatique est une erreur en soi. Demandez si deux sommets donnés sont adjacents et la matrice répond en un accès mémoire là où la liste balaye une séquence de voisins. Multipliez le graphe par lui-même et la matrice vous donne gratuitement le nombre de marches. Stockez un graphe réellement dense et la matrice occupe moins de mémoire, pas plus. Exécutez sur un GPU et aucune des deux structures n'est ce qu'il vous faut.

La formulation honnête n'est donc pas « quelle représentation est la meilleure », mais quelle question allez-vous poser le plus souvent, et quelle est la taille du graphe. Cet article passe en revue les sept représentations qui comptent en pratique, en déduit le coût de chaque opération sur chacune, et se termine par une procédure de décision. Tous les chiffres concernant le graphe d'exemple ci-dessous ont été calculés par script plutôt qu'affirmés, et le calcul est reproduit pour que vous puissiez le vérifier.

2. L'exemple récurrent

Un petit graphe pondéré porte tout l'article. Il est volontairement assez minuscule pour être écrit en entier dans chaque représentation, et volontairement assez irrégulier pour que les représentations aient vraiment l'air différentes.

V = {0, 1, 2, 3, 4, 5}

E = { {0,1}:4   {0,2}:3   {1,2}:2   {1,3}:5   {2,4}:7   {3,4}:1   {3,5}:6 }

n = 6      m = 7      somme des degrés = 14 = 2m
degrés     0:2   1:3   2:3   3:3   4:2   5:1

Deux faits à son sujet vont revenir sans cesse. Ses ensembles de voisins, écrits dans l'ordre croissant, sont

0 → 1, 2
1 → 0, 2, 3
2 → 0, 1, 4
3 → 1, 4, 5
4 → 2, 3
5 → 3

et sa densité vaut 7 / 15 = 46.7%, puisqu'un graphe simple à 6 sommets admet au plus C(6,2) = 15 arêtes. C'est très dense à l'échelle du monde réel, ce qui constitue un correctif utile : les graphes jouets des manuels sont presque toujours denses, et les intuitions qu'ils construisent sur la représentation sont presque toujours fausses pour des données de production. Nous corrigerons cela à la section 6.

3. La liste d'arêtes

La représentation la plus simple consiste à écrire les arêtes et à s'arrêter là.

edges = [ (0,1,4), (0,2,3), (1,2,2), (1,3,5), (2,4,7), (3,4,1), (3,5,6) ]

Un tableau de m triplets. L'espace est en Θ(n + m) si vous gardez aussi un compte des sommets, et en Θ(m) si l'ensemble des sommets est implicite dans les arêtes. Rien n'est précalculé, rien n'est indexé.

La conséquence est que presque toute requête est un balayage complet. « 1 et 4 sont-ils adjacents ? » impose de parcourir les sept arêtes. « Quels sont les voisins de 3 ? » impose de parcourir les sept arêtes. Les deux sont en O(m), ce qui est catastrophique si vous le faites dans une boucle sur les sommets, car cela devient O(nm).

Et pourtant la liste d'arêtes n'est pas un choix naïf, car trois situations importantes veulent exactement cette forme :

• Les algorithmes qui itèrent sur les arêtes plutôt que sur les sommets. L'algorithme de Kruskal trie toutes les arêtes par poids et les examine dans l'ordre ; il ne demande jamais de liste de voisins. Bellman-Ford relâche chaque arête n - 1 fois ; à nouveau, pure itération sur les arêtes. Pour ceux-là, la liste d'arêtes n'est pas seulement suffisante, elle est optimale, puisque toute autre représentation devrait être réaplatie dans l'ordre des arêtes.
• Échange et stockage. Tout format de fichier de graphe sur disque est une liste d'arêtes, car c'est la seule représentation indépendante de l'ordre, purement additive et triviale à analyser. Quand vous téléchargez un jeu de données depuis SNAP ou les collections DIMACS, vous obtenez une liste d'arêtes, et votre premier geste est de la convertir.
• Streaming. Si le graphe ne tient pas du tout en mémoire, c'est une liste d'arêtes qui arrive, une arête à la fois, et le modèle de calcul semi-streaming repose sur l'hypothèse que c'est tout ce que vous aurez.

La règle pratique est qu'une liste d'arêtes est un format de transport et un format de parcours , pas un format de requête. Les systèmes réels lisent une liste d'arêtes et construisent aussitôt quelque chose d'indexé. Cette conversion fait l'objet de la section 7, et elle coûte moins cher qu'on ne le croit : un tri par comptage sur les identifiants de sommets la réalise en O(n + m).

4. La matrice d'adjacence

Numérotez les sommets de 0 à n - 1 et construisez la matrice n × n notée A , dans laquelle A[u][v] = 1 si {u, v} est une arête et 0 sinon. Pour l'exemple récurrent :

      0  1  2  3  4  5        somme de ligne
  0 [ 0  1  1  0  0  0 ]         2
  1 [ 1  0  1  1  0  0 ]         3
  2 [ 1  1  0  0  1  0 ]         3
  3 [ 0  1  0  0  1  1 ]         3
  4 [ 0  0  1  1  0  0 ]         2
  5 [ 0  0  0  1  0  0 ]         1

36 cases, dont 14 non nulles

Trois propriétés structurelles en découlent directement, et chacune est une vérification utile au débogage.

• La matrice d'un graphe non orienté est symétrique. A[u][v] = A[v][u] toujours, donc la moitié du stockage est redondante. Les graphes orientés abandonnent cette symétrie, et c'est précisément ce qui rend l'orientation visible dans l'algèbre.
• Les sommes de lignes sont les degrés : 2, 3, 3, 3, 2, 1, conformes à la liste de la section 2. Le nombre total de uns vaut 2m = 14, puisque chaque arête occupe deux cases.
• La diagonale est nulle pour un graphe simple, car une entrée diagonale non nulle est une boucle.

Ce que vous gagnez, c'est l'adjacence en temps constant. Demander si 1 et 4 sont adjacents, c'est une seule lecture dans le tableau, A[1][4], indépendamment du degré. Aucune autre représentation de cet article n'y parvient sans hachage. Ce que vous payez, c'est Θ(n2) d'espace quel que soit le nombre d'arêtes, et Θ(n) de temps pour énumérer les voisins d'un sommet, aussi peu nombreux soient-ils.

C'est ce dernier coût qui mord. Le sommet 5 n'a qu'un seul voisin, mais lire la ligne 5 pour le découvrir touche six cases. Passez à un million de sommets et trouver les voisins d'un sommet de degré un touche un million de cases. Le O(n2) du BFS sur matrice, c'est entièrement cet effet, accumulé.

Le raffinement par bits. Si le graphe n'est pas pondéré, chaque case a besoin d'un bit, pas d'un octet et certainement pas d'un entier 32 bits. Empaqueter les lignes dans des mots machine divise la mémoire par 8 face à une matrice d'octets et par 32 face à une matrice d'entiers, et fait quelque chose de plus intéressant : cela permet d'opérer sur 64 voisins par instruction. Intersecter deux voisinages, qui est la boucle interne du comptage de triangles et de nombreux algorithmes de clique, devient un AND par mots sur n/64 mots au lieu d'une boucle sur n entrées. Nous y revenons à la section 11, car c'est la principale raison de la survie des représentations denses.

5. La liste d'adjacence

Stockez, pour chaque sommet, une séquence de ses voisins.

adj[0] = [ (1,4), (2,3) ]
adj[1] = [ (0,4), (2,2), (3,5) ]
adj[2] = [ (0,3), (1,2), (4,7) ]
adj[3] = [ (1,5), (4,1), (5,6) ]
adj[4] = [ (2,7), (3,1) ]
adj[5] = [ (3,6) ]

L'espace est en Θ(n + m) : un emplacement par sommet plus 2m = 14 entrées de voisins pour un graphe non orienté, ou m pour un graphe orienté. Énumérer les voisins de v coûte Θ(deg(v)), ce qui est optimal, puisqu'on ne peut pas lister k choses en moins de k de temps.

C'est la représentation qui rend possibles les algorithmes de graphes en temps linéaire, et son adoption a une histoire précise. L'article de Tarjan de 1972 sur le parcours en profondeur et les algorithmes compagnons de Hopcroft et Tarjan de 1973 sont explicites : les bornes en O(n + m) dépendent d'un stockage en liste d'adjacence ; les mêmes procédures sur une matrice sont en O(n2). Le manuel d'Aho, Hopcroft et Ullman de 1974 a ensuite fait de la liste la présentation standard, et elle est depuis le choix par défaut dans le code de parcours .

Le prix à payer est que le test d'adjacence n'est plus constant. Pour répondre à « 1 et 4 sont-ils adjacents ? », vous balayez adj[1], trois entrées, et ne trouvez rien. En général c'est en O(deg(u)), ou en O(min(deg(u), deg(v))) si vous êtes assez soigneux pour balayer la plus courte des deux listes. Sur un graphe comportant quelques sommets de très haut degré, ce à quoi ressemble tout graphe social ou web, ce minimum peut encore se compter en millions.

La question de l'ordre des voisins. Rien dans la définition n'impose que les séquences de voisins soient triées, et la plupart du code les laisse dans l'ordre d'insertion. Les trier coûte O(m log m) une fois et apporte deux choses : une adjacence en recherche binaire en O(log deg(u)), et l'intersection de voisinages en temps linéaire par fusion, sur laquelle reposent les implémentations rapides du comptage de triangles. Si vous intersectez des voisinages, triez.

Le piège d'implémentation. L'image de manuel d'une liste d'adjacence est un tableau de listes chaînées, et cette image est un mauvais conseil sur le matériel moderne. Une liste chaînée déréférence un pointeur par voisin, et chaque déréférencement est un défaut de cache potentiel qui coûte de l'ordre de cent cycles. Un vector<vector<int>> vaut mieux, puisque les voisins de chaque sommet sont contigus, mais cela éparpille encore n blocs alloués séparément dans le tas et paie un en-tête d'allocation par sommet. La solution se trouve à la section 7.

Les variantes à base de hachage. Remplacer chaque séquence de voisins par un ensemble haché donne un test d'adjacence en O(1) attendu tout en conservant un espace en Θ(n + m) , ce qui semble réunir le meilleur des deux mondes. En pratique la constante est rude : un ensemble haché coûte plusieurs fois la mémoire d'un tableau compact d'entiers, détruit la localité d'itération et ralentit sensiblement le balayage des voisins, c'est-à-dire l'opération que vous faites le plus. Utilisez-le quand les requêtes d'adjacence dominent réellement le parcours, et mesurez au lieu de supposer.

6. Ce que « creux » veut vraiment dire

Tout ce qui précède tient à un seul mot. Un graphe est creux quand m est proche de n et dense quand m est proche de n2, et la ligne de partage pratique est la densité

densité = m / C(n,2) = 2m / (n(n-1))

c'est-à-dire la fraction des arêtes possibles qui existent. L'exemple récurrent se situe à 7/15 = 46,7 %, ce qui est énormément dense. Les graphes réels ne sont pas ainsi. Un réseau social d'un million d'utilisateurs et cinquante millions d'amitiés, soit 100 amis en moyenne, a une densité de 1.0 × 10-4 : un centième de un pour cent. Les réseaux routiers sont encore plus extrêmes, avec un degré moyen inférieur à 3 parce qu'un carrefour n'a qu'un nombre borné de routes. Le graphe du web, les graphes de citations, les réseaux d'interaction de protéines et les graphes de dépendances sont tous dans le même régime.

Voici ce que cela coûte, calculé pour exactement ce graphe d'un million de sommets :

La matrice est environ 300 fois plus grande que les structures creuses, même réduite à des bits isolés, et elle ne tient dans la mémoire d'aucune machine ordinaire. Ce n'est pas une préférence marginale. C'est la différence entre un programme qui s'exécute et un programme qui ne peut pas démarrer.

Le seuil mérite d'être connu précisément. Une matrice empaquetée en bits coûte n2/8 octets ; une structure creuse stockant une cible de 4 octets par arc orienté coûte environ 8m octets. La matrice l'emporte quand n2/8 < 8m, c'est-à-dire quand m > n2/64, ce qui correspond à une densité supérieure à environ 3,1 %. Au-dessus, utilisez une matrice ; en dessous, non. Presque tous les graphes que vous rencontrerez hors des petits problèmes de recherche combinatoire sont trois ordres de grandeur en dessous.

La comparaison complète, opération par opération, avec d pour le degré du sommet concerné :

Le tableau sous essentiellement cette forme est la présentation standard, elle remonte à Aho, Hopcroft et Ullman et est reproduite dans le chapitre sur les graphes de Cormen, Leiserson, Rivest et Stein. Lisez-le comme un énoncé sur la question que vous posez, et non sur la ligne qui serait la meilleure. La seule case où la matrice est unique en son genre est le test d'adjacence, et les seules cases où la liste d'arêtes est forte sont l'itération sur les arêtes entières et l'ajout en fin. Tout le reste appartient aux structures creuses indexées.

7. La ligne creuse compressée

La représentation qu'utilise réellement le code de graphes en production n'est pas la liste d'adjacence sous forme de tableau de vecteurs. C'est la ligne creuse compressée, empruntée telle quelle à l'algèbre linéaire creuse, où elle est standard depuis les travaux de Gustavson au début des années 1970 et documentée chez Duff, Erisman et Reid comme le schéma canonique de stockage creux. Dans le monde des graphes on l'appelle parfois la représentation forward star , ou simplement une liste d'adjacence aplatie.

L'idée est de concaténer toutes les séquences de voisins en un seul tableau et de garder un second tableau indiquant où commence la tranche de chaque sommet.

offsets = [ 0, 2, 5, 8, 11, 13, 14 ]                       longueur n + 1 = 7
targets = [ 1, 2, 0, 2, 3, 0, 1, 4, 1, 4, 5, 2, 3, 3 ]     longueur 2m  = 14
weights = [ 4, 3, 4, 2, 5, 3, 2, 7, 5, 1, 6, 7, 1, 6 ]     longueur 2m  = 14

Les voisins du sommet v sont targets[offsets[v] .. offsets[v+1] - 1]. Pour le sommet 2, ce sont les positions 5 à 7, ce qui donne les voisins [0, 1, 4] avec les poids [3, 2, 7], ce qui correspond exactement à adj[2] . Le degré vient gratuitement comme offsets[v+1] - offsets[v], retrouvant 2, 3, 3, 3, 2, 1 sans toucher du tout au tableau des cibles.

Asymptotiquement, c'est identique à une liste d'adjacence. En pratique c'est nettement plus rapide, pour quatre raisons qui n'ont rien à voir avec le grand O :

• La localité. Les voisins d'un sommet occupent des octets consécutifs, donc les balayer défile dans les lignes de cache au lieu de suivre des pointeurs. Le préchargeur matériel voit le motif d'accès et garde une longueur d'avance.
• Aucune allocation par sommet. Deux allocations en remplacent n + 1 . Sur l'exemple à un million de sommets, cela supprime environ 38 Mio d'en-têtes et, surtout, supprime un million d'occasions pour les blocs de voisins de se disperser.
• Trivialement sérialisable. Toute la structure tient en deux tableaux d'entiers : elle peut donc être mappée en mémoire depuis le disque, envoyée sur un réseau ou confiée à un GPU sans corriger de pointeurs.
• Compression des indices. Comme targets contient des identifiants de sommets, un graphe de moins de 2³² sommets n'a besoin que de 4 octets par entrée, et un graphe de moins de 2¹⁶ n'en demande que 2. Le tableau des offsets, lui, a besoin d'entrées 64 bits dès que 2m dépasse 2³¹, ce qui est une erreur réelle et fréquente à l'échelle du milliard d'arêtes.

Construire une CSR à partir d'une liste d'arêtes coûte O(n + m) et ne demande aucun tri. Comptez le degré de chaque sommet en une passe, faites la somme préfixe des compteurs dans offsets, puis faites une seconde passe en plaçant chaque arête à son emplacement avec un curseur mobile par sommet. C'est un tri par comptage selon le sommet source, et c'est la voie d'ingestion standard dans toute bibliothèque de graphes sérieuse.

Le prix, c'est la rigidité. Insérer une seule arête décale toutes les entrées suivantes de targets, la structure est donc de fait immuable : vous la reconstruisez en Θ(n + m) au lieu de la mettre à jour. C'est un bon compromis quand le graphe est chargé une fois et interrogé souvent, ce qui décrit la plupart des charges analytiques, et un mauvais quand le graphe change sans arrêt. La section 12 traite le second cas.

8. La matrice d'incidence

La troisième matrice classique indexe les sommets face aux arêtes plutôt que face aux sommets. Étiquetez les sept arêtes de e1 à e7 dans l'ordre où elles ont été listées, et posez B[v][e] = 1 quand v est une extrémité de e :

       e1 e2 e3 e4 e5 e6 e7
   0 [  1  1  0  0  0  0  0 ]
   1 [  1  0  1  1  0  0  0 ]
   2 [  0  1  1  0  1  0  0 ]
   3 [  0  0  0  1  0  1  1 ]
   4 [  0  0  0  0  1  1  0 ]
   5 [  0  0  0  0  0  0  1 ]

sommes de colonnes toutes à 2      sommes de lignes 2,3,3,3,2,1 = degrés

La forme est n × m, donc l'espace est en Θ(nm), ce qui est pire que la matrice d'adjacence pour tout graphe ayant plus d'arêtes que de sommets. Personne ne stocke un graphe ainsi pour calculer. La matrice d'incidence gagne sa place pour une autre raison : elle est le pont entre la théorie des graphes et l'algèbre linéaire.

Deux identités le montrent. Pour la matrice non signée ci-dessus, B BT = A + D, où D est la matrice diagonale des degrés. En y substituant les nombres de l'exemple récurrent, on le vérifie exactement. Si au contraire vous orientez chaque arête arbitrairement et écrivez -1 à son origine et +1 à son extrémité, la matrice d'incidence signée Bs vérifie

B_s B_s^T  =  D - A  =  L,   le laplacien

indépendamment de l'orientation choisie. Cette identité est la raison pour laquelle le laplacien est semi-défini positif, et c'est la porte d'entrée de la théorie spectrale des graphes. Diestel poursuit cette ligne en utilisant la matrice d'incidence pour définir l'espace des cycles et l'espace des coupes d'un graphe, deux espaces vectoriels sur le corps à deux éléments dont les dimensions valent m - n + c et n - c pour un graphe à c composantes. La matrice d'incidence est aussi le cadre naturel des problèmes de flot : la matrice des contraintes d'un programme linéaire de flot de réseau est la matrice d'incidence signée, et sa totale unimodularité est ce qui garantit que le programme linéaire admet des solutions optimales entières.

Une dernière remarque. La matrice d'incidence gère les multigraphes avec plus d'élégance que la matrice d'adjacence, puisque les arêtes parallèles sont simplement des colonnes distinctes plutôt qu'un compte entassé dans une case. Les hypergraphes, où une arête peut relier plus de deux sommets, n'ont aucune matrice d'adjacence sensée mais une matrice d'incidence parfaitement naturelle avec des sommes de colonnes supérieures à deux. Si vous devez un jour généraliser au-delà des graphes ordinaires, c'est la représentation qui se généralise.

9. Orientation, poids, multiplicité et boucles

Tout ce qui précède supposait un graphe simple non orienté. Quatre écarts courants changent ce que chaque représentation doit faire, et c'est là que se concentrent les bugs d'implémentation.

Orientation. Dans un graphe orienté la matrice d'adjacence cesse d'être symétrique, et A[u][v] = 1 signifie seulement un arc de u vers v . La liste d'adjacence stocke chaque arc une fois au lieu de deux, donc les tableaux de voisins contiennent m entrées plutôt que 2m. Cette division par deux est de loin la source la plus fréquente d'estimations mémoire fausses d'un facteur deux.

La vraie complication est qu'un graphe orienté a deux voisinages. adj[v] donne les successeurs ; les prédécesseurs exigent soit de balayer toute la structure, soit de stocker une seconde copie avec tous les arcs inversés. L'algèbre linéaire creuse appelle cette seconde copie colonne creuse compressée, et tout algorithme qui remonte en arrière, y compris l'accessibilité inverse, la procédure de composantes fortement connexes de Kosaraju et le Dijkstra arrière dans la recherche bidirectionnelle, en a besoin. Prévoyez deux structures, pas une.

Poids. Les poids peuvent vivre directement dans les cases de la matrice, en remplaçant le 1 par le poids. La subtilité est ce que devient une non-arête : 0 est un poids légitime, donc une case à 0 est ambiguë. La convention est de stocker ∞ pour les arêtes absentes dans un contexte de plus courts chemins, ce que Floyd-Warshall suppose précisément en entrée, et 0 dans un contexte de flot, où un arc de capacité nulle et un arc absent sont vraiment la même chose. Choisissez délibérément. Dans les structures creuses, le poids va dans un tableau parallèle indexé exactement comme targets, comme dans le listing CSR ci-dessus, ce qui garde les deux au pas et préserve la localité. Stocker des paires entrelacées convient aussi et vaut parfois mieux ; stocker les poids dans une table de hachage séparée indexée par arête est presque toujours pire.

Multiplicité. Les arêtes parallèles brisent la prémisse de base de la matrice d'adjacence, puisqu'une case contient une valeur. Le correctif habituel est de stocker la multiplicité comme un compte entier, ce qui marche pour les problèmes de comptage mais jette les données propres à chaque arête, comme des poids ou des identifiants distincts. Les listes d'adjacence acceptent les arêtes multiples sans broncher : le même voisin apparaît simplement plus d'une fois. Si vous avez besoin d'attributs par arête sur un multigraphe, stockez des identifiants d'arêtes dans les tableaux de voisins et gardez les attributs dans une table d'arêtes séparée indexée par ces identifiants, ce que font la plupart des bases de données de graphes.

Boucles. Une boucle en v met une valeur non nulle sur la diagonale. La convention qui piège, c'est que dans un graphe non orienté une boucle apporte 2 au degré de v, si bien que la matrice d'adjacence non orientée standard stocke A[v][v] = 2 pour une seule boucle, afin que l'identité somme de ligne égale degré reste vraie. Beaucoup de code stocke 1 à la place et rapporte ensuite discrètement des degrés faux. Dans une liste d'adjacence, la même question devient de savoir si v apparaît une ou deux fois dans sa propre séquence de voisins, et la réponse honnête est qu'il faut trancher et le documenter, car les deux conventions existent dans la littérature.

10. Représentations algébriques

Dès lors qu'un graphe est une matrice, les opérations matricielles veulent dire quelque chose. Ce n'est pas une curiosité, c'est la base de tout un style de calcul sur les graphes.

Les puissances de la matrice d'adjacence comptent les marches. L'entrée Ak[u][v] est exactement le nombre de marches de longueur k de u vers v, ce qui s'obtient par récurrence à partir de la définition du produit matriciel. Sur l'exemple récurrent :

A^2 =  [ 2  1  1  1  1  0 ]
       [ 1  3  1  0  2  1 ]
       [ 1  1  3  2  0  0 ]
       [ 1  0  2  3  0  0 ]
       [ 1  2  0  0  2  1 ]
       [ 0  1  0  0  1  1 ]

On y lit A2[1][4] = 2 : il y a deux marches de longueur 2 de 1 à 4, à savoir 1→2→4 et 1→3→4. Vérifiez-le sur le dessin. La diagonale A2[v][v] vaut 2, 3, 3, 3, 2, 1, c'est-à-dire de nouveau la suite des degrés, car une marche de longueur 2 de v vers lui-même est un pas vers un voisin puis le retour. Une puissance plus loin, trace(A3) = 6, et la division par 6 donne un triangle, que la force brute confirme être {0, 1, 2}. La division par 6 tient compte des trois points de départ et des deux sens de parcours de chaque triangle.

Le laplacien. Définissez L = D - A :

L =  [  2 -1 -1  0  0  0 ]
     [ -1  3 -1 -1  0  0 ]
     [ -1 -1  3  0 -1  0 ]
     [  0 -1  0  3 -1 -1 ]
     [  0  0 -1 -1  2  0 ]
     [  0  0  0 -1  0  1 ]

Chaque ligne somme à zéro, donc le vecteur de uns est dans le noyau et L est singulière. Le théorème matrice-arbre de Kirchhoff dit que supprimer une ligne quelconque et la colonne correspondante puis prendre le déterminant compte les arbres couvrantsdu graphe. Les six cofacteurs de la matrice ci-dessus valent tous 11, et énumérer les C(7,5) = 21 sous-ensembles de cinq arêtes en testant l'absence de cycle trouve exactement 11 arbres couvrants. Le théorème n'est pas une approximation, c'est une identité, et il transforme un problème de comptage d'apparence exponentielle en un seul déterminant.

Les valeurs propres du laplacien en disent davantage. La multiplicité de la valeur propre 0 est le nombre de composantes connexes. La deuxième plus petite valeur propre, la connectivité algébrique de Fiedler, mesure la difficulté à déconnecter le graphe, et le motif de signes de son vecteur propre fournit une bissection utilisable. C'est la machinerie derrière le clustering spectral et derrière une large part de la théorie spectrale des graphes de Chung.

Les graphes comme algèbre linéaire sur des semi-anneaux. La version la plus profonde de cette idée est que beaucoup d'algorithmes de graphes sont des opérations matricielles, une fois l'arithmétique changée. Remplacez (+, ×) par (min, +) et le produit matriciel devient le relâchement des plus courts chemins, donc An-1 sur le semi-anneau min-plus est la matrice des plus courts chemins entre toutes les paires. Remplacez-le par (OR, AND) et il devient l'accessibilité. Le parcours en largeur depuis une source est la multiplication répétée d'un vecteur de front creux par la matrice d'adjacence sur un semi-anneau booléen. Kepner et Gilbert exposent cela systématiquement, et c'est la spécification qu'implémente le standard GraphBLAS. Le gain est pratique : exprimer un algorithme comme des produits matrice creuse par vecteur lui fait hériter de décennies d'algèbre linéaire parallèle optimisée, et c'est ainsi que sont construits de nombreux frameworks de graphes sur GPU.

11. Quand la matrice gagne

Après la section 6, il serait facile de conclure que les matrices d'adjacence sont un outil pédagogique. Elles ne le sont pas, et il vaut la peine d'être précis sur les quatre situations où la matrice est la bonne réponse.

Petit n. Si n vaut quelques centaines, n2 fait quelques dizaines de milliers de cases et l'argument mémoire s'évapore. Floyd-Warshall calcule les plus courts chemins entre toutes les paires en temps Θ(n3) et espace Θ(n2) sur une matrice, avec une boucle interne de trois lignes et un comportement de cache quasi parfait ; pour n de l'ordre de quelques centaines, il bat couramment l'exécution de Dijkstra n fois sur une structure creuse, malgré une asymptotique moins bonne. La programmation compétitive et la recherche opérationnelle regorgent de ce régime.

Les graphes réellement denses. Au-dessus du seuil de densité d'environ 3,1 % calculé plus haut, la matrice est plus petite en plus d'être plus rapide. Les graphes complémentaires, les graphes de similarité à seuil permissif et les graphes de contraintes issus de problèmes d'ordonnancement atterrissent régulièrement ici.

Le parallélisme par bitsets. C'est l'argument le plus fort. Empaquetez chaque ligne de la matrice dans des mots machine et les opérations ensemblistes sur les voisinages deviennent parallèles par mot. La fermeture transitive par la méthode des Quatre Russes, introduite par Arlazarov, Dinic, Kronrod et Faradzev en 1970, calcule l'accessibilité en O(n3 / log n) en précalculant des résultats pour des blocs de bits ; la même astuce avec de simples mots de 64 bits donne un gain énorme sur le facteur constant pour presque aucun code. Le comptage de triangles, la clique maximum par séparation et évaluation et les produits matriciels booléens s'appuient tous là-dessus. Une structure creuse ne peut tout simplement pas faire 64 tests d'adjacence en une instruction.

L'accès à la multiplication matricielle rapide. Certains problèmes de graphes se réduisent à la multiplication de matrices et en héritent l'exposant. L'algorithme de Seidel calcule les plus courts chemins entre toutes les paires dans un graphe non orienté non pondéré en temps O(nω log n) par élévations au carré répétées de la matrice d'adjacence, où ω est l'exposant de la multiplication matricielle. Alman et Vassilevska Williams ont fait passer ω sous 2,3729 en 2021, et des raffinements ultérieurs l'ont encore légèrement abaissé. Ces bornes sont largement théoriques, car les algorithmes qui les atteignent ont des constantes qui les rendent impraticables, mais la réduction est réelle et elle n'existe que parce que le graphe est une matrice.

12. Les graphes qui changent

Toutes les structures ci-dessus ont été décrites comme si le graphe était figé. Beaucoup ne le sont pas, et le coût de mise à jour est une dimension que le tableau comparatif standard sous-estime.

Les cas nets sont les extrêmes. Une matrice d'adjacence supporte insertion et suppression en O(1), puisque les deux sont une simple écriture de case ; son problème n'a jamais été la vitesse de mise à jour. Une liste d'arêtes ajoute en O(1) mais supprime en O(m), car elle doit d'abord trouver l'arête. La CSR ne fait ni l'un ni l'autre : tout changement structurel la reconstruit entièrement en Θ(n + m).

Les listes d'adjacence se situent entre les deux et récompensent un peu de soin. Ajouter un voisin à un tableau dynamique est en O(1) amorti. Supprimer coûte O(deg(u)) pour localiser l'entrée, mais seulement O(1) pour la retirer une fois trouvée, à condition d'échanger le dernier élément avec le trou plutôt que de tout décaler. Si vous devez aussi supprimer la copie inverse dans un graphe non orienté, stockez pour chaque entrée la position de sa jumelle afin que la seconde suppression soit elle aussi en O(1) , ce que fait exactement la représentation classique des arêtes par tableaux avec indices appariés.

Trois schémas couvrent la plupart des besoins réels :

• Regrouper et reconstruire. Accumulez les mises à jour dans un petit tampon annexe, répondez aux requêtes sur la CSR plus le tampon, et reconstruisez la CSR quand le tampon dépasse un seuil. Une reconstruction coûte Θ(n + m), donc l'étaler sur Θ(m) mises à jour revient à O(1) par mise à jour dès que m vaut au moins n, ce qui couvre à peu près tout graphe réel. C'est ce que font la plupart des systèmes analytiques, et cela suffit en général.
• Les pierres tombales. Marquez les entrées supprimées au lieu de les retirer, et compactez périodiquement. Retirer l'entrée devient O(1) une fois trouvée, et aucune autre entrée ne bouge, si bien que les indices dans les tableaux de voisins restent valides. Localiser l'entrée reste en O(deg(u)) à moins que vous n'en déteniez déjà une poignée, et tout balayage ultérieur doit sauter les entrées mortes.
• Les structures vraiment dynamiques. Quand mises à jour et requêtes de connexité s'entremêlent et que les deux doivent être rapides, la littérature des structures de données a des réponses. Les link-cut trees et les Euler tour trees maintiennent une forêt changeante en temps logarithmique par opération, et la connexité dynamique générale sur des graphes quelconques se construit par-dessus, en O(log2 n) amorti par mise à jour. Elles sont considérablement plus complexes que tout ce qui précède, et vous ne devriez y recourir qu'après avoir mesuré le schéma regrouper-et-reconstruire et l'avoir trouvé insuffisant.

Un avertissement propre au matériel. Une structure rapide dans le tableau asymptotique peut être lente en pratique parce que les mises à jour la fragmentent. Une liste d'adjacence qui a grandi par un million d'insertions individuelles a ses blocs de voisins dispersés dans le tas selon l'ordre d'allocation, et tout parcours ultérieur paie cette dispersion à chaque sommet. Reconstruire périodiquement en CSR vaut souvent le coup rien que pour restaurer la localité, même quand aucune borne asymptotique ne change.

13. Graphes implicites : ne rien stocker du tout

Il existe encore une représentation, et c'est celle dont on oublie l'existence : ne pas stocker le graphe.

Un graphe implicite ou procédural est défini par une fonction. Au lieu d'une structure de données, vous fournissez une routine successeur qui, pour un sommet donné, engendre ses voisins à la demande. Rien n'est matérialisé avant d'être visité.

Ce n'est pas une technique marginale. C'est ainsi que fonctionne pour l'essentiel toute la recherche dans les espaces d'états :

• Espaces d'états de casse-têtes et de jeux. Le graphe des configurations du Rubik's cube compte environ 4,3 × 10¹⁹ sommets. Le stocker n'est pas une question d'effort d'ingénierie : un bit par état représente déjà plus de cinq exaoctets, et les arcs, à dix-huit par état, dépasseraient six zettaoctets. Sa fonction successeur, appliquer l'une des dix-huit rotations de face, tient en une douzaine de lignes de code. Les algorithmes de recherche y fonctionnent parfaitement.
• Planification et vérification de modèles. Le graphe des états accessibles d'un programme concurrent est engendré en exécutant des transitions. Les vérificateurs de modèles à états explicites ne stockent que l'ensemble visité, jamais les arêtes.
• Graphes géométriques et grilles. Une grille de recherche de chemin a une fonction successeur évidente : quatre ou huit décalages avec un test de bornes et d'obstacles. Une liste d'adjacence pour une grille de 4096 sur 4096 avec déplacement en huit directions contient 134 millions d'entrées, que reproduit exactement une fonction de deux lignes. Cela compte directement pour A* sur les grilles.

Les conséquences méritent d'être dites simplement. L'espace passe de Θ(n + m) pour le graphe à Θ(|visited|) pour la recherche, et c'est ce qui rend la technique viable. En échange, vous perdez tout ce qui exige de voir le graphe entier : vous ne pouvez ni compter les arêtes, ni calculer une distribution des degrés, ni exécuter un algorithme qui itère sur tous les sommets. Vous ne pouvez pas non plus demander les prédécesseurs à bas coût sans écrire une seconde fonction pour eux, et régénérer un voisinage coûte du calcul à chaque fois au lieu d'une lecture mémoire, ce qui peut revenir plus cher pour une région très souvent revisitée.

La représentation implicite est aussi ce qui autorise la famille des recherches à mémoire bornée. A* à approfondissement itératif ne garde que le chemin courant au lieu d'une liste ouverte, échangeant la régénération répétée contre un espace linéaire, et cela n'a de sens que parce que la régénération est possible.

14. Représentations compressées et succinctes

À l'échelle du web, même la CSR est trop grande, et deux lignes de recherche distinctes s'y attaquent.

Exploiter la structure. Le framework WebGraph de Boldi et Vigna est ici la référence standard. Il observe que si l'on ordonne les pages web par URL, les pages d'un même site finissent avec des ensembles de liens sortants presque identiques, et leurs listes de cibles sont numériquement proches. Coder chaque liste comme une référence à une liste antérieure similaire plus une petite correction, puis coder les cibles restantes par écarts avec un code de longueur variable, ramène le graphe du web à quelques bits par lien, un ordre de grandeur mieux que des identifiants bruts de 32 bits. La technique dépend entièrement d'un bon ordre des sommets, ce qui est la leçon générale : compresser des graphes est avant tout un problème de réétiquetage. Blandford, Blelloch et Kash ont démontré un résultat complémentaire pour les graphes séparables, qui incluent les graphes planaires et la plupart des maillages : un ordre fondé sur les séparateurs donne des représentations en O(n)bits qui répondent toujours à une requête d'adjacence en temps constant.

Les structures de données succinctes. Une autre tradition demande des représentations dont la taille approche le minimum théorique de l'information tout en répondant aux requêtes sans décompression. Les travaux de Jacobson en 1989 ont introduit les primitives rank et select qui rendent cela possible, et Munro et Raman les ont étendues aux arbres et à d'autres structures. Un arbre enraciné à n nœuds demande environ 2n bits plutôt que les n pointeurs que dépense un codage naïf, et la navigation reste en temps constant. Pour un graphe le problème général est plus dur, mais le cadrage est le bon : le nombre de graphes étiquetés distincts à n sommets et m arêtes donne une borne inférieure d'environ m log(n2/m) bits, et la proximité d'une représentation à cette borne est une façon sensée de la juger.

Aucune de ces deux lignes n'est à adopter par défaut. Les deux coûtent du temps de requête, les deux coûtent en complexité d'implémentation, et les deux ne valent le coup que si le graphe ne tient vraiment pas. L'étape intermédiaire pratique, celle que la plupart devraient essayer en premier, consiste simplement à renuméroter les sommets pour que les voisins aient des identifiants proches. Cela seul améliore mesurablement le comportement du cache sur une CSR ordinaire, et cela coûte un parcours en largeur.

15. Une procédure de décision

Tout ce qui précède, condensé en quelque chose d'utilisable au clavier :

1. Pouvez-vous engendrer les voisins à partir d'une règle ? Si le graphe est un espace d'états, une grille ou toute chose définie procéduralement, utilisez une représentation implicite et ne stockez que ce que vous visitez.
2. Le graphe est-il dense, ou n est-il petit ? Au-dessus d'environ 3 % de densité, ou en dessous d'environ mille sommets, utilisez une matrice d'adjacence empaquetée en bits. Vous obtenez l'adjacence en temps constant et des opérations ensemblistes parallèles par mot, et au-dessus du seuil de densité, moins de mémoire également. En dessous, avec un npetit, la matrice est la structure la plus grosse et cela n'a tout simplement aucune importance.
3. Votre algorithme ne fait-il que balayer les arêtes ? Kruskal, Bellman-Ford et tout ce qui relève du streaming veulent une liste d'arêtes. Ne construisez pas un index que vous n'interrogerez jamais.
4. Le graphe change-t-il après le chargement ? Si non, construisez une CSR. S'il change rarement, construisez une CSR avec un tampon de mises à jour et reconstruisez périodiquement. S'il change sans arrêt, utilisez des listes d'adjacence de tableaux dynamiques avec suppression par swap-and-pop.

Appliquez ensuite deux corrections. Si le graphe est orienté et que vous avez besoin des prédécesseurs, construisez aussi la structure inversée et payez la seconde copie. Si le test d'adjacence domine vraiment votre charge de travail plutôt que l'itération sur les voisins, triez les tableaux de voisins pour la recherche binaire avant de vous tourner vers des ensembles hachés.

16. Erreurs courantes

• Supposer que la liste d'adjacence a toujours raison. C'est le bon choix par défaut, pas une réponse universelle. Sur un graphe dense de 500 sommets, une matrice d'adjacence est plus petite, plus simple et plus rapide.
• Annoncer O(n + m) pour un algorithme qui tourne sur une matrice. Le parcours sur une matrice d'adjacence est en Θ(n2). La borne appartient à la représentation, pas au pseudocode.
• Oublier le facteur deux. Un graphe non orienté stocke 2m entrées dans toute structure d'adjacence, car chaque arête figure dans les listes de ses deux extrémités. Dimensionner un tableau à m est un débordement de tampon, pas un problème de performance.
• Utiliser un tableau d'offsets en 32 bits. Les offsets d'une CSR indexent un tableau de longueur 2m. Au-delà d'environ deux milliards d'arcs orientés, cela déborde silencieusement et corrompt toute recherche de voisins. Les cibles peuvent rester en 32 bits tant que n est sous les quatre milliards ; les offsets, non.
• Stocker zéro pour une arête pondérée absente. Zéro est un poids valide. Utilisez une sentinelle ∞, ou stockez la présence séparément, ou utilisez une structure creuse où l'absence est simplement une entrée absente.
• Construire une CSR par tri. La construction par tri par comptage est en O(n + m). Trier d'abord la liste d'arêtes est en O(m log m) et inutile, même si c'est un raccourci raisonnable si vous vouliez de toute façon des tableaux de voisins triés.
• Ne pas stocker le graphe inverse. Les requêtes de prédécesseurs sur une CSR orientée exigent un balayage complet du tableau des cibles. Si vous en faites, construisez la structure transposée une fois pour toutes.
• Choisir une représentation sur la seule asymptotique. Une liste d'adjacence et une CSR sont toutes deux en Θ(n + m), et la CSR est couramment plusieurs fois plus rapide grâce à la localité. Les facteurs constants sur du code de graphes limité par la mémoire ne sont pas une erreur d'arrondi.
• Mal gérer les boucles dans le compte des degrés. Une boucle ajoute 2 au degré dans un graphe non orienté. Quoi que vous décidiez de stocker dans la structure d'adjacence, faites en sorte que la fonction de degré s'y conforme.

17. Glossaire

19. Références

Sources des définitions, bornes de complexité et techniques ci-dessus, avec les ouvrages de référence où ce matériel est développé, classées par ordre chronologique.

1. Arlazarov, V. L., Dinic, E. A., Kronrod, M. A. et Faradzev, I. A. (1970). “On economical construction of the transitive closure of a directed graph.” Soviet Mathematics Doklady, 11, 1209–1210.
2. Gustavson, F. G. (1972). “Some basic techniques for solving sparse systems of linear equations.” Dans Sparse Matrices and Their Applications, Plenum Press, 41–52.
3. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
4. Hopcroft, J. et Tarjan, R. E. (1973). “Algorithm 447: efficient algorithms for graph manipulation.” Communications of the ACM, 16(6), 372–378.
5. Aho, A. V., Hopcroft, J. E. et Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.
6. Duff, I. S., Erisman, A. M. et Reid, J. K. (1986). Direct Methods for Sparse Matrices. Oxford University Press.
7. Jacobson, G. (1989). “Space-efficient static trees and graphs.” Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 549–554.
8. Seidel, R. (1995). “On the all-pairs-shortest-path problem in unweighted undirected graphs.” Journal of Computer and System Sciences, 51(3), 400–403.
9. Chung, F. R. K. (1997). Spectral Graph Theory. CBMS Regional Conference Series in Mathematics 92, American Mathematical Society.
10. Munro, J. I. et Raman, V. (2001). “Succinct representation of balanced parentheses and static trees.” SIAM Journal on Computing, 31(3), 762–776.
11. Blandford, D. K., Blelloch, G. E. et Kash, I. A. (2003). “Compact representations of separable graphs.” Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 679–688.
12. Boldi, P. et Vigna, S. (2004). “The WebGraph framework I: compression techniques.” Proceedings of the 13th International World Wide Web Conference (WWW), 595–602.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition, chapitre 22. MIT Press.
14. Kepner, J. et Gilbert, J., éditeurs (2011). Graph Algorithms in the Language of Linear Algebra. Society for Industrial and Applied Mathematics.
15. Diestel, R. (2017). Graph Theory, 5e édition. Springer, Graduate Texts in Mathematics 173.
16. Alman, J. et Vassilevska Williams, V. (2021). “A refined laser method and faster matrix multiplication.” Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 522–539.