Engineering a Fast and Adaptive Graph Algorithms Library

Many algorithmic problems can be modelled with graphs, i.e. abstract networks of nodes and edges. While several open source graph libraries such as NetworkX, OGDF.net and Boost.Graph exist today for such algorithms, their main purpose is to provide the widest possible choice of graph algorithms, rather than implementations highly optimised for speed. Thus, state-of-the-art implementations of graph algorithms are still mostly written in proprietary code and data structures to ensure competitiveness and to scale appropriately with the input size. In this master thesis, a new graph library will be designed and implemented that highly optimises elementary algorithms (such as depth-first search and minimal edge pruning) in terms of computation time. This will be done from an algorithm engineering perspective, supported by continuous profiling and testing of the written code, and adaptive to the minimum resources required by the algorithms (e.g. in LEDA).

This Master’s thesis therefore requires

• Expertise in C++ (stackoverflow is your preferred place to stay and you know templates, memory alignment in std, …),
• the ability to write efficient C++ code for graph data structures and algorithms, using profilers and computational time tests,
• Knowledge of graphs and interest in graph theory and algorithms.

The results of this implementation are to be made available open source and cross-platform. If you are interested in this work, please contact me by email.