GDR: A Visualization Tool for Graph Algorithms

GDR (Graph DRawing) tool -- developed by Matthias Stallmann, Rance Cleaveland, and Prashant Hebbar.

©COPYRIGHT

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program (file COPYING.txt); if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

We have the following additional requests:

• that any publications or software for which this program was useful give credit by referring to the article "GDR: A Visualization Tool for Graph Algorithms" by M. Stallmann, R. Cleaveland, and P. Hebbar in Computational Support for Discrete Mathematics (Dean and Shannon, editors; AMS, 1994), pp. 17-28;
• that any modifications that improve, update, or build upon this program be reported and made available to us ( matt_stallmann AT ncsu.edu).

• Four new animations: dfs_scc (strongly-connected components) supersedes dfs_d, dijkstra (does either a minimum spanning tree algorithm or a single-source shortest-paths algorithm) supersedes prim., bfs (breadth-first search), and kruskal (Kruskal's minimum spanning tree algorithm). The last two were contributed by Josh Blomberg, CSC 505 student, Spring 2005.
• Move mode now works with either the left or middle mouse button (allowing operation with a one-button mouse).
• The pop-up menu can be activated by selecting POP MENU on the panel and using the left mouse button (the right button also still works; again, this allows operation with a one-button mouse).
• Keyboard shortcuts for all menu options are displayed on the menu (capital letters in parentheses --- the lower-case equivalents also work).
• A new menu option, RE-(I)NIT allows user to reset the display attributes of a graph if an animation fails to clean up after itself (labels on vertices and edges are displayed only if they have non-empty content -- user needs to decide whether that content needs to be saved).

Known Deficiencies:

• Move mode displays only a black dot for the item being moved; cross-hairs would be better, but ultimately the display needs to "rubber band" items and show their progress (this was too slow when GDR was first developed, but should be reasonably fast now).
• There needs to be a way to cancel a request to read, clear, init, save, or quit, with options to save before quitting, etc. In fact, all the pop-up boxes are rather crude by modern standards.

Documentation for the user interface is available here (slightly outdated -- see the notes about new features above).

Documentation for programmers (incomplete) is also available.

A "zipped" version of the new code may be downloaded at http://courses.ncsu.edu/csc230/common/GDR-1.2.9.zip or copied: the zip file is /afs/eos/courses/csc/csc230/common/www/GDR-1.2.9.zip.

Documentation for GDR developers, in the form of a doxygen web site is also available to help with code browsing.

This directory contains files for the GDR graph editing tool and various animations that have been written. The file Makefile contains instructions for compiling all the existing animations (and a list of the animations themselves). Source code is contained in files *.[ch]. The *.tex files contain documentation for users of GDR (programmer_doc.tex is not finished; it attempts to explain how a programmer can implement other animations on top of GDR).

The main GDR code is in the following files (a brief description of each is given):

All.h -- include this file to get everything needed by any internal GDR module

Defs.h -- data structures, constants, and macros internal to GDR

Display.h -- GDR functions that alter the display of a graph

Gdr.c -- implementations of functions required by the GDR programmer and some of their helpers.

Gdr.h -- the file to be included in animation programs using GDR (all other necessary includes emanate from here)

Geometric.h -- GDR functions that access and change geometric attributes

Globals.h -- specifications for global variables used by GDR

InOut.c -- GDR input and output routines

List.h -- routines for manipulating lists of edges

Logical.h -- GDR functions accessing and/or manipulating logical graph attributes.

Macros.h -- macros and typedefs for GDR programmers (some of the macros are advertised as functions)

Main.c -- main GDR program and supporting functions

Misc.h -- miscellaneous programmer functions in GDR

Panel.c -- routines associated with the side panel (manipulation of the panel itself or functions activated by the panel)

Prototypes.h -- prototypes of functions internal to GDR

Settings.h -- compile-time constants that can be customized for GDR

Text.c -- routines for manipulating text windows

Utilities.c -- routines that perform low-level operations having to do with display or geometry

alphabet.c -- functions for manipulating edge labels of graphs representing finite automata

alphabet.h -- header for alphabet.c (functions for manipulating edge labels of graphs that represent finite automata)

bfs.c -- breadth-first search (contributed by Josh Blomberg, CSC 505, Spring 2005)

bicon.c -- biconnectivity algorithm for undirected graphs

btree.c -- a tool for creating binary trees for GDR (the animation draws them automatically to fit into a window).

chk_dfa.c -- check a graph to see if it represents a valid dfa

dfa.c -- a DFA simulator

dfs_scc.c -- depth-first search for directed graphs, using the detailed algorithm of Cormen, Leiserson, and Rivest (Introduction to Algorithms, first edition, p. 478). Also does strongly connected components.

dijkstra.c -- Dijkstra's shortest path and minimum spanning tree algorithms (the animation asks the user which to do).

general.h -- header file with definitions of general interest, used by the automata animations (most of these can be replaced by C constructs and are no longer needed).

kruskal.c -- Kruskal's minimum spanning tree algorithm (contributed by Josh Blomberg, CSC 505, Spring 2005)

minimize.c -- DFA minimization algorithm

print_logical.c -- print logical representation of the graph

Animations that have been implemented so far are (each can be created using the command make name, where name is listed below):

bfs

breadth-first search of a directed graph; vertex labels show distance from the start vertex (contributed by Josh Blomberg, CSC 505, Spring 2005).

bicon

biconnectivity algorithm for undirected graphs. DFS always starts at vertex 0, vertex labels show preorder and low numbers, edge labels show biconnected component to which the edge belongs

btree

actually not an animation, but the program creates a directed, rooted, complete binary tree of a given height

chk_dfa

a program to check the validity of a DFA (does every state have a unique transition for each alphabet symbol)

dfa

a DFA simulator. Vertex 0 is the start state. Transitions are shown by highlighting the transition edge and moving a label containing the rest of the string to the new state

dfs_scc

Depth-first search on directed graphs, using the description of Cormen, Leiserson, and Rivest. Tree edges are highlighted. Other edges are labeled B, C, or F (back, cross, or forward). There is also an option to find strongly connected components of the graph.

dijkstra

animates the Dijkstra shortest path algorithm and the Prim/Dijkstra minimum spanning tree algorithm (using the implementation of Baase). Edge labels are interpreted as integer costs. At each stage, the fringe edges are highlighted as are the tree vertices. At the end, all non-tree edges are deleted and the shortest path or minimum spanning tree is shown.

kruskal

Kruskal's minimum spanning tree algorithm (contributed by Josh Blomberg, CSC 505, Spring 2005).

minimize

animates the Hopcroft-Ullman O(n log n) algorithm for DFA minimization.

print_logical

a simple tool to print the logical representation of a graph in an easy to read format.