Orthogonal drawings have an impressive range of applicability. In what follows we show how to use GAPI for constructing orthogonal 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. Fourth, we show how several choices are available for constructing drawings that are more or less compact. Fifth, we show how to customize the drawing according to your special requirements. Finally, we show how to deal with dynamic orthogonal drawing.

A simple strategy

If you want to construct an orthogonal 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). If some edges are directed give to them the desired direction (make_directed). Suppose that the variable corresponding to the graph is named "ug".
Perform the following sequence of steps:
The meaning of such steps is the following:
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.
Constructor orth_plan_undi_graph performs an "orthogonalization" of the planarized graph. Each edge is assigned with a specific shape, with the minimum number of bends along the edges. The name of the orthogonal graph so obtained is "opug". Variable "opug" is an object of the class orth_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 an orthogonal drawing. For example, applying center to node "v" returns the coordinates of the center of "v".

An example of orthogonal drawing constructed with the previous steps is shown in the following figure.

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 either in terms of number of bends along edges or in terms of global area occupied by the drawing. On the other hand you will have better time performance. GDT offers several facilities to explore the performance/effectiveness trade-off.

For example, if you accept to have more bends that those that are strictly needed, you can replace
orth_plan_undi_graph opug(pug);
with
orth_plan_undi_graph opug(pug, PLAN_ORTH_QUICK);
This replaces the default algorithm for orthogonalization with a faster one.

Note: the current version of GDT allows to apply option PLAN_ORTH_QUICK only to graphs that are biconnected and whose nodes have at most four incident edges. A graph is biconnected if the removal of one node is not sufficient to cut it into two (or more) disconnected pieces.

As another example, if you accept to have a larger area than the one that is strictly needed, you can replace
draw_undi_graph dug(opug);
with
draw_undi_graph dug(opug, FAST_COMPACTION);
This replaces the default algorithm used in the last step with a faster one. An example of orthogonal drawing constructed with the FAST_COMPACTION option is shown in the following figure.

The same graph drawn with the default algorithm is as follows

GDT offers other alternatives to FAST_COMPACTION allowing to choose different trade-offs between performance and aesthetics. Namely, FAST_COMPACTION_REFINED, SLOW_COMPACTION, and SLOW_COMPACTION_REFINED (default option).

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
orth_plan_undi_graph opug(pug);
with
orth_plan_undi_graph opug(pug, PLAN_ORTH_SLOW);
This replaces the default algorithm for orthogonalization with a more accurate one.

An orthogonal drawing constructed with option PLAN_ORTH_SLOW of the same graph of a previous figure is shown below.

Note: the current version of GDT allows to apply option PLAN_ORTH_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_ORTH_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 compaction

Several strategies are available for compacting orthogonal drawings. They have assigned constants:

FAST_COMPACTION,
FAST_COMPACTION_REFINED,
SLOW_COMPACTION,
SLOW_COMPACTION_REFINED,
FAST_REGULAR_COMPACTION_1,
SLOW_REGULAR_COMPACTION_1,
FAST_REGULAR_COMPACTION_2,
SLOW_REGULAR_COMPACTION_2,
FAST_REGULAR_COMPACTION_1_REFINED,
SLOW_REGULAR_COMPACTION_1_REFINED,
FAST_REGULAR_COMPACTION_2_REFINED, and
SLOW_REGULAR_COMPACTION_2_REFINED.

If no specification is given, then compaction SLOW_REGULAR_COMPACTION_2_REFINED is applied as a default. If you want to force GDtoolkit to use a certain compaction strategy, different from the default one, you have to specify it as follows:

plan_undi_graph pug(ug);
orth_plan_undi_graph opug(pug);
draw_undi_graph dug(opug,SLOW_COMPACTION);

In this case BLAG will use the compaction strategy SLOW_COMPACTION. Usually, the best strategies, from the aesthetics point of view, are SLOW_REGULAR_COMPACTION_1_REFINED and SLOW_REGULAR_COMPACTION_2_REFINED. On the other hand they are more time consuming than the others. They are strongly recommended for applications where having very compact drawings is a strict requirement.

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:

Suppose that "ug" is your graph and that "Le" is the list of the nodes of the above set. First, you have to perform:
ug.new_constraint_same_face_node(Le,c)
Where "c" is an integer label that you use to denote the face where the nodes in "Le" will be placed.

Perform the following sequence of steps:

plan_undi_graph pug(ug);

orth_plan_undi_graph opug(pug,f);
draw_undi_graph dug(opug);

During the execution of plan_undi_graph, the constraint is taken into account. Once "pug" is computed, "f" can be determined by simply scanning the faces containing the nodes of "Le". For example you can exploit method node_belongs_to_face that is offered by class plan_undi_graph.

At this point variable "dug" stores all the information that is needed to draw "ug" as an orthogonal drawing with the nodes in "Le" on the external face.

An orthogonal drawing of the previous graph, constructed with a specific set of nodes (0, 5, and 6) on the external face is shown in the following figure.

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.

You can also specify the width and the height of each node, by simply using the following commands ug.new_constraint_node_width(v,width) and/or ug.new_constraint_node_height(v,height) before performing any orthogonal layout algorithm. What follows is an example of orthogonal drawing in which we have set the width and the height of node 8 both equal to 1, and the width and the height of node 2 equal to 1 and equal to 3, respectively. The length are in terms of integer grid points, and the width and the height of any node are always equal to 0 if not specified otherwise.

Dynamic orhogonal drawing

Dynamic algorithms can be used by application developers in order to effectively support the user when, once obtained a satisfactory diagram using one of the available static algorithms, he/she needs to add a new node or a new edge while keeping the shape of the current drawing substantially unchanged.

DynamicOrthogonal provides the user with on-line support, by locally updating the given layout after each individual node/edge creation. The path of each new edge is calculated with a shortest-path technique. Path costs are evaluated taking into account user-defined costs per bend, per cross, and per length-unit. This allows the developer to tune the algorithm in order to make it generate, for example, longer edges rather than crossing ones.

DynamicOrthogonal at work...

(Animation, bends smoothed)

Last update : July 31, 2002
Website design by INTEGRA Sistemi, www.IntegraSistemi.it