Visualization of advanced graph algorithms
This IDP aims at extending the previous HTML5 framework that was developed at the chair to support advanced graph algorithms:
- the Tarjan-Goldberg push-relabel algorithm to solve the maximum flow problem
- a Label Setting algorithm to solve the shortest path problem with resource constraints (SPPRC)
In particular, the goal was to provide an intuitive visual representation of all state variables and state transitions during the algorithm execution. Since both algorithms carry a lot of state information, an additional visualization layer, linked to the original graph layer was developed. This second layer displays:
- the height function of each node in case of the Tarjan-Goldberg algorithm
- the pareto frontier of all labels resident in a certain node in case of the Label Setting algorithm
To achieve the goal of a highly interactive and easily extensible user experience, we replaced the old canvas based graph visualization code, which was really hard to extend, with a new implementation using the Stanford development D3.js (or just D3 for Data-Driven Documents), a JavaScript library for producing dynamic, interactive data visualizations in web browsers. It makes use of the widely implemented SVG, HTML5, and CSS standards.
During the development process, we also migrated the existing graph editor to the new technologies, it now easily supports
- an arbitrary number of resources defined on edges and nodes
- download and upload functionality
- cropped SVG export of graphs
This talk is not only suitable to mathematicians found of graph problems, but to anyone who wants to leverage today's web standards to express his interactive visualization needs.