The Generic Graphics Interface

The layout of a graph is expressed by graphical attributes of vertices and edges. Most graph drawing packages define an extended graph data structure, and use this structure with their graph drawing functions.

This approach contains several disadvantages: Many applications that require graph layout algorithms have already defined their own data structures, e.g., the graph editor GRAPHLET uses the class GT_Graph to represent a graph together with its graphical attributes. Another disadvantage is that a specific application could need further graphical attributes, such as bitmaps or PostScript graphics, or the provided graph class contains many unnecessary attributes.

AGD does not define an extended graph data structure, but uses a generic interface class to access graphical attributes in existing data structures. This makes it possible to use different data structures representing layouts by implementing a specific layout interface.

In a drawing of a graph, vertices are represented by graphical objects such as rectangles or circles usually containing a text label, and edges are represented by curves (polylines or splines). A layout algorithm does not need to know the specific details of the graphical representation of a vertex, it is sufficient to know its size. The algorithm computes a position for each vertex, and a list of bends for each edge. Some algorithms, e.g., visibility representation, in addition have to change the size of a vertex and to specify where exactly the edges are connected to the corresponding source and target vertices. These points of connection are often called edge anchors.

For the representation of edge anchors we adopted the method used in the GRAPHLET system [Him97]. Each anchor p is defined by a point with two coordinates describing the relative position of p with respect to the position of the corresponding vertex v. The point (0, 0) corresponds to the center of v. The coordinates in the range of [- 1...1] x [- 1...1] are linearly mapped to the bounding box of v which is specified by the width and height of v.

The class LayoutInterface defines a generic interface to read and manipulate these basic attributes. It does not store them, but defines how these attributes are accessed. An implementation of a layout interface is a class derived from LayoutInterface that implements the virtual methods for a specific data structure representing a layout.

Furthermore, the class LayoutInterface contains two notification methods. The method update() is called, when intermediate changes in the layout shall be made visible, and the method refresh() is called in order to indicate that the topology of the associated graph has changed, e.g., nodes or edges have been inserted or deleted.

There are already several predefined specializations of LayoutInterface available in AGD: GraphWinInterface and GraphWinAnimInterface for LEDA's graph visualization component GRAPHWIN [MNSU99], PSInterface for the output to a POSTSCIPT file and AGDLayout as a simple storage for graphical attributes. For an example of how to use a layout interface with a graph drawing algorithm see Section usage.