C++ Graph mit Boost
Dieser Artikel zeigt wie man einen C++ Graph mit Boost implementiert. Um meine fiktive Graphstruktur für einen Performance Test umzusetzen benutze ich die Graph Bibliothek von Boost. Die ist effizient, man muss sich aber erst einmal einarbeiten. Dieser Artikel ist die Fortsetzung meins C++ Graph Performance Test Artikels in dem ich nur die normale Klassenhierarchie abgebildet habe.
C++ Graph mit Boost
Die Boost Bibliothek ist neben der STL die interessanteste Sammlung an Datentypen für die C++ Programmierung. Mit der GBL steht eine alte, aber sehr effizient programmierte, erprobte und generische Bibliothek für die Entwicklung von Graphen bereit. Ich habe diese verwendet um das zuletzt vorgestellte Beispiel als Graph implementiert. Den Source Code findet man wie immer auf meiner GitHub Seite.
Implementierung
Die erforderlichen 4 Funktionen wurden mittels statischer Methoden in der GraphFactory Klasse implementiert:
GraphFactory::create(); GraphFactory::findPlayer(graph, randomName); GraphFactory::listRandomTeam(graph); GraphFactory::moveRandomPlayerToRandomTeam(graph);
Das Factory Pattern wurde durch diesen Ansatz um Funktionalität erweitert, ein Umstand der in einem Produktivcode besser umgesetzt werden kann. In der Testimplementierung ist der komplette Graph relevante Code in der GraphFactory implementiert. In den Dateien GraphFactory.h und GraphFactory.cpp findet man dazu alles notwendige.
boost::graph
Die boost Bibliothek erlaubt eine flexible Implementierung eines Graphen.Für meine zwecke habe ich folgende Typen definiert
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperty> Graph; typedef boost::graph_traits::vertex_descriptor vertex_t; typedef boost::graph_traits::vertex_iterator vertex_iterator; typedef boost::graph_traits::edge_iterator edge_iterator; typedef boost::graph_traits::in_edge_iterator in_edge_iterator; typedef boost::graph_traits::out_edge_iterator out_edge_iterator;
Die Graphenbibliothek von boost bietet 3 Container an um einen Graphen abzubilden. Ich habe mich für die am öftesten verwendete adjacency_list entschieden. Bei der Definition meiner Graphen Struktur Graph gebe ich an, welche Datenstruktur für Verbindungslinien und Punkte verwendet werden sollen. Standardmäßig wird jeweils ein std::vector verwendet, es können also Duplikate abgespeichert werden. Mit boost::vecS verwende ich genau das. Man könnte aber auch beispielsweise boost::setS verwenden um diese Duplikate zu verhindern. Weiters sind übrigens auch boost::listS, boost::mapS oder boost:hash_setS mögliche Datenstrukturen. Der dritte Parameter des Templates ist die Art, wie Verbindungen zwischen Knoten gespeichert werden. Ich verwende boost:bidirectionalS, deshalb kann man Knoten vorwärts und rückwärts durchlaufen (wie in einer doppelt verketteten Liste). Die Alternative wäre boost:unidirectedS. Im letzten Parameter definiere ich noch ein eigenes Format für einen Vertex (Knoten im Baum). Die weiteren Typen sind nur Kurzschreibweisen.
Das selbst definierte Vertex Format wird in folgender Klasse abgebildet:
class VertexProperty
{
public:
VertexProperty(int id = -1, Node_type type = Node_type::UNKNOWN) : id(id), type(type) { }
VertexProperty(int id, Node_type type, GraphData data) : id(id), type(type), data(data) { }
std::string toString() const
{
std::ostringstream oss;
oss << *this;
return oss.str();
}
int getVertexID() { return id; }
Node_type getType() { return type; }
GraphData getData() { return data; }
private:
friend std::ostream& operator<<(std::ostream& os, VertexProperty const& v) {
return os << "id " << v.id << " type " << v.type;
}
int id;
Node_type type;
GraphData data;
};Jeder Knoten hat eine eindeutige id, welche im Konstruktor initialisiert wird. Zusätzlich hat so ein Knoten auch einen Typ, in meinem speziellen Fall für die Anforderung sind das:
enum class Node_type { COUNTRY, LEAGUE, TEAM, PLAYER, UNKNOWN };Jeder dieser Typen wird ganz unterschiedliche Daten enthalten. Diese Daten werden in der GraphData Struktur gespeichert, welche wiederum wie folgt definiert ist:
using GraphData = std::shared_ptr;
Das heißt man kann den Pointer auf ein beliebiges Objekt, welches von GraphDataFacility erbt in den Knoten hängen. Damit verknüpft man den Graphen mit den Daten im Speicher.
Benchmark
Der Benchmark zeigt sehr schön auch bei kleiner Datenstruktur und wenigen Operationen auf den Graph, dass dieser im Vergleich zur Implementierung in einer Objekthierarchie effizienter ist. Die Effizienz ist in diesem Fall die Prozessorzeit, die benötigt wird. In meinem Fall benötigt der Graph im Speicher jedoch etwas mehr Platz.
Die Klassenhierarchie auf meinem Laptop im Release Modus:
Im Vergleich dazu für die selben Abfragen auf den Graphen:
Bei deutlich höherer Nutzung des Hauptspeichers ist die Zugriffszeit wesentlich kürzer. Man darf dieses Ergebnis übrigens nicht überbewerten oder gar skalieren. Der Graph besteht aktuell hauptsächlich aus seiner Struktur. Speichert man umfangreichere Daten, dann relativiert sich der Unterschied zur Klassenhierarchie sehr schnell und dieser Unterschied ist kaum noch messbar.
Fazit
Ich habe euch gezeigt wie man einen C++ Graph mit Boost implementiert. Mein praktisches Beispiel zeigt sehr eindrucksvoll um wie viel schneller die Zugriffszeit auf die Datenstrukturen mit einem Graphen ist.
