À la recherche du type de données disparu

À la recherche du type de données manquant

• Un graphe est un ensemble de nœuds reliés par des flèches (arêtes).
• Les nœuds et les arêtes peuvent contenir des données.
• En génie logiciel, les graphes existent sous de nombreuses formes : dépendances de paquets, liens Internet, espace d’états d’un logiciel, bases de données relationnelles, listes chaînées, arbres binaires, tables de hachage, etc.
• Dans la logique métier aussi, les graphes sont utilisés pour les références entre citations, les réseaux de transport, les réseaux sociaux, etc.
• Plus on fait du développement logiciel longtemps, plus il est probable de rencontrer des graphes partout.

Réflexions sur l’usage des graphes

• Les graphes sont utiles, mais les utiliser dans du vrai code reste contraignant.
• La plupart des langages grand public ne prennent pas en charge les graphes comme type intégré, c’est rare même dans les bibliothèques standard, et il n’existe pas tant de bibliothèques tierces robustes.
• Il faut souvent implémenter les graphes soi-même.
• Il existe un écart entre la fréquence à laquelle les ingénieurs logiciels peuvent avoir besoin de graphes et le niveau de support offert par l’écosystème de programmation.

Pourquoi il n’existe pas de type graphe

Trop de choix de conception

• Il existe de nombreux types de graphes : orientés ou non orientés, graphes simples ou multigraphes, hypergraphes, ubergraphes, etc.
• Pour chaque type, il faut décider s’il faut attribuer des ID aux nœuds et aux arêtes, ainsi que quelles données y stocker.
• Une bibliothèque de graphes parfaite couvrant toutes les possibilités demanderait énormément de temps.
• Les performances des algorithmes de graphes sont importantes, et les cas particuliers comptent.
• Les algorithmes de graphes sont difficiles à implémenter correctement.

Trop de choix d’implémentation

• Même en supposant qu’on ne veuille prendre en charge qu’un simple graphe orienté, il existe plusieurs façons de représenter un graphe en interne.
• Il existe différents modes de stockage : liste d’arêtes, liste d’adjacence, matrice d’adjacence, ensemble de structures, etc.
• Les différentes opérations sur les graphes ont des caractéristiques de performance différentes selon la représentation choisie.
• Selon qu’un graphe est clairsemé ou dense, la représentation interne optimale change.
• Implémenter des données de nœuds, des données d’arêtes, ainsi que différents types de nœuds et d’arêtes rend la situation encore plus complexe.

Les performances sont trop importantes

• Beaucoup d’algorithmes de graphes relèvent de problèmes NP-complets, voire plus difficiles.
• Les graphes peuvent devenir très grands, et les performances varient fortement selon la représentation et les détails d’implémentation des algorithmes.
• Il faut disposer d’un contrôle important sur la représentation des données et les algorithmes.

Le constat partagé

• La variété des types de graphes, des représentations, des algorithmes, leur sensibilité aux performances, ainsi que l’exécution d’algorithmes coûteux sur de grands graphes expliquent pourquoi leur prise en charge n’est pas généralisée.
• Cela explique pourquoi les langages ne prennent pas en charge les graphes dans leur bibliothèque standard.
• Cela explique aussi pourquoi les programmeurs évitent les bibliothèques tierces de graphes.
• Comme l’usage des graphes est difficile, on préfère souvent éviter de penser en termes de graphes sauf dans des situations extrêmes.

L’avis de GN⁺

• Cet article apporte un éclairage sur les raisons pour lesquelles les graphes ne se sont pas imposés comme type de données fondamental dans les langages et bibliothèques de programmation.
• La théorie des graphes est un domaine important de l’informatique, avec des applications dans les algorithmes, l’analyse de réseaux, les bases de données et bien d’autres domaines.
• Pour utiliser efficacement les graphes, l’optimisation des performances et le choix d’une structure de données adaptée sont essentiels.
• Parmi les bibliothèques tierces, on peut citer NetworkX, Boost Graph Library et Graph-tool, qui peuvent servir à résoudre divers problèmes liés aux graphes.
• Lorsqu’on utilise des graphes, il est important de choisir le type de graphe et l’algorithme adaptés aux caractéristiques du problème, car cela a un impact direct sur les performances du système.

[GN⁺]

Commentaires sur Hacker News

