Engineering a Fast and Adaptive Graph Algorithms Library

Supervisor: Jens M. Schmidt

An abundance of problems may be solved by modeling them using graphs, i.e. as abstract network of vertices and edges. While there exist already many efficient open-source libraries designated for graph algorithms like NetworkX, OGDF.net and Boost.Graph, the main focus of these libraries is to provide a wide range of functionality, not highly optimized code. Indeed, state-of-the-art implementations of graph problems use still mostly proprietary code and data structures in order to be competitive in speed and to scale well with the input size.

In this master thesis, we design and implement a new library on very basic graph algorithms (like depth first search and minimum edge-cuts) with a focus on speed and highly optimized platform-independent code. This shall be done from an algorithm engineering perspective, be supported by continuous testing and profiling of the written code, and adaptive to the particular algorithm that is called, i.e. limiting the resources to the bare minimum demand of the respective algorithm (as done in e.g. LEDA). This thesis therefore needs you to have

  • a profound knowledge of C++ (stackoverflow is most likely your regular friend, and you know templates, memory alignment in std, ...),
  • skill in writing efficient C++ code for graph data structures and algorithms, and in profiling and testing highly optimized code
  • familiarity with graphs, and interest in graph theory and algorithms.

The resulting implementation of this thesis shall be made available open-source and platform-independent. If you are interested in this thesis, please contact me by email.

 


 

Betreuer: Jens M. Schmidt

Viele algorithmische Probleme lassen sich mit Graphen, d.h. mit abstrakten Netzwerken aus Knoten und Kanten, modellieren. Während heutzutage mehrere quelloffene Graphbibliotheken wie NetworkX, OGDF.net und Boost.Graph für solche Algorithmen existieren, stellen diese als Hauptzweck eine möglichst breite Auswahl an Graphalgorithmen bereit, und nicht etwa auf Geschwindigkeit hochoptimierte Implementationen. So sind state-of-the-art Implementationen von Graphenalgorithmen meist trotzdem in proprietärem Code und Datenstrukturen geschrieben, um die Kompetitivität sicherzustellen und um geeignet mit der Eingabegröße zu skalieren.

In dieser Masterarbeit soll eine neue Graphenbibliothek entworfen und implementiert werden, die elementare Algorithmen (wie Tiefensuche und minimale Kantenschnitte) im Hinblick auf die Rechenzeit hochoptimiert. Dies soll aus der Perspektive des Algorithm Engineering erfolgen, von kontinuerlichem Profiling und Testen des geschriebenen Code unterstützt sein, und adaptiv zu den jeweils von den Algorithmen minimal benötigten Ressourcen sein (wie z.B. in LEDA). Diese Masterarbeit benötigt daher

  • Expertise in C++ (Stackoverflow ist Ihr bevorzugter Aufenthaltsort, und Sie kennen Templates, Memory alignment in std, ...),
  • die Fähigkeit, effizienten C++-Code für Datenstrukturen und Algorithmen von Graphen zu schreiben, und dafür Profiler und Rechenzeittests einzusetzen,
  • Kenntnisse von Graphen und Interesse an Graphentheorie und Algorithmen.

Die Ergebnisse dieser Implementierung sollen quelloffen und plattformübergreifend zur Verfügung gestellt werden. Bei Interesse an dieser Arbeit kontaktieren Sie mich bitte per Email.