Auf der Spur des verschwundenen Datentyps

• Graphen sind in Software allgegenwärtig – etwa bei Abhängigkeiten, Web-Links, Zustandsräumen von Model Checkern oder Fremdschlüsseln in relationalen Datenbanken –, aber gängige Programmiersprachen bieten dafür kaum eingebaute Typen oder Unterstützung in der Standardbibliothek
• Ein eingebauter Graph-Typ ist zunächst deshalb schwer umzusetzen, weil es viele Grapharten gibt – etwa gerichtet/ungerichtet, einfach/mehrfach oder Hypergraphen – und bestimmte Eigenschaften die Wahl des Algorithmus und die Performance stark beeinflussen
• Auch die Darstellungsform macht einen Unterschied: Kantenliste, Adjazenzliste, Adjazenzmatrix oder referenzierende Structs haben unterschiedliche Speicher- und Abfrageeigenschaften, sodass sich mit einer einzigen universellen Darstellung kaum alle Anwendungsfälle gut abdecken lassen
• Graphalgorithmen sind schwer zu implementieren und laufen oft auf großen Eingaben; wie die Beispiele Nosey Parker und Gecode zeigen, können problemangepasste Darstellung und Traversierung wichtiger sein als eine allgemeine Bibliothek
• Dass Graphen in Standardbibliotheken selten sind, liegt an den Trade-offs bei Typen, Darstellungen, Algorithmen und Performance sowie am hohen Wartungsaufwand; auch Third-Party-Bibliotheken können eingeschränkt oder zu langsam sein

---

Graphen sind verbreitet, aber Sprachunterstützung ist schwach

• Ein Graph besteht aus Knoten und Kanten; sowohl Knoten als auch Kanten können Daten enthalten
• Im Software Engineering tauchen Graphen in vielen Formen auf
  • Paketabhängigkeiten und Modul-Imports bilden gerichtete Graphen
  • Das Internet ist ein Link-Graph zwischen Webseiten
  • Model Checker durchsuchen den Zustandsraum aller möglichen Konfigurationen; Knoten sind Zustände, Kanten sind gültige Übergänge
  • Relationale Datenbanken lassen sich als Graphen auffassen, bei denen Datensätze Knoten und Fremdschlüssel Kanten sind
  • Graphen kann man als Verallgemeinerung von Linked Lists, binären Bäumen und Hash-Tabellen sehen
• Auch in der Business-Logik treten Graphen häufig auf, etwa bei Zitationsbeziehungen, Routen in Verkehrsnetzen oder Verbindungen in sozialen Netzwerken
• Obwohl Graphen oft gebraucht werden, bieten die meisten gängigen Sprachen sie weder als eingebauten Typ noch in der Standardbibliothek an
• In vielen Ökosystemen fehlen zudem robuste Third-Party-Graphbibliotheken, sodass man sie oft selbst implementieren muss

Beim Entwurf eines Graph-Typs gibt es zu viele Wahlmöglichkeiten

• Neben gerichteten und ungerichteten Graphen gibt es viele weitere Varianten
  • einfache Graphen mit höchstens einer Kante zwischen zwei Knoten und Multigraphen mit mehreren Kanten
  • Hypergraphen, bei denen eine Kante drei oder mehr Knoten verbindet
  • Ubergraphen, bei denen Kanten auf andere Kanten zeigen können
• Mit jeder Variante kommen weitere Designentscheidungen hinzu
  • Sollten auch Kanten IDs bekommen oder nur Knoten?
  • Welche Daten sollen in Knoten und Kanten gespeichert werden?
• Man könnte alle Graphen als universellen Typ wie einen „gerichteten Hyper-Uber-Multigraphen“ anbieten und die Nutzer einschränken lassen, aber das führt sofort zu zwei Problemen
  • Die Schnittstelle ändert sich, etwa je nachdem, ob das Ergebnis einer Operation ein Einzelwert oder eine Liste ist
  • Wenn spezielle Grapheigenschaften nicht ausgenutzt werden, leidet die Performance der Algorithmen
• Zum Beispiel kann maximum weight matching mit einem schnelleren Algorithmus gelöst werden, wenn bekannt ist, dass der Graph bipartit ist; bei allgemeinen Graphen braucht man einen langsameren, allgemeineren Algorithmus
• Wenn es ein Problem P, einen Graphen G und die Algorithmen A, B und C gibt, stellt sich außerdem die Frage des Algorithm Dispatch: Welcher Algorithmus soll ausgeführt werden?
• Eine perfekte Graphbibliothek müsste viele Grapharten unterstützen, doch dadurch bliebe weniger Zeit für die Implementierung der Algorithmen, die Nutzer tatsächlich brauchen
• Graphalgorithmen sind schwer zu implementieren
  • Der von Python-Erfinder Guido geschriebene Algorithmus find_shortest_path wurde später fünfmal korrigiert
  • Nicole sagt, dass alle von ihr verglichenen PageRank-Implementierungen falsch waren
  • NetworkX bietet etwa 500 Graphalgorithmen; allein der Algorithmus-Code umfasst fast 60.000 Zeilen
  • Die gesamte Python-Standardbibliothek hat rund 300 Pakete und weniger als 600.000 Zeilen
