An HTML5-based application for demonstrating graph algorithms

OData support
Supervisor:
Dr. Katona Gyula
Department of Computer Science and Information Theory

The visualization tools available for the graph algorithms featured in our university’s computer science education are not ideal: they are not always accessible, they might be inconsistent with the way we teach these algorithms, and they don’t provide a common user interface. In my thesis I create an application in HTML5 and Javascript which provides a solution to these problems. The application can demonstrate the workings of several basic graph algorithms, and provides sophisticated tools for interaction which are not common in similar applications. The list of included algorithms contains Prim’s, Kruskal’s and Borůvka’s methods for finding minimal spanning trees, breadth-first and depth-first search, the Ford-Fulkerson method, the PERT method, Floyd’s, Dijkstra’s and the Bellman-Ford algorithm for finding shortest paths, and the Hungarian method for finding a maximal matching in bipartite graphs.

As part of our work we collected results from projects with similar aims, and tried to show solutions to their shortcomings and weaknesses. We also examined the most important research results concerning the effectiveness of visualization tools in computer science education, and we’ve adjusted our goals in accordance with their findings.

The resulting application is supporting multiple languages, and due to its open source nature and generic modules it can be easily adopted and developed further by others.

The latest version of the application is publicly available at http://cs.bme.hu/~diotomi/graf/

Downloads

Please sign in to download the files of this thesis.