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 compile-time 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 [Control-C] 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 x-coordinate of the vertex v
vertex_y(vertex:v)	returns the y-coordinate 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 x-coordinate of the label of edge e
edge_label_y(edge:e)	returns the y-coordinate 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]