Eine moderne (ähnliche) C++-Bibliothek zur Darstellung und Manipulation von Graphen

An meinem alten Arbeitsplatz hatte ich gemischte Erfahrungen mit der Grafikbibliothek von Boost ; Ich war nicht die Person, die hauptsächlich mit diesem Code arbeitete, aber wir erlebten Zerbrechlichkeit, Dinge, die sich unter unseren Füßen veränderten, und die Notwendigkeit, den Zustand aus nicht ausreichenden Gründen wiederholt zu aktualisieren. Ja, ich weiß, das klingt ein bisschen vage, aber der Punkt ist, dass ich mir die Alternativen ansehen möchte.

Also suche ich nach einer Grafikbibliothek, die:

  • Repräsentiert ungerichtete und gerichtete Graphen.
  • Hängt überhaupt nicht oder zumindest nicht wesentlich von Boost ab.
  • Zeigt sowohl bei statischen Diagrammen (dh Suchen, Nachschlagen, Iterieren mit und ohne Filter usw.) eine gute Leistung.
  • Zeigt eine gute Leistung, wenn Graphen manipuliert werden – Hinzufügen, Entfernen, Verschieben und Aktualisieren von Kanten und Scheitelpunkten.
  • Skaliert gut zu großen, aber nicht unbedingt riesigen Graphen, die eher spärlich als dicht sind - sagen wir, Zehntausende von Scheitelpunkten und Hunderttausende von Kanten.
  • Stört nicht bei sehr ungleichmäßigen Scheitelgraden.
  • Freundlich gegenüber dem Anreichern von Kanten und Knoten mit zusätzlicher Semantik (ja, wieder, hier vage sein, um Antworten nicht im Voraus auszuschließen).
  • Kostenlos und Open-Source .
  • Ist in C++11 und höher geschrieben ... weißt du was? OK, keine strenge Anforderung, aber ich wäre diesen gegenüber sehr voreingenommen.

Es wäre auch schön, wenn es auch:

  • Lässt sich gut auf riesige Graphen skalieren.
  • Funktioniert sowohl auf spärlichen als auch auf dichten Graphen gut.
  • Ermöglicht es Ihnen, die zugrunde liegende Darstellung gemäß Ihren Leistungszielen zu konfigurieren.
  • Ist das nicht eines dieser Dinge, bei denen malloc() so aussieht, als gäbe es kein Morgen, und Sie in einem Labyrinth nervtötender Zeiger gefangen lässt.
  • Hat eine nicht so virale Lizenz.
  • Wird aktiv gepflegt.
  • Ist gut dokumentiert.
  • Ist weit verbreitet.
Es gibt auch dlib
@Antony: Ich glaube nicht, dass das alle meine Kriterien erfüllt ...
Entschuldigung, ich hatte es befürchtet, als ich eher einen Kommentar als eine Antwort gepostet habe. Ich habe die Boost Graph Library ein wenig benutzt, also fühle ich Ihren Schmerz :-(

Antworten (2)

Einige potenzielle Kandidaten oder potenzielle Kandidaten:

Könnte relevant sein:

  • LEMON oder Library for Efficient Modeling and O ptimization in Networks – Eine „ C ++-Vorlagenbibliothek, die effiziente Implementierungen allgemeiner Datenstrukturen und Algorithmen mit Schwerpunkt auf kombinatorischen Optimierungsaufgaben bietet, die hauptsächlich mit Graphen und Netzwerken verbunden sind.“ Hier ist eine Präsentation aus dem Jahr 2010 , in der LEMON beschrieben wird.
  • GGL , die G raph G rammar Library - . Hier ist das Handbuch .
  • Goblin - "Eine Werkzeugkette zur Handhabung von Graphen", einschließlich Code für graphenbezogene kombinatorische Optimierungsalgorithmen; Anordnung von Graphen im Raum (zB geschichtet, orthogonal), Graphenaufbau (?), Serialisierung zu/von Dateien, Scheitel- und Kantenattribute und Inzidenzstrukturen. Wahrscheinlich nicht C++ 11ish und auch nicht zu sehr mit Templates.
  • SNAP - The S tanford Network A nalysis P latform - scheint einerseits ziemlich auf eine bestimmte Anwendung fokussiert zu sein; Auf der anderen Seite könnte es eine ziemlich vollständige API zur Darstellung und Manipulation von Diagrammen haben. Es gibt auch einen Hinweis darauf, dass es möglicherweise auf einer anderen Grafikbibliothek auf niedrigerer Ebene basiert.
  • NGraph - Eine supereinfache, einzelne 23 KiB .hpp-Datei, Grafikbibliothek.
  • digraph - Eine C++11-Bibliothek für Digraphen, die für die Verwendung als Teil des Faust -Compilers für die Audiosignalverarbeitung ausgelegt ist.

Nicht relevant / eher nicht relevant:

  • LEDA - Ein Teil einer größeren Codebasis kombinatorischer Algorithmen und gleichnamiger Datenstrukturen. Dies ist kommerzielle Software, und sogar die kostenlose Edition ist Closed-Source (Sie können - keuchen - die Quelle von ihnen kaufen). Nein danke.
  • OGDF - Open G raph D rawing F ramework - Scheint sich mehr mit dem Layout zu befassen, dem Zeichnen von Graphen auf einer Ebene. Behauptet, ein FOSS-Ersatz für LEDA zu sein.
  • igraph - AC (wie in: nicht C++) Graphbibliothek, die für die Verwendung in der Netzwerkanalyse erstellt wurde. Behauptet, sich auf die Leistung für große, aber nicht riesige Graphen zu konzentrieren; und scheint sich über mehr als ein Jahrzehnt erheblich weiterentwickelt zu haben. GitHub-Seite . Es hat einige instabile API-C++-Bindungen namens igraphpp.
  • NoCycle - Eine Bibliothek zur DAG-Darstellung. Es verwendet eine kompakte (?) Darstellung einer Nachbarschaftskarte. Wahrscheinlich zu anders als das, was ich brauche, und ich glaube nicht, dass ich den Hype um seine Darstellung "abkaufe".
  • libcgraph - Teil des GraphViz- Graph-Layout-Projekts/Toolkits. Beachten Sie, dass es dort auch eine Komponente namens libgraph gibt - nicht sicher, welche welche verwendet.
  • GCT - G raph Class T emplates - Eine weitere Bare-Bones-Bibliothek mit einer Header-Datei.

Es ist nicht unmöglich, dass einige der C-Bibliotheken gut sind, aber ich glaube nicht, dass ich Zeit damit verbringen werde, sie in C++ zu packen, ganz zu schweigen von dem Mangel an Abstraktionen, die effektiv mit ihnen verfügbar wären.

Siehe auch die folgenden Stack Overflow-Fragen:

Es gibt ein sehr ernsthaftes Projekt zum Schreiben einer vorlagenbasierten, bereichsbezogenen Graphbibliothek als Vorschlag zur Ergänzung des C++-Standards. Es verbessert und erweitert Ideen von Boost Graph, indem es moderne C++-Einrichtungen und -Mechanismen (einschließlich umfassender Nutzung von Bereichen) nutzt.

Es ist noch nicht fertig, kann aber hier gefunden werden: https://github.com/pratzl/graph

Und der Vorschlag ist P1709R2 .

Eine moderne (ähnliche) C++-Bibliothek zur Darstellung und Manipulation von Graphen
AntwortenHierDatenschutz-Bestimmungen1y, 0v