GDR: A Visualization Tool For Graph Algorithms

This report describes GDR (for Graph Drawing), a tool for editing graphs and animating graph algorithms. The motivation for animation tools comes primarily from the classroom; students often have difficulty mastering the formal concepts of graph theory, even though they usually have no trouble in following the associated visual intuitions. An appropriate animation tool can provide an invaluable link between formalism and graphical intuition, since students are given the opportunity to see how a formal presentation of a graph algorithm directly translates into visually intuitive operations on graphs. For this reason, animation systems can also play a very useful research role as testbeds for prototyping new algorithms and for testing conjectures about graphs. The design of GDR was strongly influenced by our desire for the tool to be easyto -use (even by relatively inexperienced programmers), portable, and flexible. Our approach was to develop GDR as a tool rather than a self-contained system, so that it is easily modified and simple to interface with other software. This has led to two approaches to using GDR in conjunction with other tools. In the first, GDR functions as a graph editor; users create graphs using the tool, save them in files, and feed the files as input into the other tools. This mode of interaction only requires that front-ends be written for the other tools that can parse the (very simple) output generated by GDR. The second mode of interaction is object-oriented; GDR provides a high-level interface to graph objects that programmers can write programs to manipulate (using calls to functions implemented in GDR). Users of GDR can then create graphs and apply the programmer-supplied routines to these graphs. Moreover, GDR is written in C and uses the libr..