The Structure of AGD

The two main parts of AGD are a collection of layout algorithms and a toolbox for extending the library by new implementations.

AGD is written in the programming language C++ and uses the LEDA platform for combinatorial and geometric computing [MN95]. The design of AGD is based on the object-oriented features of the C++ programming language. In particular, each layout algorithm is implemented as a C++ class. There is a common base class for all layout algorithms called LayoutModule. The main advantages of this approach are a generic interface to all layout algorithms, which allows for an easy integration into applications, and a mechanism for handling preconditions and postconditions of algorithms in the base class which is simply inherited by all algorithms.

Figure: A Sketch of the User's View of AGD

Figure User's View shows an overview of the AGD library from the user's perspective. The class GridLayoutModule is a base class of the specific layout algorithms Convex or MixedModel. GridLayoutModule provides operations for all layout algorithms which place the vertices on integer coordinates. Moreover, it defines a common user interface for this type of layout algorithms. GridLayoutModule inherits from LayoutModule which provides common functionality and a basic interface for all layout algorithms.

Depending on the application different types of visualization of the computed layouts may be suitable including no visualization at all (e.g., just using the computed vertex coordinates as input to further computations). Thus it is important that the layout algorithms are not tied to a specific visualization tool. In AGD we achieve this goal by manipulating the graphical attributes of a graph by means of a generic interface which is defined in the abstract class LayoutInterface. The user can specify which package to use for representing and displaying graphical attributes of a graph by choosing a predefined specialization of LayoutInterface ( GraphWinInterface for LEDA's graph visualization component GRAPHWIN and GraphletInterface for the graph editor GRAPHLET [Him97] are already available) or by deriving her own class from LayoutInterface.