GDR (Graph DRawing) tool -- developed by Matthias Stallmann, Rance Cleaveland, and Prashant Hebbar.
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:
matt_stallmann AT ncsu.edu
).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.
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:
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):
Matt underscore Stallmann at ncsu dot edu
)
Last modified: Thu Jun 28 16:36:54 2007