• Maintainer von Standardbibliotheken müssen entscheiden, welche Graph-Typen, welche topologischen Spezialfälle und welche Algorithmen aufgenommen werden sollen; das erhöht den Wartungsaufwand erheblich
• Auch Python ist zwar für „batteries included“ bekannt, aber mit PEP 594 geht der Trend dahin, 20 Module aus der Standardbibliothek zu entfernen

Auch bei der Graphdarstellung ist eine Einheitslösung schwer

• Selbst wenn man nur den einfachsten gerichteten Graphen betrachtet, gibt es mehrere mögliche interne Darstellungen
  • Kantenliste: [[a, b], [b, c], [c, a], [c, b]]
  • Adjazenzliste: [[b], [c], [a, b]]
  • Adjazenzmatrix: [0 1 0; 0 0 1; 1 1 0]
  • eine Menge gegenseitig referenzierender Structs
• Je nach Darstellung unterscheidet sich die Performance der Operationen
  • Wenn ein Graph mit 100 Knoten und 200 Kanten als Adjazenzmatrix dargestellt wird, enthält die 100×100-Matrix 200 Einsen und 9.800 Nullen
  • Derselbe Graph braucht als Kantenliste nur 200 Knotenpaare
  • Je nach Sprache und Optimierungsgrad kann sich der Speicherverbrauch um mehr als den Faktor 20 unterscheiden
• Umgekehrt sieht es bei einem Graphen mit 100 Knoten und 8.000 Kanten anders aus, wenn man nach einer Kante zwischen Knoten 0 und 93 sucht
  • In der Adjazenzmatrix ist die Abfrage mit graph[0][93] in O(1) möglich
  • Bei einer Kantenliste muss man 8.000 Kanten durchlaufen, also O(|edge|) Zeit aufwenden
• Graphen mit wenigen Kanten heißen sparse Graphen, Graphen mit fast allen möglichen Kanten dense Graphen
• Programme, die einen Graphen aus externen Daten aufbauen, können anfangs sparse und später dense sein; eine intern „immer richtige“ Darstellung gibt es daher nicht
• Wenn man Knotendaten, Kantendaten sowie mehrere Arten von Knoten und Kanten unterstützt, steigt die Implementierungskomplexität weiter
• Third-Party-Bibliotheken wählen meist eine von zwei Richtungen
  • Sie bieten einen reichhaltigen Einheits-Typ für möglichst viele Anwendungsfälle und opfern dafür Effizienz
  • Oder sie bieten getrennte Graph-Typen je Darstellungsform an und überlassen die Verwaltung von Knoten- und Kantendaten den Nutzern

Die Trade-offs von NetworkX und Petgraph

• NetworkX speichert Graphen als dict-von-dict-von-dict, damit sich beliebige Daten an Knoten und Kanten anhängen lassen
• Es gibt Funktionen zur Umwandlung in andere Darstellungen, aber keine Arbeitsweise, bei der direkt auf diesen Darstellungen gearbeitet wird
• Die bekannte Rust-Graphbibliothek Petgraph bietet mit graph, graphmap und matrix_graph verschiedene Typen für unterschiedliche Anwendungsfälle
• Bradford verwendet Petgraph in Nosey Parker, einem Sicherheitstool, das Secrets in der gesamten Historie eines Git-Repositories findet
  • Der Benchmark-Graph ist CPython und umfasst 250.000 Commits und 1.300.000 Objekte
  • Pro Commit-Knoten gibt es nur wenige Kanten, daher fiel die Wahl auf eine Adjazenzliste
• Die Unterstützung mehrerer Darstellungen erhöht jedoch die Kosten für zusätzliche Algorithmen
  • Wenn man für jede Darstellung eigene Algorithmen schreibt, steigt der Wartungsaufwand um das Drei- bis Vierfache
  • Nutzt man stattdessen allgemeine Abstraktionen über polymorphen Typen, sinkt die Performance
• Ein Interviewpartner schätzte, dass selbst geschriebene Graphalgorithmen mehr als 20-mal schneller sein können als generische Algorithmen

Performance-Beschränkungen sind das Kernproblem von Graphbibliotheken

• Unter Graphalgorithmen finden sich viele NP-vollständige oder noch schwierigere Probleme
  • Von Karps 21 kanonischen NP-vollständigen Problemen sind 14 Graphprobleme
• Graphprobleme laufen oft auf sehr großen Eingaben, sodass Darstellungsform und Implementierungsdetails darüber entscheiden, ob die Berechnung überhaupt praktikabel ist
• Bradford musste in Nosey Parker den Objektgraphen traversieren, um für jeden Commit einen Dateisystem-Snapshot zu rekonstruieren
  • Die vier Graph-Walker von Petgraph ließen sich für diesen Anwendungsfall nicht passend erweitern
  • Daher entwarf er spontan einen „semi-novel“ graph traversal algorithm und reduzierte den Speicherverbrauch auf ein Tausendstel
• Zayenz nennt das 15 puzzle als Beispiel für einen Graphen, der so groß ist, dass man ihn nicht vollständig behandeln kann
  • Die Lösungssuche läuft als A* search im Zustandsraum
  • Dieser Zustandsraum hat mehr als zwei Billionen Zustände
  • Schon das Erzeugen aller Knoten bedeutet praktisch das Scheitern
