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:

• Construct your graph by using the primitives that the class undi_graph puts at disposal of the programmer to insert nodes and edges (new_node and new_edge). Give each edge the desired direction (make_directed). Suppose that the variable corresponding to the graph is named "ug".
• Perform the following sequence of steps:
list<edge> Le = ug.make_embedding_cand_expanded();
forall (e,Le) ug.new_constraint_uncrossable_edge (e);
plan_undi_graph pug(ug);
pug.contract();
upwa_plan_undi_graph upug(pug);
draw_undi_graph dug(opug);
The meaning of such steps is the following:
Operation ug.make_embedding_cand_expanded() finds an ordering of the edges around each node such that all edges leaving the node are consecutive, as well as all edges entering the node. Then it replaces each node "v" with two nodes "v1" and "v2" such that "v1" has only the edges entering "v" and "v2" has only the edges leaving "v"; finally, a directed dummy edge from "v1" to "v2" is added, and it is stored in the list "Le".
Cycle forall (e,Le) ug.new_constraint_uncrossable_edge (e) adds a set of constraints in order to avoid crossings on the edges of the list "Le" during the next step.
Constructor plan_undi_graph performs a "planarization" of the graph: an order is choosen for the edges around each node trying to keep the number of crossings between edges as low as possible. The name of the planarized graph so obtained is "pug". Variable "pug" is an object of the class plan_undi_graph.
Operation pug.contract() restores the original graph by contracting previously split nodes, preserving the ordering of the edges around nodes.
Constructor upwa_plan_undi_graph computes a quasi-upward representation of the planarized graph, minimizing the total number of bends along edges. The name of the quasi-upward graph so obtained is "upug". Variable "upug" is an object of the class upwa_plan_undi_graph.
Constructor draw_undi_graph constructs the final drawing by assigning each node with a position of the plane and each edge-segment with a length. The constructor has the target of using as less area as possible. Variable "dug" is an object of the class draw_undi_graph.
• At this point variable "dug" stores all the information that is needed to draw "ug" as a quasi-upward drawing. For example, applying center to node "v" returns the coordinates of the center of "v".
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 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 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.

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