I finally handed in the final documentation of my interdisciplinary research project (IDP) about the visualization of advanced graph algorithms and am thus officially done with my studies. Please have a look at the demo.

Abstract

This interdisciplinary project deals with the vivid visualization of advanced graph algorithms. In particular, algorithms to solve two distinctive problems in discrete math are considered. Namely the maximum flow problem as well as the shortest path problem with resource constraints. For efficiency reasons, one often employs advanced graph algorithms to solve above problems. The maximum flow problem is solved using the efficient push-relabel algorithm. To solve the shortest path problem with resource constraints, we employ a generic label-setting algorithm which follows the dynamic programming principle. Both algorithms carry a lot of state variables and are thus not easy to understand intuitively. An additional visualization layer with an intuitive representation of all state variables and state transitions during algorithm execution was developed. It displays the height function of each node in case of the push-relabel algorithm or the pareto frontier of all labels resident in a certain node in case of the label-setting algorithm. To achieve the goal of a high interactivity, we replaced the previous Canvas based graph visualization code with a new implementation based on SVG, using D3.js, a JavaScript library for producing dynamic, interactive data visualizations in web browsers.