• Auch in einem Forschungsprojekt zu Graph-Erweiterungen für den Constraint Solver Gecode, an dem Zayenz beteiligt war, konnte ein generischer Graph-Typ nicht mit einer problemspezifischen Darstellung konkurrieren
• Graphdatenbanken sind zwar für die Ausführung komplexer Graphalgorithmen konzipiert, haben aber weiterhin Performance-Probleme
  • Laut Nicole besucht man beim Traversieren ohne Tiefenbegrenzung schnell den gesamten Graphen
  • Selbst eine Suche wie „gehe drei Schritte nach außen und finde einen Pfad, falls es ihn gibt“ besucht sehr viele Daten
• Nicole führt in ihrer Beratung zur Performance von Graphabfragen meist Migrationen weg von Graphdatenbanken durch
  • In einem Projekt blieb nur eine einzige Berechnung unverändert, der Rest wurde als MapReduce-Verfahren neu geschrieben
  • Das war schwerer zu verstehen, konnte aber tatsächlich über Nacht abgeschlossen werden

Warum Graphen in Standardbibliotheken selten sind

• Dass breite Graphunterstützung selten ist, liegt an mehreren zusammenwirkenden Faktoren
  • Es gibt viele Grapharten
  • Für jede Graphart gibt es viele Darstellungsformen
  • Es gibt viele Graphalgorithmen
  • Die Performance von Algorithmen reagiert empfindlich auf Darstellung und Implementierungsdetails
  • Menschen führen sehr teure Algorithmen auf sehr großen Graphen aus
• Standardbibliotheken von Sprachen müssten zu viele Designentscheidungen, Trade-offs und Wartungslasten schultern
• Es gibt auch Gründe, warum Programmierer Third-Party-Graphbibliotheken meiden
  • Die Bibliothek kann zu eingeschränkt sein
  • Eine generische Bibliothek erfüllt die Performance-Anforderungen womöglich nicht
• Graphen sind für die Systemanalyse nützlich, aber bei der Implementierung muss man Datenrepräsentation und Algorithmuswahl oft selbst kontrollieren

Anhang: Sprachen mit Graph-Typen und verwandte Werkzeuge

• Eine Graph Query Language (GQL) erfüllt in Graphdatenbanken eine ähnliche Rolle wie SQL
  • Einen breit genutzten Standard gibt es nicht, bekannte Beispiele sind aber SPARQL und Cypher von Neo4j
  • Dieses GQL darf nicht mit der in Entwicklung befindlichen Standardsprache GQL verwechselt werden
• GraphQL ist keine Graph Query Language; der Name geht auf die Verbindung zu Facebook Graph Search zurück
• Ein wesentlicher Unterschied zwischen GQL und SQL ist, dass Beziehungen beziehungsweise „joins“ Entitäten erster Klasse sind
  • In einem Film-und-Personen-Datensatz würde SQL die Beziehungen „spielt mit“, „führt Regie“ und „produziert“ jeweils als Many-to-Many-Tabellen modellieren
  • In SPARQL sind Beziehungen Kanten, sodass sich „welche Personen hatten in Film Y irgendeine Rolle und welche war das?“ leicht abfragen lässt
• GQL kann auch Kantenoperationen wie Kantenumkehr, Komposition und transitive Hülle unterstützen
  • SPARQL unterstützt weder Pfadlängen noch Berechnungen entlang eines Pfads, etwa das Sammeln einer Filmkette, die zwei Schauspieler verbindet
  • Ein GQL, das so etwas unterstützt, wird deutlich komplexer
• Die formale Spezifikationssprache Alloy hat nützliche Graph-Traversierungs-Primitiven für den Datentyp relation, wodurch sich Graphdarstellungen leichter handhaben lassen als in allgemeinen Programmiersprachen
  • Diese Primitiven basieren allerdings auf gelabelten Kanten und passen womöglich nicht zu anderen Graphdarstellungen
• Python hat 2020 graphlib hinzugefügt
  • Es gibt außer TopologicalSorter keine weiteren Methoden
  • Der Graph wird nur als Knoten-dict angenommen
  • Ein Graph a -> b wird als umgekehrtes dict wie {b: [a]} dargestellt
