Next: About this document ...
GDR Programmer Documentation
(last modification: 14 March 2002)
This document describes how to write an animated program for GDR.
A program implementing a graph algorithm is written in plain C with
macros and functions to access and animate the graph created by the user.
The declarations needed for interfacing with GDR are provided by an
#include "Gdr.h" statement.
The code that is to be executed by the user is written as a
parameterless procedure animat().
Examples of previously written animations can be found in files
bicon.c, dfa.c, dfs_d.c, nfa.c, and prim.c.
The first step is to code the graph algorithm in C using graph traversal
macros where appropriate.
GDR provides the following traversal macros (the definitions for these
are found in def.h:

for_adjacent(v,e,w) creates a loop whose body is executed once for
each outgoing edge e from vertex v  the vertex w is the other
endpoint of e (for undirected graphs, all edges incident to v are
traversed).

for_incoming_edges(v,e,u) traverses all edges e=(u,v) leding
into v (in the case of undirected graphs, this is identical to
for_adjacent).

for_all_vertices(v) accesses all valid vertices v

for_all_edges(e) accesses all edges e
In GDR a graph is a set of edges  multiple edges between the same two
vertices are allowed.
The above macros may not work correctly if the graph is modified in the
loop body, e.g. if edges are deleted. More careful implementation using
the functions first_out_edge and next_out_edge may be required.
Tables and list all the GDR functions
for accessing and changing graph structure.
Table:
Access to Logical Graph Attributes in GDR
max_vertex() 
returns the maximum vertex id possible
(current implementation does not guarantee that it's valid) 
is_valid_vertex(vertex:v) 
returns TRUE if v is a valid vertex,
FALSE otherwise (the vertex whose id is v may have been deleted) 
get_a_vertex() 
returns the first valid vertex in the graph 
are_edges_equal(edge:e1,e2) 
returns TRUE if the edges are
the same, FALSE otherwise 
head(edge:e) 
returns the vertex to which e is
directed (the second vertex to be added to e in case of an
undirected edge) 
tail(edge:e) 
returns the vertex from which e is
directed (the first vertex to be added to e in case of an
undirected edge) 
other_vertex(vertex:v,edge:e) 
returns the vertex that along with
v defines the edge e 
first_out_edge(vertex:v) 
returns the first outgoing edge
from vertex v (first edge on v 's adjacency list if
undirected graph) 
next_out_edge(vertex:v,edge:e) 
returns the next outgoing edge
after e from vertex v (to be used in conjunction
with first_out_edge for sequential access of adjacency
lists) 
first_in_edge(vertex:v) 
returns the first edge into vertex
v (for directed graphs; first edge on v's adjacency list
if undirected) 
next_in_edge(vertex:v,edge:e) 
returns the next edge after
e going into vertex v (analogous to
next_out_edge ) 
first_edge() 
returns the first edge from the list of all edges
in the graph 
next_edge(edge:e) 
returns the next edge after e
in the list of all edges 
vertex_label(vertex:v) 
returns the label of vertex v in
an allocated string 
edge_label(edge:e) 
returns the label of edge e in
an allocated string 

Table:
Changing Logical Graph Attributes in GDR
add_vertex(int:x,y;string:label) 
adds a new vertex and returns its id;
the vertex is drawn at position (x,y) and is given label as
its label 
add_edge(vertex:v1,v2;string:label) 
adds a new edge from v1 to v2 and returns its id;
label of the new edge is label 
delete_vertex(vertex:v) 
deletes vertex v and all incident
edges from the graph 
delete_edge(edge:e) 
deletes edge e from the graph 
change_vertex_label(vertex:v;string:label) 
changes the
label of v to label 
change_edge_label(edge:e;string:label) 
changes the label of
e to label 

Animations are created by changing the logical structure, geometry, or
display characteristics of a graph in response to actions taken by the
algorithm.
Simple animations can be created by highlighting vertices and edges, by
exposing or hiding their labels, or by changing the text of the labels.
The functions to do this are described in Table (the
functions for changing labels are described in Table ).
Table:
Access to Display Attributes in GDR
is_highlighted_vertex(vertex:v) 
returns TRUE
if the vertex v is highlighted 
is_highlighted_edge(edge:e) 
returns TRUE if the
edge e is highlighted 
is_exposed_vertex_label(vertex:v) 
returns TRUE if the
label of vertex v is exposed 
is_exposed_edge_label(edge:e) 
returns TRUE if the
label of edge e is exposed 
highlight_vertex(vertex:v) 
highlights vertex v, i.e.
makes its background white 
un_highlight_vertex(vertex:v) 
removes highlighting from vertex
v, i.e. makes its background black 
highlight_edge(edge:e) 
highlights edge e, i.e.
fattens all of the line segments representing e 
un_highlight_edge(edge:e) 
removes highlighting from edge
e, i.e. represents the edge as line segments of thickness 1 
expose_vertex_label(vertex:v) 
causes the vertex label of
v to appear on the display 
expose_edge_label(edge:e) 
causes the edge label of e
to appear on the display 
hide_vertex_label(vertex:v) 
causes the vertex label of v to be erased from the display 
hide_edge_label(edge:e) 
causes the edge label of e to
be erased from the display 

Table shows other useful functions for interacting with
the display of the graph.
Vertices and edges can be blinked (the delay of a blink is controlled by
a compiletime parameter BLINK_DELAY in gr.h).
Windows to display text can be created and manipulated.
Pauses for user response can be added using suspend_animation (a
general pause mechanism), get_xy_from_mouse (to query user for a
position), or select_vertex (to have user point to a vertex).
Table:
Miscellaneous Programmer Functions in GDR
blink_vertex(vertex:v,int:count) 
causes vertex v to blink (change from unhighlighted to highlighted and back)
count times 
blink_edge(edge:e,int:delay,count) 
causes edge e to blink
(details same as vertex blinking) 
print_graph_data(string:name;flag:append) 
outputs the
current graph, in GDR format, to file name;
if append is TRUE, the
existing file gets appended, else it is overwritten
(can be used for automatic generation of stills from animation) 
suspend_animation() 
gives control back to edit mode;
program execution is resumed when user clicks left in the RESUME ? window or presses q or Q 
create_text_window(int:x,y;string:message) 
creates a window
with upper left corner at
postion (x,y) and message written into it ( message
can have
multiple lines, delimited by \n ), and returns a window identifier
(type Window) 
write_text_window(Window:w,string:message) 
changes the
content of window w to message and causes window
w to appear (if hidden) 
hide_window(Window:w) 
makes window w disappear from view 
kill_window(Window:w) 
destroys the window w and unmaps
it in the process; warning: any further references to the window
indentifier w will result in
an X Window Protocol error. 
get_xy_from_mouse(int reference:x,y) 
prompts user to click
the mouse and the x and y coordinates are passed back by reference
(returns FALSE
if user hits
[ControlC] to abort, else returns TRUE) 
select_vertex() 
returns the id of a vertex selected by
left mouse click or NULL_VERTEX if user typed q
before clicking the mouse 
query(int: x,y; string:msg,ans) 
prints msg in a box at
position (x,y) and returns what the user typed through ans; the actual
value returned is a flag indicating a response other than C 

GDR also gives the programmer access to the geometry of the displayed
graph  for details, see Table .
Table:
Access to Geometric Attributes in GDR
add_vertex(int:x,y;string:label) 
adds a new vertex and returns its id;
the vertex is drawn at position (x,y) and is given label as
its label 
vertex_x(vertex:v) 
returns the xcoordinate of the vertex v 
vertex_y(vertex:v) 
returns the ycoordinate of the vertex v 
move_vertex_relative(vertex:v;int:d_x,d_y) 
moves the
vertex v to the right d_x units and down d_y
units (left and/or up if negative numbers are used); also
moves the associated edges; returns FALSE on error, else returns
TRUE 
edge_label_x(edge:e) 
returns the xcoordinate of the
label of edge e 
edge_label_y(edge:e) 
returns the ycoordinate of the
label of edge e 
move_edge_label(edge:e;int:x,y) 
moves the edge label of
e so that it is centered at point (x,y) 
window_width() 
returns the width of the graph display area 
window_height() 
returns the height of the graph display area 

Suppose an animated program for directed graphs
has been written in file alg.c.
It can be compiled and linked with GDR using the following commands
cc c I/usr/include/X11 alg.c
cc c I/usr/include/X11 DICON='"Title Bar"' DDIRECTED gr.c
cc o alg gr.o gr_tool.o pane.o list.o alg.o lX11 lm
This assumes that gr_tool.c, pane.c, and list.c have
already been compiled (using an incantation like that of the first line above).
The I/usr/include/X11 indicates the directory where X11 header
fiels are to be found, DICON='"Title Bar"' causes the given text
to appear in the icon and the title bar of the GDR window (if this is
omitted, the title bar just has the name GDR), and DDIRECTED is
omitted if the program deals with undirected graphs.
The program alg then becomes a version of GDR customized to run
the animation supplied by the programmer in alg.c.
Another alternative is to add an entry for alg in the Makefile,
and then invoke the command make alg.
Further customizations can be done by editing the file gr.h (be
sure to recompile everything when you do this).
[make a list of the sorts of things that can be customized]
[explain blink delays and blink ratio]
Next: About this document ...
Matthias F M Stallmann
19981019