Handling Preconditions and Postconditions of Modules

There is no generic algorithm for drawing all types of graphs, but a wealth of algorithms for different restricted classes of input graphs (e.g., the input graph has to be planar, simple and biconnected). Thus there is a natural need for handling the precondition on the input graph of a particular algorithm. A simple approach to this task is to describe the precondition in the written documentation of the algorithm, and to simply assume that the algorithm gets only valid input graphs. However, this is quite unsatisfactory.

A related problem lies in coping with the different models of drawing graphs, e.g., edges have bends or not, vertex coordinates are integers or not. Again, a simple solution is to describe the properties of the drawing in the documentation and that is it. If in a particular application the user wants to know, which of the available algorithms satisfy a certain property, then there is no elegant way for the application to answer the question.

Our solution to the problems described above is to provide a mechanism for specifying, querying and checking the precondition of an algorithm, and a mechanism for specifying and querying properties of its output, which we call the postcondition of the algorithm. These mechanisms are implemented in the base classes AGD and AGDModule by means of hash tables and they are easy to (re-)use.

Let us see an example. The precondition of a layout algorithm is represented by a set of properties of the input graph, and the postcondition by a set of properties of the layout. They are usually specified in the constructor of a particular algorithm class. The following is the constructor of the class FPPLayout, which implements the layout algorithm by de Fraysseix, Pach, and Pollack [DPP90].

FPPLayout::FPPLayout()
{
    add_precondition (key::planar);
    add_precondition (key::simple);
    add_precondition (key::no_self_loops);

    add_post_rule (key::straight_line);
    add_post_rule (key::no_crossings);
}

In this case all input graphs have to be planar and simple (no parallel edges are allowed) and they may not contain self loops. The drawing that the algorithm produces for a valid input graph is always planar (indicated by no_crossings) and the edges are drawn as straight lines. Therefore, the precondition is {planar,simple,no self loops}, and the postcondition is {straight-line,no crossings}.

The base class LayoutModule defines a function check() which gets a potential input graph and checks whether it satisfies the specified precondition. Function check() simply uses the method check_graph() of its base class AGDModule, which is able to check all common graph properties, like, e.g., planarity, simplicity, biconnectivity. Moreover, there is the possibility to add new properties for particular algorithms, and to extend the check_graph() method accordingly. The check() method is not called by default, if an algorithm is executed, because there are possible situations where it does not make sense to do so, e.g., an application can guarantee the validity of the input because there is some preprocessing step which only produces inputs satisfying all preconditions.