Grasper-CL provides a layered architecture comprised of several different components: a core procedure library for programmatically manipulating the graph abstract datatype, a graph-display module for producing drawings of graphs, a graph editor that allows users to interactively draw and edit arbitrary graphs, and a suite of automatic graph-layout algorithms. Each layer has been fully articulated and developed, and is accessible to the programmer. This open architecture provides the programmer with an extensive set of tools for building applications that manage and display graphs.

The Grasper-CL core provides a library of functions for manipulating a graph abstract datatype. These functions perform no drawing operations; they provide a memory-resident graph database facility in which nodes and edges can be created, destroyed, and modified, and relationships among nodes and edges can be queried. A graph can also be written to and read from a disk file. The shape module manages information about the shapes and locations of nodes and edges, and performs shape-related calculations, such as determining the bounding box of a given node.

Given a set of nodes and edges defined using the Grasper-CL core, and shape and location information defined by the shape module, the display module draws or erases a graphical rendition of a graph, or of individual nodes and edges. Node positions might have been determined interactively by the user, or programmatically by either an application-specific layout algorithm, or by a member of the Grasper-CL suite of graph layout algorithms.

The graph editor is a menu-driven Grasper-CL application that allows users to interactively draw and edit graphs. It includes operations for interactively creating, renaming, deleting, copying, or altering the shape of nodes and edges. The interactive display module includes the functions that implement the operations within the graph editor. These functions provide a high-level substrate for building interfaces in which users also perform interactive graph editing, but with added application semantics.

Grasper-CL has an open architecture because every level is documented and available to applications. Different classes of applications make use of different subsets of the Grasper-CL system. Core applications have no graphics component - they simply use the core procedures to manipulate instances of the graph abstract datatype. For example, imagine that we wish to program a solution to the traveling salesman problem. We could use the core procedures to create a graph whose nodes and edges represent cities and highways, to store intercity distance information at each edge, and to query these relationships during the optimization process.

Display applications use the display module to draw a graph. For example, we might wish to display the final solution computed by our traveling salesman algorithm in a single window. Display applications support only the most primitive user interaction with a graph, such as clicking on a node to perform some action. For example, we might allow the user to left click on an edge to query the distance between two cities, and to modify the computed solution by middle clicking on an edge to delete it. The entire graph is displayed at once in a scrollable window. Interactive applications use the display module to display graphs, and they use the interactive display module procedures to support direct user interaction with the graph. Interactive applications include multiple display panes, one or more of which contains the display of a graph. Other display panes typically contain a menu of commands that can be selected for application to the graph. For the traveling salesman graph, one menu command might prompt the user to click on a city, and then display the population of the city. Another menu command might prompt the user to create a new city by clicking on the background of the graph pane, and then draw the new city at that location.

Graph-editor applications are a restricted type of interactive applications-restricted in the sense that the style of user interaction shares much in common with the style of the graph editor. Such applications are faster to program than interactive applications because of the potential for reusing code within the graph editor. For example, imagine that we wish to provide the user of the traveling salesman system with the ability to edit a solution graph in arbitrary ways that incorporate the semantics of the application (for example, by moving cities, adding cities, copying cities, changing the drawn shape of cities). It is easy to define such commands by using the procedures from which the graph editor is implemented.


Back to John D. Lowrance, <lowrance@ai.sri.com>
Back to Artificial Intelligence Center
Back to SRI International

Grasper-CL is a trademark of SRI International.
Copyright © 1995 SRI International, 333 Ravenswood Ave., Menlo Park, CA 94025 USA. All rights reserved.