• Stand 2023 wird graphlib intern in CPython nicht verwendet
  • Auf GitHub gibt es weniger als 900 Dateien, die graphlib referenzieren
  • zoneinfo, das im selben Jahr hinzugefügt wurde, taucht in mehr als 6.000 Dateien auf
  • Der Ausdruck def topological_sort( erscheint in 4.000 Dateien
  • Viele selbst implementierte topologische Sortierungen verwenden andere Graphdarstellungen als graphlib und lassen sich daher nur schwer umstellen
• Weitere Beispiele für Graph-Typen in Standardbibliotheken sind Erlang und SWI-Prolog
• Es gibt auch Programmiersprachen, in denen „alles ein Graph“ ist
  • Beispiele sind GP2 und Grape
  • Der Bereich ist derzeit stark akademisch geprägt
• Auch mathematische Softwaresprachen wie Mathematica, MATLAB und Maple haben in irgendeiner Form Graphbibliotheken
• Mit einem Update vom 18. März 2024 wurden einige Kommentare zum Artikel auf einer separaten Seite gesammelt

[GN⁺]

Hacker-News-Kommentare

• Graphviz hat eine eigene Basis-Graphbibliothek, die von anderen Projekten nicht verwendet wird, mit Vor- und Nachteilen
  Auf Grundlage dieser Erfahrung haben wir wohl auch das typische Second-System-Syndrom erlebt. Wir wollten eine modulare, typsichere und effiziente Graphbibliothek bauen, aber am Ende war es vermutlich eine Variante von „gut, schnell, billig — wähle zwei“
  Modular bedeutete, dass wir Bündel von Graphalgorithmus-Bibliotheken unabhängig entwickeln und kompilieren können wollten, und typsicher bedeutete, dass wir Programmierfehler lieber beim Kompilieren oder spätestens beim Linken erkennen wollten statt als Laufzeitfehler wie „Knoten hat kein Attribut color“
  Effizient bedeutete, dass der Zugriff auf Grapheigenschaften so billig sein musste wie der Zugriff auf Strukturfelder in C, und wir wollten weder externe Hash-Tabellen mit uns herumschleppen noch viele String-Konvertierungen verwenden
  Ob diese Ziele den Preis wert waren oder überhaupt sinnvoll, darüber lässt sich streiten, aber das war damals unser Ziel. Im Labor gab es bekannte C++-Schöpfer, und wir waren bereit, C++ noch eine Chance zu geben
  Gordon Woodhull, der als Praktikant anfing und dann dabeiblieb, war ein hervorragender Programmierer und schrieb eine Implementierung dieser Graphbibliothek in Template-C++. Der Quellcode steht auch auf https://www.dynagraph.org/
  Der Rest von uns war sich nicht sicher, ob wir jemals verstehen würden, wie dieser Code funktioniert, also machten wir Code-Reviews mit berühmten C++-Erfindern, und nach zahllosen Bildschirmen voller Code und Schweigen kamen wir zu dem Schluss: „Wird wahrscheinlich funktionieren.“ Da wussten wir schon, dass wir vielleicht bereits über die Klippe der Komplexität hinaus waren
  Template-Fehler zur Compile-Zeit füllten mit einem einzigen Fehler den ganzen Bildschirm und spuckten Details aus, die wohl nur C++-Erfinder lieben könnten. Der Fehler lag bei uns, und Gordon drückte weiter und brachte sogar dynamisches Graph-Layout auf Microsoft OLE zum Laufen
  Rückblickend war es so etwas wie unser eigenes Project Xanadu, und während wir uns darin verirrten, erschienen Dinge wie Gephi (Java), NetworkX und NetworKit (Python). John Ellson, ein brillanter Softwareingenieur, der Teile von Graphviz geschrieben hat, belebte die eigentliche Hauptlinie der Arbeit wieder

  • Man kann die Graphviz-dot-Syntax mit NetworkX parsen, um Ausführungspläne für teure Tools zu erstellen, und dank der Graphstruktur ist automatische Parallelisierung möglich

• Als jemand, der viel mit Graphen gearbeitet hat, wurde ich unzählige Male gefragt: „Warum haben Programmiersprachen keinen eingebauten Graph-Datentyp?“
  Ich freue mich, jetzt nicht nur sagen zu müssen „Vertrau mir, das ist wirklich schwer gut zu machen“, sondern auf tiefergehende Analysen wie diesen Artikel verweisen zu können

  • Ein leicht komischer Punkt an dieser Frage ist, dass dabei meist übersehen wird, dass die meisten Sprachen nicht einmal eine Baum-Datenstruktur haben
    Die meisten Sprachen bieten als strukturelle Typen nur statische Arrays, dynamische Arrays und verkettete Listen. Dinge wie binäre Suchbäume oder Hash-Tabellen sind semantische Abstraktionen, die einen Teil der Fähigkeiten der zugrunde liegenden Struktur verbergen, und keine reine strukturelle Darstellung
  • Graphen sind eine breite Datenstruktur, deren Repräsentation je nach Anforderungen stark variiert, deshalb hielt ich es immer für sinnvoller, sie auf Domänenebene zu implementieren
    Der Teil im Artikel „es gibt zu viele Implementierungsoptionen“ sagt im Grunde dasselbe. Dann sah ich Petgraph [0] und schaute mir zum ersten Mal eine allgemeine Graphbibliothek wirklich genauer an; ich fand sie ziemlich interessant, habe Graphen aber trotzdem weiterhin auf Domänenebene implementiert
    [0] https://github.com/petgraph/petgraph
  • Ich hatte auch die gegenteilige Erfahrung. Als ich in Tcl zum ersten Mal mit Graphen arbeitete, ging ich selbstverständlich davon aus, dass es in der Standardbibliothek keine Graphalgorithmen geben würde, aber es gab sie doch, und dadurch musste ich das Rad nicht neu erfinden
    https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
  • Noch wichtiger als „es ist wirklich schwer, es gut zu machen“ ist, dass es viele Trade-offs gibt
    Fast jede Sprache bietet eine Hash-Map, und auch wenn man sie in bestimmten Situationen mit einer Eigenimplementierung schneller machen kann, funktioniert die Standardimplementierung im Allgemeinen ziemlich gut. Bei Graphen ist das schwieriger, und wenn man es anbietet, müsste man womöglich mehrere Graphtypen bereitstellen
    Nebenbei ist Java HashMap insofern etwas ungewöhnlich, als man dort im Unterschied zu den meisten anderen Sprachen den Lastfaktor anpassen kann
  • Das ist vielleicht ein sehr naiver Gedanke, aber ich würde Zeiger im Grunde als nativen Graph-Typ ansehen
    Was die Leute eigentlich wollen, ist weniger ein Graph-Typ an sich als vielmehr Werkzeug zum Traversieren von Graphen

• Ich denke, Graphen sind eher eine Abstraktion als eine Datenstruktur oder ein Datentyp
  Grundsätzlich braucht man zur Definition eines Graphen nur eine Knotenmenge v \in V und die Funktion Neighbors(v), und für die meisten grundlegenden Graphalgorithmen reicht das tatsächlich schon aus
  Alles andere sind fallbezogene Einschränkungen. Etwa ob A->B bedeutet, dass auch B->A gilt, ob die Knotenmenge unter bestimmten Bedingungen partitionierbar ist oder ob es Farben oder Labels gibt
  Verallgemeinert kann man bis zu Hypergraphen gehen; dort braucht man nur eine Knotenmenge und eine Menge von Knotenmengen. Je nach Interesse kann man das auf unzählige Arten darstellen, und gewöhnliche Graphen sind nur ein Spezialfall davon
  Aus Datenbanksicht kann man das auch als Problem der Abfrageoptimierung und Indizierung sehen. Je nachdem, welche Fragen man an einen Graphen stellen möchte, eignen sich unterschiedliche Darstellungen besser. So wie es nicht nur eine Art gibt, die Abstraktion „Tabelle“ darzustellen, gibt es auch nicht nur eine Art für „Graph“

  • Der Grund, warum Graphen überall sind, ist, dass sie so abstrakt sind
    Sie liegen auf derselben Abstraktionsebene wie reine Zahlen. So wie man von nützlichen „numerischen“ Bibliotheken sprechen kann, kann man auch von nützlichen „graphartigen“ Bibliotheken sprechen, aber eine „Zahlen“-Bibliothek oder eine „Graph“-Bibliothek gibt es kaum. Solche Konzepte sind zu abstrakt, um daraus eine API zu machen
  • Schon mit einer Knotenmenge und Neighbors(v) gibt es starke Einschränkungen. Denn Mehrfachkanten zum selben Nachbarn werden damit nicht erlaubt
  • Wenn ein Hypergraph eine Knotenmenge und eine Menge von Knotenmengen ist, klingt das auch ein wenig wie ein Dateisystem
    Dateien wären dann Knoten und Verzeichnisse verschachtelbare Knotenmengen

• Es gibt zwei zentrale Hindernisse
  Für einfache und kleine Graphprobleme ist es schon einfach genug, eine Adjazenzliste direkt als Vektor von Vektoren zu schreiben, und bei komplexen und riesigen Graphproblemen bekommt man nur dann Leistung, wenn man die Graphimplementierung passgenau auf die Details des zu lösenden Problems zuschneidet
  Deshalb ist schwer zu erkennen, welche Sprachunterstützung hier helfen würde. Es wäre schwierig, außer vielleicht mit einem superintelligenten Compiler, der den Code analysiert und entscheidet, ob Adjazenzliste, Matrix, 3D-Array oder etwas anderes optimal ist. Solche Optimierungen wird man in Compilern wohl noch lange nicht sehen
  Das ist ein weiteres Beispiel für das von Stroustrup beobachtete Phänomen. Wir teilen Code gut bei kleinen Dingen wie Vektoren und bei großen Dingen wie Betriebssystemen, aber bei Problemen mittlerer Größe gelingt uns das nicht gut

  • Selbst kleine Dinge werden nicht wirklich so gut geteilt. Jede Programmiersprache hat schließlich ihre eigene Vektorimplementierung
    Innerhalb eines Sprachökosystems wirkt das Teilen leicht, weil eine Vektor-API klein ist. Betriebssysteme haben im Verhältnis zu ihrer internen Komplexität ebenfalls eine relativ kleine API, und für numerische Bibliotheken gilt Ähnliches, daher lassen sie sich gut teilen
    Wenn man dagegen etwas stärker anpassen will, etwa bei komplexen Datenstrukturen, wird die API komplizierter und das Teilen schwieriger. Letztlich scheint die Teilbarkeit von der Oberfläche des Geteilten abzuhängen, also von der relativen Größe der API
  • Algorithmen zu betrachten, die gegen abstrakte Graph-Typen geschrieben sind, und dann die Implementierung passend zu einem bestimmten Algorithmus auszufüllen und zu optimieren, scheint ziemlich gut in den Bereich code-spezialisierter LLMs zu passen

• Electric Clojure verwendet die S-Expressions von Clojure selbst als Syntax zum Schreiben von Graphen und konkretisiert per Makros den Datenfluss eines reaktiven Client/Server-Systems
  Hier sind Full-Stack-Benutzeroberflächen der Anwendungsfall, aber die Idee lässt sich verallgemeinern. https://github.com/hyperfiddle/electric Gründer
  Meine Antwort auf „Wo sind all die Graph-Typen geblieben?“ wäre, dass ein DSL zum Schreiben von Graphen Scope, Kontrollfluss und Abstraktion ausdrücken muss und damit letztlich isomorph zu einer Programmiersprache wird, die vom Auswertungsmodell befreit ist. In Python und TypeScript ist es ziemlich schwer, eine vollständige Programmiersprache hineinzustecken
  Auch der Blogbeitrag „Four problems preventing visual flowchart programming from expressing web applications“ ist lesenswert
  https://www.dustingetz.com/#/page/four%20problems%20preventi...

• Dieser Beitrag beantwortet vor allem die Frage „Warum unterstützen Programmiersprachen Graphalgorithmen nicht besser?“ und scheint sich eher auf die Verarbeitung von „Big-Data“-Graphen zu konzentrieren als auf allgemeine Graphunterstützung
  Wenn man Graphunterstützung insgesamt betrachtet, gehören auch breitere Fragen dazu wie „Warum sind OGM (Object Graph Mapper) nicht so beliebt wie ORM?“ oder „Warum ist JSON weit verbreitet, RDF oder andere low-level Graphserialisierungen aber nicht?“
  Am Ende sind historische Gründe wohl ausschlaggebend. RDF kam etwas zu früh und konnte sich nicht richtig weiterentwickeln, stattdessen entstand ein schrecklicher akademischer Standard- und Implementierungs-Stack. Dazu kommt, dass Graphen bei Implementierung und Lernkurve inhärent etwas komplexer sind und sich deshalb für viele Entwickler nicht gut skalieren
  Dem Abschnitt „Graph Querying Language“ im Artikel würde ich nicht zu viel Gewicht geben. Teile davon lesen sich wie Marketingsprache von begeisterten Neo4J- oder SPARQL-Nutzern, die nie tatsächlich ein Produkt gebaut haben
  Es heißt dort, „der Hauptunterschied zwischen allen GQLs und SQL sei, dass Joins, also Beziehungen, First-Class-Entities seien“, aber in SQL sind Joins ebenfalls First-Class-Entities. Es gibt sogar das Schlüsselwort JOIN
  Wenn man auf die niedrigere Ebene von Graphabfragesprachen hinuntergeht und sich die Abfrageplanung ansieht, gibt es kaum bedeutende Unterschiede zu SQL-basierten Abfragen. Dass die Standardisierung von GQL[0] als SQL-Erweiterung voranschreitet, ist dafür ein Beleg
  SPARQL ist einfach, wenn man exakte Pfadtraversierung braucht, aber sobald man etwas etwas Komplexeres machen will, wie es in einem Web-App-Backend vorkommen könnte, stößt man schnell auf Fallen wie Joins mit ungebundenen Werten, die versehentlich die gesamte Ergebnismenge auslöschen
  [0]: https://en.wikipedia.org/wiki/Graph_Query_Language

  • Dass es ein eigenes Schlüsselwort gibt, ist eher ein starkes Indiz dafür, dass etwas kein First-Class-Objekt ist
    Zum Beispiel sind Haskells Typeclasses nicht First-Class, und in den meisten Programmiersprachen gilt das auch für Kontrollfluss
  • JOINs, besonders bei rekursiven Abfragen, sind der Kern von Graphdatenbanken, und SQL-Relationale Datenbanken können damit im Allgemeinen ebenfalls gut umgehen
    Es fehlt ihnen nur an syntaktischen Abkürzungen, und darauf sind Graphabfragesprachen im Wesentlichen fokussiert

• Auch Werkzeuge zum Zeichnen von Graphen sind ziemlich enttäuschend. Bei kleinen Graphen funktionieren sie gut, aber sobald es ungefähr mehr als 500 Knoten werden, ist die Ausgabe entweder völlig unverständlich oder sehr schwer lesbar
  Es fehlt an der Fähigkeit, Graphen automatisch in eine Hierarchie zu ordnen und eine Oberfläche bereitzustellen, die sich gut zum Erkunden eignet. Wenn man bedenkt, dass wir es gewohnt sind, fast alles um uns herum bis zu einem gewissen Grad als Hierarchie zu betrachten, scheint es, als müsse beim Erstellen eines allgemeinen Graph-Datentyps dieselbe Art von Problem gelöst werden
  Das müsste womöglich auf Compiler-Ebene umgesetzt werden, sodass sich allgemeine Graph-Algorithmen an die erzeugte Strukturhierarchie anpassen. Wenn man dazu noch einen Theorembeweiser hinzufügt, der bestätigen kann, dass bestimmte Teilgraphen immer eine bestimmte Struktur besitzen, könnte dieses Verfahren statisch erzeugt werden, während es für den übrigen übergeordneten Graphen zur Laufzeit dynamisch erzeugt werden könnte
  Wer also das Problem des allgemeinen Zeichnens von Graphen löst, wird vermutlich auch die Fähigkeit oder Einsicht haben, dieses Problem umzusetzen

  • Graphen zu zeichnen ist schwierig
    Eine allgemeine Bibliothek zum Zeichnen von Graphen im Stil von Graphviz, die mehr Optionen und Kontrolle bietet
    https://eclipse.dev/elk/
    Ein vom ELK-Entwicklungsteam der Kiel University durchgeführtes Experiment
    https://github.com/kieler/KLighD
    Kieler-Projekt-Wiki
    https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
    Eine constraint-basierte Bibliothek zum Zeichnen von Graphen
    https://www.adaptagrams.org/
    JavaScript-Implementierung
    https://ialab.it.monash.edu/webcola/
    Als interessantes Material: HOLA: Human-like Orthogonal Network Layout
    https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
    Die Confluent-Graphs-Demo macht Kanten besser lesbar
    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
  • Manche Algorithmen gehen besser mit diesem Problem um, aber im allgemeinen Fall ist die Aufgabe „ein gutes Diagramm eines Graphen zu erzeugen“ beinahe ein intelligenzvollständiges Problem
    Selbst bei strukturell identischen Graphen können zwei Personen sie völlig unterschiedlich rendern, um verschiedene Aspekte der Daten hervorzuheben. Das ähnelt auch den Problemen „allgemeiner Graph-Algorithmus“ und „allgemeine Graph-Datenstruktur“
    Graphen liegen an der Grenze zwischen Code und Daten. Zum Beispiel hat jedes Programm einen Aufrufgraphen, also ist in gewissem Sinne ein „allgemeiner Graph-Algorithmus“ gleichbedeutend mit Berechnung selbst
  • Ideale Dinge sehen meist wie Bäume aus, aber Strukturen in der realen Welt sind, selbst wenn sie gut geordnet sind, normalerweise gerichtete azyklische Graphen
    Schon ab einigen Dutzend Knoten ist es meist schwierig, sie planar zu machen oder mit wenigen Kreuzungen und guter Gruppierung verwandter Knoten so darzustellen, dass sie fast planar wirken
  • Ich denke, das größere Problem ist, dass wir an die Illusion gewöhnt sind, alles sei hierarchisch
    Tatsächlich muss das Zeichnen von Graphen Dinge miteinander versöhnen, die fast nie hierarchisch sind, und es ist schwer, mathematisch präzise festzulegen, bis wohin etwas als Hierarchie gelten soll. Je weniger Annahmen man über die zugrunde liegende Graphstruktur macht — etwa über Zusammenhang, Zyklenfreiheit oder Sparsity —, desto schlimmer wird dieses Problem
    Wenn man in der Praxis eine UI baut, die mit Graphen interagiert, kann man meist eine oder zwei Ebenen von Meta-Hierarchie festlegen oder erzwingen, um Clustering zu ermöglichen. Dadurch lässt sich der Einfluss von Hairball-Knoten verringern, die das Layout ruinieren, und zugleich die Anzahl der Knoten reduzieren, was auch die Rendering-Performance verbessert. Für das Layout kann man fCOSE verwenden, wofür es auch eine Cytoscape.js-Implementierung gibt
  • Wenn man sich Diagramme neuronaler Netze ansieht, wird sehr deutlich, wie Visualisierung großer Graphen völlig unverständlich werden kann

• Ich halte die zentrale Beobachtung „Es gibt zu viele Implementierungsoptionen“ nicht für völlig zutreffend.
  Tatsächlich könnte eine Bibliothek alle geeigneten Graph-Repräsentationen implementieren, für jede Repräsentation den performantesten Algorithmus bereitstellen und Konvertierungen zwischen den Repräsentationen anbieten. Diese Konvertierungen wachsen proportional zur Zahl der Repräsentationen und sind sowohl in der Implementierung als auch in der Nutzung einfach, also für Maintainer wie Nutzer eine durchaus vernünftige Belastung.
  Zusätzlich könnte sie Import-/Export-Konvertierungen aus Standardbibliotheks-Datentypen und gängigen Idiomen bereitstellen. Speicher- und Konvertierungskosten sind gering, und in 99 % der Anwendungsfälle lässt sich der Overhead der Datenkonvertierung sowohl bei RAM als auch CPU vermutlich ignorieren.
  Das erinnert mich auch an den Spruch: „Die harte Wahrheit bei Google ist, dass man am Ende nur protobufs von einem Ort zum anderen verschiebt.“
  https://news.ycombinator.com/item?id=20132880

  • Das klingt dann nach einer riesigen Bibliothek, und ich bin nicht sicher, ob ich sie in meiner Arbeit verwenden würde. Ich arbeite viel mit Graphen, aber meine Erfahrung ist ähnlich wie die der Leute, die der Autor interviewt hat.
    Am Ende implementiert man Graphen immer wieder neu. Performance ist wichtig, und die vorhandenen Graph-Bibliotheken, die ich gesehen habe, konnten die Regelmäßigkeit unserer Datensätze nicht ausnutzen. Wir verwenden zum Beispiel einen append-only DAG, bei dem fast alle Knoten nur eine Kante haben, die auf den zuletzt hinzugefügten Eintrag zeigt, sodass intern Run-Length-Encoding möglich ist.
    Ich habe auch keine allgemeine Graph-Bibliothek gesehen, die die benötigten Abfragen unterstützt. Besonders wichtig ist dabei eine Subgraph-Diff-Funktion.
    Außerdem ist eine maßgeschneiderte Implementierung gar nicht so viel Arbeit. Graphen lassen sich viel leichter neu implementieren als B-Bäume, und eine einfache Implementierung braucht nur ein paar Dutzend Zeilen. Selbst unsere hochoptimierte Bibliothek mit unterstützenden Algorithmen kommt nur auf ein paar hundert Zeilen.
    Eine Möglichkeit, die Daten in ein Standardformat zu exportieren, wäre praktisch, aber in unserem Anwendungsfall würde das Einbinden einer Bibliothek wohl mehr Probleme schaffen als lösen.

• Eine Anwendung, die mir oft als fehlend einfiel, ist Excel für Graphen.
  So wie Excel für tabellarische Daten: ein Werkzeug für Daten, die in den RAM passen, also groß genug, dass man einen Computer braucht, aber nicht so groß, dass ein Rechenzentrum nötig wäre; eines, das viele Algorithmen und Visualisierungen „gut genug“ implementiert und sich ohne Programmierkenntnisse nutzen lässt.
  Wie im Artikel gesagt, sind viele reale Probleme Graph-Probleme — warum sollten dann nur Programmierer Werkzeuge haben, um sie zu lösen?

  • Ich habe das Gefühl, der Artikel zieht zu schnell ein Fazit. Viele andere Probleme kann man genauso beliebig komplex und schwierig machen, wenn man nur weitere Anforderungen hinzufügt.
    Trotzdem gibt es für die meisten Anwendungsfälle passende Datenstrukturen und Standardbibliotheken, und wenn die Anforderungen besonders scharf sind, baut man eben eine maßgeschneiderte Lösung.
    Der Artikel behauptet, Graphen seien oft zu groß, aber wenn man Leute fragt, die tatsächlich mit Graph-Algorithmen arbeiten, bekommt man leicht genau diesen Eindruck. Die meisten Programmierer und Nutzer werden vermutlich nur mit wirklich kleinen Graphen arbeiten.
  • Ich denke, nur Programmierer und Mathematiker modellieren solche Probleme als Graphen.
    Ich glaube nicht, dass normale Nutzer in zufälligen realen Problemen Graphen sehen. Was ich bei der Arbeit in Großunternehmen gelernt habe: Mit genug Mühe kann alles zu einer Excel-Tabelle werden.
  • Es ist zwar nicht genau das, worum gebeten wurde, aber https://gephi.org/ implementiert viele Algorithmen zur Graph-Visualisierung.
    https://strlen.com/treesheets/ kommt Excel für Baumdaten ziemlich nahe.
  • Der Artikel untermauert den Punkt „Viele reale Probleme sind Graph-Probleme“ nicht wirklich.
    Zum Beispiel heißt es, man könne das Internet als Graph modellieren, aber selbst wenn das stimmt, ist unklar, was daraus folgt. Das Internet kann auf viele Arten dargestellt werden, und es ist nicht offensichtlich, dass eine Darstellung als Graph im Allgemeinen nützliche technische Implikationen hat.
    Man könnte mit ähnlich überzeugender Rhetorik behaupten, die ideale Darstellung zur Gewinnung nützlicher Informationen sei stattdessen eine Blackbox-Matrixkodierungsfunktion, die beliebige Eingaben auf konsistente Ausgaben abbildet — also ein neuronales Netz.
    Für Firmen wie Google mag das eine Idee im Wert von Milliarden Dollar sein, aber das gesamte Internet ist für viele Menschen kein Graph-Problem, und durch die Darstellung als Graph wird nicht automatisch vieles gelöst.
    Menschen, die reale Probleme auf Papier als Graphen lösen, sind selten. Tabellen werden ständig verwendet. Graphen sind häufig, aber Graph-Probleme sind es nicht.
  • Ich glaube, der Kern dabei ist VR.
    In anderen Kommentaren wurde schon gesagt, dass Graph-Visualisierung schwierig ist, aber 3D-Oberflächen bieten viel mehr Raum. Als der VR-Boom begann, fragte ich mich: „Was ist das Excel von VR?“ Microsofts Antwort war offenbar: „2D-Tabellen, die im 3D-Raum schweben.“ Ich halte das für Unsinn. Ich denke, es sind Graphen.
    Wer das gemeinsam erkunden möchte, kann mir unter meinem Benutzernamen at gmail.com schreiben.

• Graph-Typen gibt es schon seit ziemlich langer Zeit.
  In Erlang gibt es https://www.erlang.org/doc/man/digraph.html und https://www.erlang.org/doc/man/digraph_utils, und wenn man eher mengentheoretische Operationen ausführen möchte, gibt es auch https://www.erlang.org/doc/man/sofs.html.

  • Gegen Ende des Artikels wird Erlang kurz erwähnt.
    Dort heißt es: „Ich habe mit Erlang und SWI-Prolog zwei weitere Sprachen mit einem Graph-Typ gefunden. Da ich mich mit beiden nicht gut auskenne, kann ich nicht sagen, wann sie hinzugefügt wurden, aber Erlang hatte ihn jedenfalls schon vor 2008. Ich habe jemanden aus dem Erlang Core Language Steering Committee kontaktiert, aber keine Antwort erhalten.“
  • Auch für Elixir gibt es eine ziemlich gute Graph-Bibliothek: https://hexdocs.pm/libgraph/api-reference.html
    Ich habe sie einmal zur Abhängigkeitsauflösung verwendet, um die Reihenfolge von Aufgaben zu bestimmen.
  • Mich würde interessieren, wie flexibel das in verschiedenen Situationen ist und wie gut die Performance ausfällt.