Upward drawings can be used in several applications, for example to draw Petri Nets or SADT diagrams. GAPI considers a more general model of upward drawing, in which some feedback edges are allowed when an upward drawing does not exist for the given graph. We call such a model "quasi-upward" drawing. In a quasi-upward drawing we call "bend" a point in which a feedback edge is tangent to the horizontal line through this point. In what follows we show how to use GAPI for constructing quasi-upward drawings.

First, we present a simple strategy, suitable for beginners (but still powerful enough to cover several applications). Second, we show how to work if performance is more important than aesthetics. Third, we describe how to behave if aesthetics are more important than performance. Finally, we show how to customize the drawing according to your special requirements

A simple strategy

If you want to construct a quasi-upward drawing of a graph with GAPI, simply do the following:

An example of quasi-upward drawing constructed with the previous steps is shown in the following figure. Smoothed edges can be used, instead of polygonal edges, computing them as bezier-curves interpolating polylines. GAPI offers the dug.draw(W,true) method to draw "dug" with smoothed edges in a LEDA-window "W"

 

If performance is more important than aesthetics

If you have strict performance requirements, then you can customize the simple piece of code shown above to obtain drawings that are slightly worse in terms of global edge length used by the drawing. On the other hand you will have better time performance. To do it, you can replace
   draw_undi_graph dug(upug);
 with
   draw_undi_graph dug(upug, FAST_COMPACTION);
 An example of quasi-upward drawing constructed with the FAST_COMPACTION option ia shown in the followin figure:

The same graph drawn with the default algorithm is as follows:

 

If aesthetics are more important than performance

If you have strict aesthetics requirements, then you can customize the simple piece of code shown above to obtain drawings that are much better in terms of number of bends along edges. On the other hand you will have worse time performance. For example, you can replace
   upwa_plan_undi_graph upug(pug);
 with
   upwa_plan_undi_graph upug(pug, PLAN_UPWARD_SLOW);
 This replaces the default algorithm for quasi-upward with a more accurate one.

A quasi-upward drawing constructed with option PLAN_UPWARD_SLOW of the same graph of a previous figure is shown below.

Note: the current version of GDT allows to apply option PLAN_UPWARD_SLOW only to graphs that are biconnected. A graph is biconnected if the removal of one node is not sufficient to cut it into two (or more) disconnected pieces.

Note: option PLAN_UPWARD_SLOW causes the invocation of a branch and bound algorithm, that is potentially exponential in time requirement. This makes it unsuitable for graphs with more that 100 nodes.

 

Drawing customization

If you need to customize your drawing, then you can exploit the capability of GDT in handling user-specified constraints.

For example, if you want that all the nodes of a certain set (that, for example, are the "boundary" of your application) are drawn on the border of the polygon surrounding the drawing (external face) then you can do the following steps:

As another example, if you want to emphasize an edge "e" that for some reason is expecially important, then you maight want to preserve it to have crossings and maybe to have bends. This is done very easily by performing ug.new_constraint_uncrossable_edge(e) and/or ug.new_constraint_number_of_bends_on_edge(e,NONE) before performing the planarization step.
Last update : July 31, 2002
Website design by INTEGRA Sistemi, www.IntegraSistemi.it