Information Technology Reference
In-Depth Information
(a) After Node Positioning
(b) After Node Alignment
(c) After Edge Routing
Fig. 2. The results of pipeline stages (1), (2), (3) are shown in (a), (b), (c), respectively.
To better show flow it is preferable for sources of edges to be to the left of
their targets and by convention edges are routed in an orthogonal fashion. Ports
can—depending on the application—be restricted by certain constraints, e. g.,
all ports with incoming edges should be placed on the left border of the node.
Sponemann et al. define five types of port constraints [17], ranging from ports
being free to float arbitrarily on a node's perimeter, to ports having well-defined
positions relative to nodes. Nodes that contain nested diagrams, i.e., child nodes,
are referred to as compound or nested nodes (as opposed to atomic nodes ); a
graph that contains compound nodes is a compound graph . We refer to the ports
of a compound node as hierarchical ports . These can be used to connect atomic
nodes inside a compound node to atomic nodes on the outside.
The main additional requirements for layout of data flow diagrams on top
of standard graph drawing conventions are therefore [17]: (R1) clearly visible
flow, (R2) ports and port constraints, (R3) compound nodes, (R4) hierarchical
ports, (R5) orthogonal edge routing, and (R6) orthogonalized node positions to
emphasize R1 using horizontal edges.
The starting point for our approach is constrained stress majorization [3]. This
extends the original stress majorization model [9] to support separation con-
straints that can be used to declaratively enforce node alignment, non-overlap
of nodes, flow in directed graphs, and to cluster nodes inside non-overlapping
regions. Brandes et al. [1] provide one method to orthogonalise an existing layout
based on the topology-shape-metrics approach, but in order to handle require-
ments R1-6 we instead use the heuristic approach of Kieffer et al. [10] to apply
alignment constraints within the stress-based model.
Our Constrained Data Flow (CoDaFlow) layout algorithm is a pipeline with
three stages:
1. Constrained Stress-Minimizing Node Positioning
2. Grid-Like Node Alignment
3. Orthogonal Edge Routing
The intermediate results of this pipeline are depicted in Fig. 2. Single stages can
be omitted, e.g., when no edge routing is required or initial node positions are
given. In this section we restrict our attention to flat graphs, i. e., those without
compound nodes, while Sect. 3 extends the ideas to compound graphs.
 
Search WWH ::




Custom Search