Auf der Spur des verschwundenen Datentyps

Auf der Suche nach dem fehlenden Datentyp

• Ein Graph ist eine Menge von Knoten, die durch Pfeile (Kanten) verbunden sind.
• Knoten und Kanten können Daten enthalten.
• Im Software Engineering treten Graphen in vielen Formen auf, etwa als Paketabhängigkeiten, Internet-Links, Zustandsräume von Software, relationale Datenbanken, verkettete Listen, binäre Bäume und Hash-Tabellen.
• Auch in der Business-Logik werden Graphen genutzt, etwa für Verweise in Zitaten, Verkehrsnetze und soziale Netzwerke.
• Wer lange genug Software entwickelt, trifft wahrscheinlich überall auf Graphen.

Überlegungen zum Einsatz von Graphen

• Graphen sind nützlich, aber ihr Einsatz in echtem Code ist unerquicklich.
• In den meisten Mainstream-Sprachen gibt es keinen eingebauten Graph-Typ, in Standardbibliotheken ist er ebenfalls selten, und auch robuste Third-Party-Bibliotheken sind nicht zahlreich.
• Oft muss man Graphen selbst implementieren.
• Es gibt eine Lücke zwischen der Häufigkeit, mit der Software Engineers Graphen einsetzen könnten, und der Unterstützung dafür im Programmierökosystem.

Warum es keinen Graph-Typ gibt

Zu viele Designentscheidungen

• Es gibt viele Graph-Typen: gerichtete und ungerichtete Graphen, einfache Graphen und Multigraphen, Hypergraphen, Ubergraphs und weitere.
• Für jeden Typ muss entschieden werden, ob Knoten und Kanten IDs erhalten und welche Daten gespeichert werden sollen.
• Eine perfekte Graph-Bibliothek, die alle Möglichkeiten abdeckt, würde sehr viel Zeit erfordern.
• Die Performance von Graph-Algorithmen ist wichtig, und Spezialfälle sind relevant.
• Graph-Algorithmen korrekt zu implementieren ist schwierig.

Zu viele Implementierungsentscheidungen

• Selbst wenn man nur einfache gerichtete Graphen unterstützt, gibt es viele Möglichkeiten, einen Graphen intern darzustellen.
• Es gibt Kantenlisten, Adjazenzlisten, Adjazenzmatrizen, Mengen von Structs und weitere Speicherformen.
• Verschiedene Graph-Operationen haben je nach Darstellungsform unterschiedliche Performance-Eigenschaften.
• Je nachdem, ob ein Graph dünn oder dicht besetzt ist, ist eine andere interne Repräsentation optimal.
• Knotendaten, Kantendaten sowie verschiedene Arten von Knoten und Kanten zu implementieren, macht alles noch komplexer.

Performance ist zu wichtig

• Viele Graph-Algorithmen sind NP-vollständig oder noch schwieriger.
• Graphen können sehr große Probleme darstellen, und je nach Repräsentation und Implementierungsdetails des Algorithmus unterscheidet sich die Performance stark.
• Man braucht viel Kontrolle über Datenrepräsentation und Algorithmen.

Ein gemeinsamer Nenner

• Die Vielfalt an Graph-Typen, Repräsentationen und Algorithmen, die Sensibilität gegenüber Performance und die teuren Algorithmen auf großen Graphen sind Gründe dafür, dass Graph-Unterstützung nicht weit verbreitet ist.
• Das erklärt, warum Sprachen Graphen nicht in ihrer Standardbibliothek unterstützen.
• Es erklärt, warum Programmierer Third-Party-Graph-Bibliotheken meiden.
• Weil die Arbeit mit Graphen schwierig ist, möchte man außer in extremen Fällen gar nicht erst in Graphen denken.

Meinung von GN⁺

• Dieser Artikel liefert Einsichten dazu, warum sich Graphen in Programmiersprachen und Bibliotheken nicht als grundlegender Datentyp etabliert haben.
• Die Graphentheorie ist ein wichtiges Gebiet der Informatik und wird in vielen Bereichen angewendet, darunter Algorithmen, Netzwerkanalyse und Datenbanken.
• Um Graphen effektiv zu nutzen, sind Performance-Optimierung und die Wahl einer geeigneten Datenstruktur wichtig.
• Zu den Third-Party-Bibliotheken gehören NetworkX, Boost Graph Library und Graph-tool; sie können zur Lösung verschiedenster Graph-Probleme eingesetzt werden.
• Beim Einsatz von Graphen ist es wichtig, den zum Problem passenden Graph-Typ und Algorithmus auszuwählen, da dies direkten Einfluss auf die System-Performance hat.

[GN⁺]

Hacker-News-Kommentare