• Graphviz possède sa propre bibliothèque de graphes, qui n’est pas utilisée dans d’autres projets. Cette bibliothèque a des avantages et des inconvénients.

  • Forts de cette expérience, ils ont souffert de leur propre « syndrome du deuxième système ».
  • Ils ont décidé qu’une bibliothèque de graphes devait être modulaire, sûre du point de vue des types et efficace. Cela ressemble peut-être à une variante de « bon, rapide et bon marché — choisissez-en deux ».
  • Modulaire signifie qu’ils voulaient écrire un ensemble de bibliothèques d’algorithmes de graphes développées et compilées indépendamment.
  • La sûreté des types signifie qu’ils voulaient détecter les erreurs de programmation à la compilation, ou au plus tard à l’édition des liens. Ils ne voulaient pas d’erreurs à l’exécution.
  • L’efficacité signifie que l’accès aux propriétés du graphe doit être aussi peu coûteux que l’accès à un champ de structure C.
  • On peut débattre de la valeur de ces objectifs, mais c’est ce qu’ils voulaient. Comme des créateurs célèbres du C++ se trouvaient dans leur labo, ils espéraient pouvoir obtenir de l’aide, et ils ont décidé de redonner une chance au C++.
  • Gordon Woodhull, un ancien stagiaire, était un programmeur exceptionnel, et il a implémenté ce type de bibliothèque de graphes en C++ à base de templates. Elle a été publiée via sourceforge sur https://www.dynagraph.org/.
  • Comme d’autres n’étaient pas sûrs de pouvoir comprendre le fonctionnement du code, ils ont fait une revue de code avec de célèbres inventeurs du C++. Ils ont compris qu’ils avaient peut-être franchi le précipice de la complexité.
  • Ce n’était pas la faute de Gordon, et il a continué à persévérer et a aussi réussi à travailler sur la mise en page dynamique de graphes dans Microsoft OLE. Avec le recul, c’était peut-être leur propre projet Xanadu.
  • Pendant qu’ils étaient absorbés par cela, beaucoup d’autres solutions sont apparues, comme Gephi (Java) et NetworkX et NetworKit (Python).
  • John Ellson est un ingénieur logiciel très talentueux qui a écrit une partie de Graphviz, et il a relancé l’effort principal.

• Si vous codez en .NET, vous devriez essayer Arborescence, une petite bibliothèque de graphes peu riche en fonctionnalités.

  • Je pense qu’elle offre une bonne séparation entre abstractions, algorithmes et structures de données.
  • Les utilisateurs peuvent employer des arêtes avec leurs propres ID, ou des graphes implicites déployés à la volée.
  • On peut utiliser à la fois des interfaces d’adjacence (voisins sortants) et d’incidence (arêtes sortantes + tête).
  • La bibliothèque n’impose pas de type d’arête, mais fournit comme utilitaire une structure de base en paire queue-tête.

• Un graphe n’est ni une structure de données ni un type de données, c’est une abstraction.

  • Fondamentalement, tout ce qu’il faut pour définir un graphe, c’est un ensemble de sommets et une fonction de voisinage.
  • Tout le reste relève de contraintes propres à chaque cas.
  • Si l’on considère les hypergraphes, un graphe n’est qu’un cas particulier.
  • Du point de vue des bases de données, un graphe est un problème d’optimisation de requêtes et d’indexation.

• On m’a souvent demandé pourquoi il n’existe pas de type de données graphe intégré aux langages de programmation.

  • Je suis heureux de pouvoir désormais renvoyer vers des analyses plus approfondies comme cet article.

• L’obstacle central est le suivant :

  • Pour des problèmes de graphes simples et petits, coder une liste d’adjacence sous forme de vecteurs de vecteurs est assez facile.
  • Pour des problèmes de graphes complexes et énormes, il n’y a aucun moyen d’obtenir de bonnes performances sans personnaliser une implémentation du graphe adaptée au problème.
  • Il n’est pas clair quel type de support au niveau du langage serait utile.

• Cet article répond en grande partie à la question de savoir pourquoi les algorithmes de graphes ne sont pas mieux pris en charge dans les langages de programmation.

  • Si l’on regarde plus largement la prise en charge des graphes, cela amène des questions plus vastes, comme pourquoi les OGM ne sont pas aussi populaires que les ORM, ou pourquoi JSON est plus largement utilisé que RDF.
  • En fin de compte, pour des raisons historiques et à cause de la complexité des graphes, cela ne passe pas bien à l’échelle parmi les développeurs.

• Les outils de dessin de graphes sont eux aussi très décevants.

  • Avec des graphes de plus de 500 nœuds, le résultat devient difficile à comprendre ou trop complexe.
  • Il manque des fonctionnalités pour organiser automatiquement les graphes en structures hiérarchiques et fournir une bonne interface pour les explorer.

• Cet article est vraiment génial.

  • Concernant l’observation centrale selon laquelle « il y a trop de choix d’implémentation », en réalité ce n’est pas le cas.
  • En pratique, une bibliothèque peut implémenter toutes les représentations de graphes pertinentes.
  • On peut adapter les algorithmes à la représentation et convertir une représentation en une autre.

• Electric Clojure utilise Clojure lui-même (les s-expressions) comme syntaxe d’écriture de graphes.

  • Un DSL d’écriture de graphes doit exprimer la portée, le contrôle de flux et l’abstraction, ce qui revient essentiellement à un langage de programmation.

• Il existe un autre type de données utile, comme les tables (par exemple les tables dans une base de données).

  • Il y aurait un progrès dans les langages de programmation si le compilateur choisissait l’implémentation de la structure de données.
  • On utiliserait des structures abstraites (séquence, map, set, table, graphe, etc.) et le compilateur choisirait une implémentation concrète en fonction du profil du programme.