À la recherche du type de données disparu
(hillelwayne.com)- Les graphes sont partout dans le logiciel — dépendances, liens web, espace d’états des model checkers, clés étrangères des bases de données relationnelles — mais les langages de programmation grand public n’ont presque jamais de type intégré ni de prise en charge en bibliothèque standard
- La première raison pour laquelle il est difficile de créer un type graphe intégré est qu’il existe de nombreux types de graphes — orientés ou non orientés, simples ou multigraphes, hypergraphes — et que certaines propriétés changent fortement le choix des algorithmes et leurs performances
- Chaque mode de représentation — liste d’arêtes, liste d’adjacence, matrice d’adjacence, structures à références — a des caractéristiques mémoire et de performance de consultation différentes, ce qui rend difficile de satisfaire tous les cas d’usage avec une seule représentation générique
- Les algorithmes de graphes sont difficiles à implémenter et s’exécutent souvent sur de grandes entrées ; comme le montrent les cas de Nosey Parker et Gecode, une représentation et un parcours adaptés au problème peuvent devenir plus importants qu’une bibliothèque générique
- Les graphes sont rares dans les bibliothèques standard parce que les compromis entre types, représentations, algorithmes et performances, ainsi que la charge de maintenance, sont importants ; les bibliothèques tierces peuvent elles aussi être limitées ou lentes
Les graphes sont courants, mais le support des langages est insuffisant
- Un graphe est composé de nœuds et d’arêtes, et les nœuds comme les arêtes peuvent contenir des données
- En ingénierie logicielle, les graphes apparaissent sous de nombreuses formes
- Les dépendances de paquets et les imports de modules forment des graphes orientés
- Internet est un graphe de liens entre pages web
- Un model checker explore l’espace d’états de toutes les configurations possibles : les nœuds sont les états et les arêtes les transitions valides
- Une base de données relationnelle peut être vue comme des enregistrements en tant que nœuds et des clés étrangères en tant qu’arêtes
- Un graphe peut être vu comme une généralisation d’une liste chaînée, d’un arbre binaire ou d’une table de hachage
- Les graphes apparaissent aussi souvent dans la logique métier, par exemple les relations de citation entre articles, les itinéraires de réseaux de transport ou les connexions de réseaux sociaux
- Les graphes sont fréquemment nécessaires, mais la plupart des langages grand public ne fournissent pas de graphe comme type intégré, et il est rare qu’ils en incluent dans leur bibliothèque standard
- Dans beaucoup d’écosystèmes, il manque aussi des bibliothèques tierces de graphes robustes, ce qui oblige souvent à les implémenter soi-même
Concevoir un type graphe implique trop de choix
- Outre les graphes orientés et non orientés, il existe plusieurs variantes de graphes
- Les graphes simples, avec au plus une arête entre deux nœuds, et les multigraphes, qui autorisent plusieurs arêtes
- Les hypergraphes, où une arête peut relier trois nœuds ou plus
- Les ubergraphes, où une arête peut pointer vers d’autres arêtes
- Chaque variante entraîne des décisions de conception supplémentaires
- Il faut décider s’il faut attribuer un ID aux arêtes aussi, ou seulement aux nœuds
- Il faut aussi décider quelles données stocker dans les nœuds et les arêtes
- On pourrait fournir tous les graphes sous forme d’un type générique, du genre « hyper-uber-multigraphe orienté », et laisser l’utilisateur le restreindre, mais deux problèmes apparaissent aussitôt
- L’interface change, par exemple selon que le résultat d’une opération est une valeur unique ou une liste
- Si l’on ne peut pas exploiter les propriétés particulières d’un graphe, les performances des algorithmes se dégradent
- Par exemple, pour le couplage de poids maximal, savoir qu’un graphe est biparti permet d’utiliser un algorithme rapide, tandis qu’un graphe général nécessite un algorithme plus lent et plus générique
- Étant donné un problème P, un graphe G et des algorithmes A, B et C, se pose aussi le problème du dispatch d’algorithmes : choisir quel algorithme exécuter
- Une bibliothèque de graphes parfaite devrait prendre en charge de nombreux types de graphes, mais cela laisse d’autant moins de temps pour implémenter les algorithmes que les utilisateurs veulent réellement
- Les algorithmes de graphes sont difficiles à implémenter
- L’algorithme
find_shortest_pathécrit par le créateur de Python a ensuite été corrigé cinq fois - Nicole affirme que toutes les implémentations de PageRank qu’elle a comparées étaient incorrectes
- NetworkX fournit environ 500 algorithmes de graphes, et le seul code des algorithmes représente près de 60 000 lignes
- L’ensemble de la bibliothèque standard de Python compte environ 300 paquets et moins de 600 000 lignes
- L’algorithme
- Les mainteneurs d’une bibliothèque standard doivent décider quels types de graphes inclure, quels cas topologiques particuliers traiter et quels algorithmes fournir, ce qui représente une lourde charge de maintenance
- Même Python, pourtant connu pour son approche « batteries included », est dans une dynamique de suppression de 20 modules de la bibliothèque standard avec PEP 594
Il est aussi difficile de choisir une représentation unique pour les graphes
- Même si l’on ne considère que le graphe orienté le plus simple, plusieurs représentations internes sont possibles
- Liste d’arêtes :
[[a, b], [b, c], [c, a], [c, b]] - Liste d’adjacence :
[[b], [c], [a, b]] - Matrice d’adjacence :
[0 1 0; 0 0 1; 1 1 0] - Ensemble de structures se référençant mutuellement
- Liste d’arêtes :
- Les performances des opérations dépendent de la représentation
- Si l’on représente par une matrice d’adjacence un graphe de 100 nœuds et 200 arêtes, la matrice 100×100 contient 200 valeurs à 1 et 9 800 valeurs à 0
- Le même graphe représenté sous forme de liste d’arêtes ne nécessite que 200 paires de nœuds
- Selon le langage et le niveau d’optimisation, l’écart mémoire peut dépasser un facteur 20
- À l’inverse, le résultat change pour un graphe de 100 nœuds et 8 000 arêtes lorsqu’on cherche une arête entre les nœuds 0 et 93
- Une matrice d’adjacence permet une consultation en O(1) avec
graph[0][93] - Une liste d’arêtes doit parcourir 8 000 arêtes, ce qui prend O(|edge|)
- Une matrice d’adjacence permet une consultation en O(1) avec
- Un graphe avec peu d’arêtes est un graphe creux ; un graphe qui contient presque toutes les arêtes possibles est un graphe dense
- Un programme qui construit un graphe à partir de données externes peut commencer avec un graphe creux puis devenir dense ensuite ; il n’existe donc pas de « toujours bon choix » pour la représentation interne
- Si l’on prend aussi en charge les données de nœuds, les données d’arêtes et plusieurs types de nœuds et d’arêtes, la complexité d’implémentation augmente encore
- Les bibliothèques tierces choisissent généralement l’une de deux directions
- Fournir un type unique riche couvrant tous les cas d’usage, au prix de l’efficacité
- Fournir des types de graphes séparés par représentation, et laisser à l’utilisateur la gestion des données de nœuds et d’arêtes
Les compromis illustrés par NetworkX et Petgraph
- NetworkX stocke les graphes sous forme de dictionnaires de dictionnaires de dictionnaires afin de permettre d’attacher des données arbitraires aux nœuds et aux arêtes
- Il fournit des fonctions de conversion vers d’autres représentations, mais ne permet pas de travailler directement avec ces représentations elles-mêmes
- Petgraph, la principale bibliothèque de graphes de Rust, fournit des types adaptés aux cas d’usage, comme
graph,graphmapetmatrix_graph - Bradford a utilisé Petgraph dans Nosey Parker, un outil de sécurité qui recherche des secrets dans l’historique complet de dépôts git
- Le graphe de benchmark est CPython, avec 250 000 commits et 1 300 000 objets
- Comme chaque nœud de commit n’a que quelques arêtes, il a choisi une liste d’adjacence
- Prendre en charge plusieurs représentations augmente le coût d’ajout d’algorithmes
- Écrire un algorithme distinct pour chaque représentation multiplie la charge de maintenance par 3 ou 4
- L’écrire au-dessus d’une abstraction générique sur des types polymorphes réduit les performances
- Une personne interrogée estime qu’un algorithme de graphe écrit sur mesure peut être plus de 20 fois plus rapide qu’un algorithme générique
Les contraintes de performance sont le problème central des bibliothèques de graphes
- Beaucoup d’algorithmes de graphes relèvent de problèmes NP-complets, voire plus difficiles
- Parmi les 21 problèmes NP-complets canoniques de Karp, 14 sont des problèmes de graphes
- Les problèmes de graphes peuvent s’exécuter sur de très grandes entrées, si bien que la représentation et les détails d’implémentation déterminent leur faisabilité
- Dans Nosey Parker, Bradford devait parcourir le graphe d’objets pour reconstruire un instantané du système de fichiers à chaque commit
- Les quatre walkers de graphes de Petgraph ne passaient pas à l’échelle pour ce cas d’usage
- Il a conçu à la volée un algorithme de parcours de graphe « semi-novel », réduisant l’usage mémoire d’un facteur 1 000
- Zayenz cite le taquin 15 comme exemple où le graphe est trop grand pour être traité dans son intégralité
- La recherche de solution consiste à exécuter une recherche A* dans l’espace d’états
- L’espace d’états contient plus de 20 000 milliards d’états
- Générer tous les nœuds signifie avoir déjà échoué
- Dans un projet de recherche auquel Zayenz a participé pour ajouter des graphes au solveur de contraintes Gecode, un type de graphe générique ne pouvait pas rivaliser avec le choix d’une représentation adaptée au problème
- Les bases de données orientées graphe sont elles aussi conçues pour exécuter des algorithmes de graphes complexes, mais les problèmes de performance subsistent
- Selon Nicole, si l’on ne limite pas la profondeur d’un parcours, on finit par visiter tout le graphe
- Même une recherche en profondeur du type « aller à trois niveaux et trouver un chemin s’il existe » visite beaucoup de données
- Dans ses missions de conseil sur les performances de requêtes de graphes, Nicole mène principalement des migrations hors des bases de données orientées graphe
- Dans un projet, une seule computation a été conservée telle quelle et le reste a été réécrit sous forme de procédures MapReduce
- C’était plus difficile à comprendre, mais cela pouvait réellement se terminer pendant la nuit
Pourquoi les graphes sont rares dans les bibliothèques standard
- La rareté d’une prise en charge étendue des graphes tient à la combinaison de plusieurs facteurs
- Il existe beaucoup de types de graphes
- Chaque type de graphe peut être représenté de nombreuses façons
- Il existe beaucoup de types d’algorithmes de graphes
- Les performances des algorithmes sont sensibles à la représentation et aux détails d’implémentation
- Les gens exécutent des algorithmes très coûteux sur de très grands graphes
- Une bibliothèque standard de langage devrait assumer trop de décisions de conception, de compromis et de charge de maintenance
- Les programmeurs ont aussi des raisons d’éviter les bibliothèques tierces de graphes
- La bibliothèque peut être trop limitée
- Une bibliothèque générique peut ne pas satisfaire les exigences de performance
- Les graphes sont utiles pour analyser les systèmes, mais à l’étape de l’implémentation, il faut souvent contrôler directement la représentation des données et le choix des algorithmes
Annexe : langages fournissant un type graphe et outils associés
- Un langage de requête de graphes (GQL) joue, pour les bases de données orientées graphe, un rôle équivalent à celui de SQL
- GraphQL n’est pas un langage de requête de graphes ; son nom vient de son lien avec Facebook Graph Search
- La principale différence entre GQL et SQL est que les relations, c’est-à-dire les « jointures », sont des entités de première classe
- Dans un jeu de données de films et de personnes, SQL implémente les relations « joue dans », « réalise » et « produit » chacune sous forme de table many-to-many
- Dans SPARQL, les relations sont des arêtes, ce qui permet de requêter facilement « les personnes ayant eu n’importe quel rôle dans le film Y, et leur rôle »
- GQL peut aussi prendre en charge des manipulations d’arêtes comme l’inversion, la composition et la clôture transitive
- SPARQL ne permet pas de récupérer la longueur d’un chemin ni d’effectuer des calculs sur un chemin, par exemple collecter la chaîne de films reliant deux acteurs
- Un GQL qui prend cela en charge devient beaucoup plus complexe
- Le langage de spécification formelle Alloy dispose, pour le type de données relation, de primitives de parcours de graphes utiles, ce qui rend la manipulation de représentations de graphes plus facile que dans les langages de programmation généralistes
- Toutefois, ces primitives reposent sur des arêtes étiquetées et peuvent ne pas convenir à d’autres représentations de graphes
- Python a ajouté graphlib en 2020
- Il n’a pas d’autre méthode que
TopologicalSorter - Le graphe n’est accepté que sous forme de dictionnaire de nœuds
- Un graphe
a -> best représenté par un dictionnaire en sens inverse, comme{b: [a]}
- Il n’a pas d’autre méthode que
- En 2023,
graphlibn’était pas utilisé en interne par CPython- Moins de 900 fichiers sur GitHub référencent
graphlib zoneinfo, ajouté la même année, apparaît dans plus de 6 000 fichiers- L’expression
def topological_sort(apparaît dans 4 000 fichiers - Les tris topologiques implémentés directement utilisent souvent des représentations de graphes différentes de graphlib, ce qui rend leur conversion difficile
- Moins de 900 fichiers sur GitHub référencent
- Parmi les autres bibliothèques standard proposant un type graphe, on trouve Erlang et SWI-Prolog
- Il existe aussi des langages de programmation où « tout est graphe »
- Les langages de logiciels mathématiques comme Mathematica, MATLAB et Maple disposent eux aussi de bibliothèques de graphes sous une forme ou une autre
- Dans une mise à jour du 18 mars 2024, certains commentaires sur l’article ont été rassemblés sur une page séparée
1 commentaires
Avis sur Hacker News
Graphviz possède sa propre bibliothèque graphique de base, que les autres projets n’utilisent pas, avec des avantages et des inconvénients.
Sur la base de cette expérience, nous avons nous aussi traversé un classique syndrome du deuxième système. Nous voulions créer une bibliothèque de graphes modulaire, type-safe et efficace, mais au final c’était probablement une variante de « bon, rapide et pas cher — choisissez-en deux ».
Par modulaire, nous voulions dire que nous souhaitions pouvoir développer et compiler indépendamment un ensemble de bibliothèques d’algorithmes de graphes ; par type-safe, que nous voulions détecter les erreurs de programmation à la compilation, ou au plus tard à l’édition de liens, plutôt que d’avoir des erreurs à l’exécution du type « le nœud n’a pas d’attribut color ».
Par efficace, nous voulions dire que le coût d’accès aux propriétés du graphe devait être aussi faible que l’accès à un champ d’une struct C, et nous ne voulions pas transporter une table de hachage externe ni faire beaucoup de conversions de chaînes.
On peut débattre du fait que ces objectifs valaient leur coût ou avaient du sens, mais c’est ce que nous voulions à l’époque. Le labo comptait des créateurs célèbres de C++, et nous étions aussi prêts à redonner sa chance à C++.
Gordon Woodhull, d’abord stagiaire puis resté travailler avec nous, était un excellent programmeur et a écrit une implémentation de ce type de bibliothèque de graphes en C++ avec des templates. Le code source est également disponible sur https://www.dynagraph.org/.
Les autres n’étaient pas certains de pouvoir un jour comprendre comment ce code fonctionnait, alors nous avons fait une revue de code avec des inventeurs célèbres de C++ ; après d’innombrables écrans de code et beaucoup de silence, la conclusion a été que « ça devrait probablement marcher ». À ce moment-là, nous avons compris que nous avions peut-être déjà franchi un mur de complexité.
Les erreurs de templates à la compilation remplissaient tout l’écran pour une seule erreur et déversaient des détails que seuls des inventeurs de C++ pouvaient aimer. La faute nous revenait, et Gordon a continué à pousser le projet jusqu’à faire fonctionner le layout dynamique de graphes même dans Microsoft OLE.
Avec le recul, c’était notre propre Project Xanadu, et pendant que nous nous y perdions, des choses comme Gephi (Java), NetworkX et NetworKit (Python) sont apparues. John Ellson, excellent ingénieur logiciel qui a écrit une partie de Graphviz, a relancé le travail principal.
Ayant beaucoup travaillé avec des graphes, on m’a posé un nombre incalculable de fois la question : « pourquoi les langages de programmation n’ont-ils pas de type de données graphe intégré ? »
Je suis content de ne plus avoir seulement à demander aux gens de me croire quand je dis que « c’est vraiment difficile à bien faire » : je peux maintenant les renvoyer à une analyse plus approfondie comme cet article.
Tout ce que la plupart des langages fournissent comme types structurels, ce sont des tableaux statiques, des tableaux dynamiques et des listes chaînées. Des choses comme les arbres binaires de recherche ou les tables de hachage sont des abstractions sémantiques qui masquent une partie des capacités de la structure sous-jacente, pas des représentations structurelles pures.
La partie de l’article sur le fait qu’« il y a trop de choix d’implémentation » dit la même chose. Puis j’ai vu Petgraph [0] et, pour la première fois, j’ai vraiment examiné une bibliothèque de graphes générique ; c’était assez intéressant, mais j’ai tout de même continué à implémenter les graphes au niveau du domaine.
[0] https://github.com/petgraph/petgraph
https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
Presque tous les langages fournissent une hash map et, même si une implémentation maison peut être plus rapide dans certains cas, l’implémentation par défaut fonctionne généralement bien. Avec les graphes, c’est difficile à obtenir ; si c’était possible, il faudrait peut-être proposer plusieurs types de graphes.
Au passage, HashMap de Java est un peu particulier en ce qu’il permet d’ajuster le facteur de charge, contrairement à la plupart des autres langages.
Ce que les gens veulent, ce n’est pas tant un type graphe en soi que des outils pour parcourir les graphes.
Je pense qu’un graphe est plutôt une abstraction qu’une structure de données ou un type de données.
Fondamentalement, tout ce qu’il faut pour définir un graphe, c’est un ensemble de sommets v \in V et une fonction Neighbors(v), et cela suffit vraiment pour la plupart des algorithmes de graphes de base.
Le reste relève de contraintes propres à chaque cas : savoir si A->B implique B->A, si l’ensemble de nœuds peut être partitionné sous certaines contraintes, s’il y a des couleurs ou des labels, etc.
En généralisant davantage, on arrive aux hypergraphes ; dans ce cas, il suffit d’un ensemble de sommets et d’un ensemble d’ensembles de sommets. Ils peuvent être représentés de très nombreuses façons selon ce qui vous intéresse, et les graphes ordinaires ne sont qu’un cas particulier.
Du point de vue des bases de données, on peut aussi voir cela comme un problème d’optimisation de requêtes et d’indexation. Selon les questions que l’on veut poser au graphe, la représentation qui permet d’y répondre au mieux change. De même qu’il n’existe pas une seule façon de représenter l’abstraction « table », il n’existe pas non plus une seule façon de représenter « graphe ».
Ils se situent au même niveau d’abstraction que les nombres purs. On peut dire qu’il existe des bibliothèques « numériques » utiles, comme il existe des bibliothèques « graphiques » utiles, mais il n’existe pas vraiment de bibliothèque de « nombres » ou de « graphes ». Ces concepts sont trop abstraits pour en faire une API.
Les fichiers seraient les sommets, et les répertoires des ensembles de sommets pouvant être imbriqués.
Les obstacles principaux sont au nombre de deux
Pour les problèmes de graphes simples et de petite taille, il est assez facile d’écrire soi-même une liste d’adjacence sous forme de vecteur de vecteurs ; pour les problèmes de graphes complexes et énormes, il faut nécessairement adapter l’implémentation du graphe aux détails du problème à résoudre pour obtenir de bonnes performances
Il est donc difficile de voir quel support du langage pourrait aider. À moins d’avoir un compilateur ultra-intelligent capable d’analyser le code et de déterminer ce qui est optimal — liste d’adjacence, matrice, tableau 3D, etc. — ce serait compliqué. On ne verra probablement pas ce type d’optimisation dans les compilateurs avant un bon moment
C’est un autre exemple du phénomène observé par Stroustrup. Nous savons bien partager du code pour les petites choses comme les vecteurs, et pour les grandes comme les systèmes d’exploitation, mais nous partageons mal les problèmes de taille intermédiaire
Au sein d’un même écosystème de langage, l’API des vecteurs est petite, ce qui semble faciliter le partage. Les systèmes d’exploitation ont une API relativement petite par rapport à leur complexité interne, et il en va de même pour les bibliothèques de calcul numérique, ce qui les rend faciles à partager
En revanche, plus on cherche à personnaliser des choses comme des structures de données complexes, plus l’API devient complexe et plus le partage devient difficile. Au final, la possibilité de partage semble dépendre de la surface de ce qui est partagé, c’est-à-dire de la taille relative de son API
Electric Clojure utilise les s-expressions de Clojure lui-même comme syntaxe d’écriture de graphes, et matérialise via des macros le flux de données d’un système client/serveur réactif
Ici, le cas d’usage est une interface utilisateur full-stack, mais l’idée peut être généralisée. https://github.com/hyperfiddle/electric J’en suis le fondateur
À la question « où sont passés les types de graphes ? », je pense que la réponse est que le DSL d’écriture de graphes doit exprimer la portée, le flux de contrôle et l’abstraction ; il devient alors, de fait, isomorphe à un langage de programmation libéré du modèle d’évaluation. En Python et TypeScript, il est assez difficile d’y intégrer un langage de programmation complet
L’article de blog « Four problems preventing visual flowchart programming from expressing web applications » mérite aussi d’être consulté
https://www.dustingetz.com/#/page/four%20problems%20preventi...
Cet article répond surtout à la question « pourquoi les langages de programmation ne prennent-ils pas mieux en charge les algorithmes de graphes ? », et semble davantage se concentrer sur le traitement de graphes “big data” que sur la prise en charge générale des graphes
Si l’on considère la prise en charge des graphes dans son ensemble, cela inclut aussi des questions plus larges comme « pourquoi les OGM (Object Graph Mappers) ne sont-ils pas aussi populaires que les ORM ? » ou « pourquoi JSON est-il largement utilisé alors que RDF et d’autres sérialisations de graphes de bas niveau ne le sont pas ? »
Au bout du compte, je pense que les raisons historiques pèsent lourd. RDF est arrivé un peu trop tôt, n’a pas correctement évolué et a accumulé un écosystème de standards académiques et d’implémentations épouvantables. À cela s’ajoute le fait que les graphes sont intrinsèquement un peu plus complexes à implémenter et à apprendre, ce qui passe mal à l’échelle pour beaucoup de développeurs
Je n’accorderais pas trop d’importance à la partie « Graph Querying Language » de l’article. Certains passages se lisent comme du discours marketing écrit par un utilisateur enthousiaste de Neo4J ou de SPARQL qui n’aurait jamais réellement construit de produit
L’article dit que « la principale différence entre tous les GQL et SQL est la jointure, c’est-à-dire le fait que les relations soient des entités de première classe », mais en SQL aussi les jointures sont des entités de première classe. Il existe même un mot-clé JOIN
Si l’on descend à un niveau plus bas dans les langages de requête de graphes et qu’on regarde les plans de requête, il n’y a pas beaucoup de différence significative avec les requêtes basées sur SQL. Le fait que la standardisation de GQL[0] soit menée comme une extension de SQL en est la preuve
SPARQL est simple lorsqu’on a besoin de parcours de chemins exacts, mais dès qu’on essaie de faire quelque chose d’un peu plus complexe, du genre de ce qu’on ferait dans le backend d’une webapp, on tombe vite sur des pièges qui font accidentellement exploser tout le jeu de résultats, comme les jointures avec des valeurs non liées
[0]: https://en.wikipedia.org/wiki/Graph_Query_Language
Par exemple, les classes de types de Haskell ne sont pas de première classe, et dans la plupart des langages de programmation, le flux de contrôle ne l’est pas non plus
Simplement, elles n’offrent pas de raccourci syntaxique ; les langages de requête de graphes se concentrent essentiellement sur l’ajout de ce raccourci
Les outils de dessin de graphes sont eux aussi assez décevants. Ils fonctionnent bien sur de petits graphes, mais dès qu’on dépasse environ 500 nœuds, la sortie devient totalement incompréhensible ou très difficile à lire
Il leur manque la capacité d’organiser automatiquement le graphe en structure hiérarchique et de fournir une interface agréable pour l’explorer. Étant donné que nous sommes habitués à voir, dans une certaine mesure, tout ce qui nous entoure sous forme de hiérarchie, il me semble que le même type de problème devrait être résolu lorsqu’on conçoit un type de données graphe généraliste
Cela pourrait devoir être implémenté au niveau du compilateur, avec des algorithmes de graphe généralistes qui s’adaptent à la hiérarchie de structures générée. Si l’on y ajoute un prouveur de théorèmes capable de vérifier qu’un certain sous-graphe possède toujours une structure donnée, la procédure correspondante pourrait être générée statiquement, tandis que le reste du graphe de plus haut niveau serait généré dynamiquement à l’exécution
Ainsi, quiconque résout le problème du dessin de graphes généraliste aura probablement aussi la capacité ou l’intuition nécessaires pour implémenter cela
Une bibliothèque de dessin de graphes généraliste du type Graphviz, offrant davantage d’options et de contrôle
https://eclipse.dev/elk/
Expérience menée par l’équipe de développement d’ELK à l’université de Kiel
https://github.com/kieler/KLighD
Wiki du projet Kieler
https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
Bibliothèque de dessin de graphes fondée sur des contraintes
https://www.adaptagrams.org/
Implémentation JavaScript
https://ialab.it.monash.edu/webcola/
Ressource intéressante : HOLA: Human-like Orthogonal Network Layout
https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
La démo Confluent Graphs rend les arêtes plus lisibles
https://www.aviz.fr/~bbach/confluentgraphs/
Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
https://arxiv.org/pdf/1408.4626.pdf
Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
https://arxiv.org/pdf/1311.6996v1.pdf
Même pour deux graphes structurellement identiques, deux personnes peuvent les rendre de manière complètement différente afin de mettre en avant des aspects différents des données. C’est aussi similaire aux problèmes de « l’algorithme de graphe généraliste » et de « la structure de données graphe généraliste »
Les graphes se situent à la frontière entre code et données. Par exemple, tout programme possède un graphe d’appels ; en un certain sens, donc, un « algorithme de graphe généraliste » revient au calcul lui-même
Dès qu’on dépasse quelques dizaines de nœuds, il devient généralement difficile de les rendre plans, ou de limiter les croisements et de bien regrouper les nœuds liés pour donner une apparence presque planaire
En réalité, le dessin de graphes doit réconcilier des choses qui ne sont presque jamais hiérarchiques, et il est difficile de tracer mathématiquement une frontière stricte entre ce qui relève ou non d’une hiérarchie. Moins on fait d’hypothèses sur la structure du graphe sous-jacent — connectivité, présence de cycles, parcimonie — plus le problème s’aggrave
En pratique, lorsqu’on conçoit une UI pour interagir avec des graphes, on peut généralement définir ou imposer un ou deux niveaux de méta-hiérarchie pour permettre le clustering ; cela réduit l’effet des nœuds en hairball qui gâchent le layout, diminue le nombre de nœuds et améliore aussi les performances de rendu. Pour le layout, on peut utiliser fCOSE, qui dispose aussi d’une implémentation Cytoscape.js
Je pense que l’observation centrale — « il y a trop de choix d’implémentation » — n’est pas entièrement juste.
En pratique, une bibliothèque pourrait implémenter toutes les représentations de graphes pertinentes, fournir les algorithmes les plus performants pour chacune, et proposer des conversions entre représentations. Ces conversions sont proportionnelles au nombre de représentations, leur implémentation comme leur usage sont simples, et la charge reste donc assez raisonnable pour les mainteneurs comme pour les utilisateurs.
En prime, elle pourrait aussi fournir des conversions d’import/export depuis les types de données et idiomes de la bibliothèque standard. La mémoire et le coût de conversion sont bon marché, et dans 99 % des cas d’usage, l’overhead de transformation des données serait probablement négligeable, aussi bien côté RAM que CPU.
Cela me rappelle aussi la phrase : « La dure vérité quand on travaille chez Google, c’est qu’au final on ne fait que déplacer des protobufs d’un endroit à un autre. »
https://news.ycombinator.com/item?id=20132880
Au final, on réimplémente toujours les graphes. Les performances comptent, et les bibliothèques de graphes toutes faites que j’ai vues ne tiraient pas parti de la régularité de nos jeux de données. Par exemple, nous utilisons un DAG append-only où presque tous les nœuds n’ont qu’une arête vers l’élément ajouté le plus récemment, ce qui permet en interne un codage par longueurs de plages.
Je n’ai pas non plus vu de bibliothèque de graphes générique prenant en charge les requêtes dont nous avons besoin. La plus importante est notamment une fonction de diff de sous-graphes.
En plus, une implémentation sur mesure ne représente pas tant de travail. Les graphes sont beaucoup plus faciles à réimplémenter qu’un B-tree, et une implémentation simple tient en quelques dizaines de lignes. Même notre bibliothèque très optimisée, algorithmes pris en charge compris, fait de l’ordre de quelques centaines de lignes.
Avoir un moyen d’exporter les données dans un format standard serait pratique, mais dans notre cas d’usage, intégrer une bibliothèque créerait probablement plus de problèmes qu’elle n’en résoudrait.
L’application manquante à laquelle je pense souvent, c’est Excel pour les graphes.
Un outil qui, comme Excel pour les données tabulaires, manipulerait des données tenant en RAM — une taille qui nécessite un ordinateur, mais pas un datacenter —, implémenterait de nombreux algorithmes et visualisations de façon « suffisamment correcte », et serait utilisable sans connaissances en programmation.
Comme le dit l’article, beaucoup de problèmes réels sont des problèmes de graphes ; alors pourquoi seuls les programmeurs devraient-ils avoir des outils pour les résoudre ?
Pourtant, il existe des structures de données et des bibliothèques standard qui conviennent assez bien à la plupart des cas d’usage, et si l’on a des exigences particulièrement corsées, on peut faire une solution sur mesure.
L’article dit que les graphes sont souvent trop grands, mais si l’on interroge des gens qui manipulent réellement des algorithmes de graphes, il est facile d’entendre ce genre d’expérience. La plupart des programmeurs et des utilisateurs ne manipulent probablement que de tout petits graphes.
Je ne pense pas que l’utilisateur lambda voie des graphes dans des problèmes réels aléatoires. Ce que j’ai appris en travaillant dans une grande entreprise, c’est qu’avec assez d’efforts, tout peut devenir une feuille de calcul Excel.
https://strlen.com/treesheets/ est plus proche d’un Excel pour données arborescentes.
Par exemple, il dit qu’on peut modéliser Internet comme un graphe ; même si c’est vrai, on ne voit pas clairement ce que cela apporte. Internet peut être représenté de plusieurs façons, et il n’est pas évident que le représenter sous forme de graphe ait, en général, des implications d’ingénierie utiles.
On pourrait soutenir avec une force de persuasion comparable que la représentation idéale pour obtenir des informations utiles est plutôt une fonction d’encodage matriciel en boîte noire qui mappe des entrées arbitraires vers des sorties cohérentes, autrement dit un réseau de neurones.
Pour un endroit comme Google, c’est peut-être une idée à plusieurs milliards de dollars, mais Internet dans son ensemble n’est pas un problème de graphe pour beaucoup de gens, et le représenter comme un graphe ne résout pas grand-chose.
Rares sont les gens qui résolvent des problèmes réels sur papier avec des graphes. Les tableaux, eux, sont utilisés en permanence. Les graphes sont courants, mais les problèmes de graphes ne le sont pas.
D’autres commentaires ont aussi dit que la visualisation de graphes était difficile, mais une interface 3D donne beaucoup plus d’espace. Quand la vague VR a commencé, je me suis demandé : « Quel sera l’Excel de la VR ? » La réponse de Microsoft a été : « une feuille de calcul 2D flottant dans un espace 3D ». Je trouve ça absurde. Pour moi, ce sont les graphes.
Si quelqu’un veut explorer ça ensemble, il peut m’écrire à mon nom d’utilisateur at gmail.com.
Les types graphe existent depuis assez longtemps.
Erlang a https://www.erlang.org/doc/man/digraph.html et https://www.erlang.org/doc/man/digraph_utils, et si l’on veut faire des opérations relevant de la théorie des ensembles, il y a aussi https://www.erlang.org/doc/man/sofs.html.
Il y est dit : « J’ai trouvé deux autres langages avec un type graphe : Erlang et SWI-Prolog. Comme je ne connais bien ni l’un ni l’autre, je ne peux pas dire quand cela a été ajouté, mais Erlang en avait au moins avant 2008. J’ai contacté quelqu’un du comité du langage Erlang, mais je n’ai pas reçu de réponse. »
Je l’ai déjà utilisée pour de la résolution de dépendances afin de déterminer l’ordre des tâches.