GDR: A Visualization Tool for Graph Algorithms

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


Matthias Stallmann and Prashant Hebbar; 1989, 2001, 2005, 2007; version 1.2.9

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:

New in this version:

Known Deficiencies:

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 or copied: the zip file is /afs/eos/courses/csc/csc230/common/www/

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):

breadth-first search of a directed graph; vertex labels show distance from the start vertex (contributed by Josh Blomberg, CSC 505, Spring 2005).
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
actually not an animation, but the program creates a directed, rooted, complete binary tree of a given height
a program to check the validity of a DFA (does every state have a unique transition for each alphabet symbol)
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
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.
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's minimum spanning tree algorithm (contributed by Josh Blomberg, CSC 505, Spring 2005).
animates the Hopcroft-Ullman O(n log n) algorithm for DFA minimization.
a simple tool to print the logical representation of a graph in an easy to read format.

Matthias Stallmann (Matt underscore Stallmann at ncsu dot edu)
Last modified: Thu Jun 28 16:36:54 2007