• Graphviz verfügt über eine eigene Graphbibliothek, die in anderen Projekten nicht verwendet wird. Das hat Vor- und Nachteile.

  • Auf Basis dieser Erfahrung litten sie an ihrem eigenen „Second-System-Syndrom“.
  • Sie entschieden, dass eine Graphbibliothek modular, typsicher und effizient sein sollte. Das ist vielleicht eine Variante von „gut, schnell, billig – wähle zwei“.
  • Modular bedeutet, dass sie eine Sammlung von Graphalgorithmus-Bibliotheken schreiben wollten, die unabhängig entwickelt und kompiliert werden können.
  • Typsicher bedeutet, dass sie Programmierfehler zur Compile-Zeit oder spätestens zur Link-Zeit erkennen wollten. Laufzeitfehler wollten sie nicht.
  • Effizienz bedeutet, dass der Zugriff auf Eigenschaften eines Graphen so günstig sein sollte wie der Zugriff auf ein Feld in einer C-Struktur.
  • Ob diese Ziele erstrebenswert sind, ist umstritten, aber genau das wollten sie. Da bekannte C++-Begründer in ihrem Labor waren, hofften sie auf Hilfe und beschlossen, C++ noch einmal eine Chance zu geben.
  • Gordon Woodhull, ein ehemaliger Praktikant, war ein hervorragender Programmierer und implementierte eine solche Graphbibliothek in Template-C++. Sie wurde über sourceforge auf https://www.dynagraph.org/ veröffentlicht.
  • Da andere nicht sicher waren, ob sie verstehen würden, wie der Code funktioniert, führten sie Code-Reviews mit den berühmten C++-Erfindern durch. Dabei stellten sie fest, dass sie möglicherweise über den Abgrund der Komplexität hinausgegangen waren.
  • Das war nicht Gordons Schuld, und er machte weiter und erledigte erfolgreich Arbeit an dynamischem Graphlayout, auch in Microsoft OLE. Rückblickend könnte dies ihr eigenes Projekt Xanadu gewesen sein.
  • Während sie sich darin vertieften, entstanden viele andere Dinge wie Gephi (Java) sowie NetworkX und NetworKit (Python).
  • John Ellson ist ein sehr talentierter Softwareingenieur, der Teile von Graphviz geschrieben hat und die Hauptanstrengung wiederbelebte.

• Wenn man in .NET entwickelt, sollte man die kleine, nicht besonders funktionsreiche Graphbibliothek Arborescence ausprobieren.

  • Ich glaube, dass diese Bibliothek eine gute Trennung zwischen Abstraktionen, Algorithmen und Datenstrukturen bietet.
  • Nutzer können Kanten mit eigenen IDs verwenden oder implizite Graphen nutzen, die sich on the fly entfalten.
  • Es können sowohl Adjazenz-Interfaces (ausgehende Nachbarn) als auch Inzidenz-Interfaces (ausgehende Kanten + Zielknoten) verwendet werden.
  • Die Bibliothek erzwingt keinen Kantentyp, stellt aber als Utility eine grundlegende Tail-Head-Paarstruktur bereit.

• Graphen sind keine Datenstruktur und kein Datentyp, sondern eine Abstraktion.

  • Im Grunde braucht man zur Definition eines Graphen nur eine Menge von Knoten und eine Nachbarschaftsfunktion.
  • Alles andere sind fallbezogene Einschränkungen.
  • Betrachtet man Hypergraphen, dann sind Graphen nur ein Spezialfall.
  • Aus Datenbankperspektive sind Graphen ein Problem der Query-Optimierung und Indexierung.

• Ich wurde oft gefragt, warum es in Programmiersprachen keinen eingebauten Graph-Datentyp gibt.

  • Ich freue mich, nun auf tiefergehende Analysen wie diesen Artikel verweisen zu können.

• Das zentrale Hindernis ist Folgendes:

  • Für einfache und kleine Graphprobleme ist es einfach genug, eine Adjazenzliste als Vektor von Vektoren zu programmieren.
  • Für komplexe und riesige Graphprobleme gibt es keine Möglichkeit, Leistung zu erzielen, außer die Graphimplementierung an das Problem anzupassen.
  • Es ist nicht klar, welche Art von Sprachunterstützung hier hilfreich wäre.

• Dieser Artikel beantwortet weitgehend auch die Frage, warum Graph-Algorithmen in Programmiersprachen nicht besser unterstützt werden.

  • Betrachtet man Graph-Unterstützung allgemein, ergeben sich breitere Fragen, etwa warum OGM nicht so populär ist wie ORM oder warum JSON weiter verbreitet ist als RDF.
  • Letztlich skaliert das unter Entwicklern wegen historischer Gründe und der Komplexität von Graphen nicht gut.

• Auch Werkzeuge zum Zeichnen von Graphen sind sehr enttäuschend.

  • Bei Graphen mit mehr als 500 Knoten sind die Ausgaben schwer verständlich oder unübersichtlich.
  • Es fehlt an Funktionen, die Graphen automatisch in hierarchische Strukturen organisieren und gute Interfaces zum Erkunden bereitstellen.

• Dieser Beitrag ist wirklich großartig.

  • Zur Kernbeobachtung „Es gibt zu viele Implementierungsoptionen“: Eigentlich stimmt das nicht.
  • In der Praxis können Bibliotheken alle geeigneten Graphrepräsentationen implementieren.
  • Man kann Algorithmen an die Repräsentation anpassen und von einer Repräsentation in eine andere konvertieren.

• Electric Clojure verwendet Clojure selbst (S-Ausdrücke) als Syntax zum Schreiben von Graphen.

  • Eine DSL zum Schreiben von Graphen muss Geltungsbereich, Kontrollfluss und Abstraktion ausdrücken, und das ist im Wesentlichen dasselbe wie eine Programmiersprache.

• Es gibt noch einen weiteren nützlichen Datentyp, nämlich Tabellen (wie Tabellen in einer Datenbank).

  • Es wäre ein Fortschritt für Programmiersprachen, wenn der Compiler die Implementierung der Datenstruktur auswählen würde.
  • Man verwendet abstrakte Strukturen (Sequenzen, Maps, Sets, Tabellen, Graphen usw.), und der Compiler wählt auf Basis des Programmprofils eine konkrete Implementierung aus.