Information Technology Reference
In-Depth Information
or else are fixed to a given node boundary side, and (2) extend Adaptive Con-
strained Alignment (ACA) [10] for achieving grid-like layout to handle directed
edges, orthogonal routing, ports, and widely varying node dimensions.
An empirical evaluation of the new approach (Sect. 4) shows it produces lay-
outs of comparable quality to the method of Schulze et al. but with a different
trade-off between aesthetic criteria. The layouts have more uniform edge length,
better aspect ratio, and are more compact but have slightly more edge crossings
and bends. Furthermore, our method is more flexible and requires far less im-
plementation effort. The Schulze et al. approach took a team of developers and
researchers several years to implement by extensively augmenting the Sugiyama
method. While their infrastructure allows a flexible configuration of the existing
functionality [16], it is very restrictive and brittle when it comes to extensions
that affect multiple phases of the algorithm. The method described in this paper
took about two months to implement and is also more extendible since it is built
on modular components with well-defined work flows and no dependencies on
each other.
Related Work.
The most closely related work is the series of papers by
Schulze et al. that show how to extend the layer-based approach to handle the
layout requirements of data flow diagrams [16,17]. Their work presents several
improvements over previous methods to reduce edge bend points and crossings
in the presence of ports. While the five main phases (classically three) of the
layer-based approach are already complex, they introduce between 10 and 20
intermediate processes
in order to address additional requirements. The authors
admit that their approach faces problems with unnecessary crossings of inter-
hierarchy edges as they layout compound graphs bottom-up, i. e., processing the
most nested actor diagrams first. Related work in the context of the layer-based
approach has been studied thoroughly in [16,17]. Chimani et al. present methods
to consider ports and their constraints during crossing minimization within the
upward planarization
approach [2]. While the number of crossings is significantly
reduced, the approach eventually induces a layering, suffering from the same is-
sues as above. There is no evaluation with real-world examples. Techniques from
the area of VLSI design and other approaches that specifically target compound
graphs have been discussed before and found to be insucient to fulfil the layout
requirements for data flow diagrams [17], especially due to lacking support for
different port constraints.
2 CoDaFlow - The Algorithm
Data flow diagrams can be modeled as directed graphs
G
=(
V,E,P,ˀ
)where
nodes
or
vertices v
∈
V
are connected by
edges e
∈
E
ↆ
P
×
P
through
ports
p
V
maps each port
p
to the
parent
node
ˀ
(
p
) to which it belongs. An edge
e
=(
p
1
,p
2
) is directed,
outgoing
from port
p
1
and
incoming
to
p
2
.A
hyperedge
is a set of edges where
every pair of edges shares a common port.
∈
P
—certain positions on a node's perimeter—and
ˀ
:
P
ₒ
