Polyline Edge Routing

This section presents polyline edge routing.

About this Algorithm

Polyline edge routing calculates polyline edge paths for a diagram's edges. The positions of the nodes in the diagram are not altered by this algorithm.

Edges can be routed orthogonally, i.e., each edge path consists of horizontal and vertical segments, or octilinear. Octilinear means that the slope of each segment of an edge path is a multiple of 45 degree.

Figure 10.85. Polyline edge routing styles

Polyline edge routing styles
Polyline edge routing styles
Graph with orthogonal edge routing... ... and with octilinear edge routing.

Relevant Classes

Table 10.67, “Relevant classes for this algorithm” lists the relevant classes for the polyline edge routing algorithm.

Table 10.67. Relevant classes for this algorithm

Classname Description
EdgeRouter Main algorithm. See the description below.
EdgeLayoutDescriptor Provides edge-related layout options. For example, configuration of minimum distances and penalty settings. See Related Classes.
PenaltySettings Configures penalty settings that will be queried during the edge routing process. See Related Classes.
Grid Provides grid settings.

Class EdgeRouter

Class EdgeRouter is a layout algorithm for routing edges in a diagram. The positions of the nodes in a diagram are not altered by this algorithm. The algorithm supports routing of all edges at once as well as incremental scenarios where subsequently added edges should be drawn to fit the existing diagram. It can be used to route edges in both flat and grouped graphs.

Routing Options

EdgeRouter provides a set of options that affect the routing behavior. This section highlights some of the configuration options available.

The SphereOfAction property determines the (sub-)set of edges that the router should process. When only a subset should be routed, a data provider holding the subset information for each edge is looked up. The data provider is expected to be registered with the graph using the look-up key returned by SelectedEdgesDpKey.

RouteAllEdges
Description Routes all edges in the graph.
RouteSelectedEdges
Description Routes only the selected subset of edges in the graph.
Polyline Edge Routing
API
bool PolylineRouting { get; set; }
Description Determines whether the edge routing algorithm creates orthogonal or octilinear edge paths.
Preferred Polyline Edge Segment Length
API
double PreferredPolylineSegmentLength { get; set; }
Description Sets the preferred length of (non-orthogonal) polyline segments.
Minimal Node to Edge Distance
API
double MinimalNodeToEdgeDistance { get; set; }
Description Determines the distance between edge segments and node sides.

Further routing options can be specified by means of the layout descriptor class for edges. One instance of this class is held by EdgeRouter to store and retrieve default values for routing options, like, e.g., preferred minimum distances between graph elements.

EdgeRouter provides access to the default EdgeLayoutDescriptor instance:

EdgeLayoutDescriptor DefaultEdgeLayoutDescriptor { get; }
Description Edge-related layout options

In addition to the instance held directly by EdgeRouter, layout descriptors can also be associated with single edges in order to specify individual settings for them. Setting individual descriptors for edges is done through a data provider that is bound to the graph. See Related Classes.

Advanced Routing Concepts

Class EdgeRouter supports:

Label Awareness

The polyline edge routing algorithm can be set up to take both node labels and edge labels into account during routing. It considers the size of node labels and labels of "fixed" edges, i.e., edges that are not to be routed. If space permits, the algorithm will generate edge paths that do not not cross through these labels in the resulting diagram.

Consider Node Labels
API
bool ConsiderNodeLabels { get; set; }
Description Specifies whether or not this edge router considers node labels as obstacles for edge paths it calculates.
Consider Edge Labels
API
bool ConsiderEdgeLabels { get; set; }
Description Specifies whether or not labels of edges that are not to be routed by the edge router are considered as obstacles for the edge paths it calculates.

Port Constraints

EdgeRouter supports both weak port constraints as well as strong port constraints that are specified for the edges of a graph (more precisely, the edge ends). The setup of port constraints is presented in the section called “Port Constraints”.

Using weak port constraints for the ends of an edge, it is possible to specify at which side of the source node or target node, respectively, an edge path must connect.

Using strong port constraints, it is possible to specify the side of the node at which an edge must connect, and additionally also the exact position of the port.

Both weak port constraints and strong port constraints can be mixed easily in the drawing.

The following table lists the data provider look-up keys that are recognized by EdgeRouter in conjunction with port constraints.

Table 10.68. Data provider look-up keys

Key Element Type Value Type Description
SourcePortConstraintDpKey edge PortConstraint For each edge a PortConstraint object encoding its source end's port constraint.
TargetPortConstraintDpKey edge PortConstraint For each edge a PortConstraint object encoding its target end's port constraint.

Port Candidates

In addition to the support provided for port constraints, polyline edge routing also supports the concept of port candidates. Both aspects, i.e., matching port candidates as well as modeling enhanced port constraints are supported.

For the matching of port candidates, the set of allowed anchor locations for edge ends at the nodes of a graph are retrieved from a data provider that is bound to the graph using the look-up key NodeDpKey. The subset of desired anchor locations where the source ports and target ports of edges like to connect to are retrieved from data providers that are bound to the graph using the look-up keys SourcePcListDpKey and TargetPcListDpKey, respectively.

See the section called “Port Candidates” for a detailed description of the port candidates concept.

For modeling enhanced port constraints, the set of possible port candidates for the edges of a graph are retrieved from data providers that are bound to the graph using the look-up keys SourcePcListDpKey and TargetPcListDpKey, respectively.

The following table lists the data provider look-up keys that are recognized by EdgeRouter in conjunction with port candidates.

Table 10.69. Data provider look-up keys

Key Element Type Value Type Description
NodeDpKey node PortCandidateSet For each node a PortCandidateSet object encoding the set of allowed anchor locations for edges.
SourcePcListDpKey edge ICollection For each edge an ICollection of PortCandidate objects that encode the subset of desired anchor locations where the source port likes to connect to.
TargetPcListDpKey edge ICollection For each edge an ICollection of PortCandidate objects that encode the subset of desired anchor locations where the target port likes to connect to.

Edge/Port Grouping (Bus-style Edge Routing)

Polyline edge routing supports the notion of grouping together multiple edge ends to be anchored at the same location. This can be specified for both source ends and target ends. The general setup for edge groups is described in the section called “Edge/Port Grouping (Bus-Style Edge Routing)”.

Figure 10.86. Edge routing with edge/port grouping

Edge routing with edge/port grouping

The following table lists the data provider look-up keys that are recognized by EdgeRouter in conjunction with edge/port grouping (bus-style edge routing).

Table 10.70. Data provider look-up keys

Key Element Type Value Type Description
SourceGroupIdDpKey edge object For each edge an arbitrary object indicating the group its source end is affiliated with.
TargetGroupIdDpKey edge object For each edge an arbitrary Object indicating the group its target end is affiliated with.

Node Halos

EdgeRouter by default supports node halos as soon as they are declared. It considers any specified additional paddings around nodes and if space permits, the algorithm will generate edge paths that do not cross through these areas in the resulting diagram. Other constraints (e.g. port constraints) that have higher costs associated, can cause edges to cross node halos, however.

The following table lists the data provider look-up keys that are recognized by EdgeRouter in conjunction with node halo support.

Table 10.71. Data provider look-up keys

Key Element Type Value Type Description
NodeHaloDpKey node NodeHalo A NodeHalo object that specifies the halo sizes at each side of a node.

Routing in Grouped Graphs

EdgeRouter supports routing in grouped graphs without further setup. It recognizes group nodes and folder nodes and finds edge paths to nodes grouped within group nodes.

Routing in Partition Grids

EdgeRouter supports routing in partition grids without further setup. It recognizes swimlane nodes/partition grids and finds edge paths to nodes within partition cells.

To know about the layout of a partition grid's rows and columns, it uses the services of class PartitionGrid. The PartitionGrid object is retrieved from a data provider that is bound to the graph using the look-up key PartitionGridDpKey.

The following table lists the data provider look-up keys that are recognized by EdgeRouter in conjunction with routing in partition grids.

Table 10.72. Data provider look-up keys

Key Element Type Value Type Description
PartitionGridDpKey graph PartitionGrid A PartitionGrid object that specifies the actual partition grid, including number of rows and columns, their respective heights and widths, and their insets.

Incremental Routing

EdgeRouter supports incremental routing through the "Sphere of Action" feature. See the above description.

Related Classes

Class EdgeLayoutDescriptor can be used to configure edge-related layout and drawing options. For example, the following options can be set:

  • preferred minimum distance between edge segments
  • preferred minimum length of first and last edge segment, respectively
  • penalty values

The edge layout can be configured using class EdgeLayoutDescriptor:

Minimum Distance Edge to Edge
API
double MinimalEdgeToEdgeDistance { get; set; }
Description Determines the preferred minimum distance between any two edge segments.
Minimum Length of First and Last Segment
API
double MinimalFirstSegmentLength { get; set; }
double MinimalLastSegmentLength { get; set; }
Description Determine the preferred minimum length of the first (at the source) and last (at the target) edge segment.
Minimum Distance to Node Corners
API
double MinimalNodeCornerDistance { get; set; }
Description Determines the preferred minimum distance between an incident edge and the corners of its node at the side where the edge connects.
Penalty Settings
API
PenaltySettings PenaltySettings { get; set; }
Description Configures different penalty settings that are queried during edge routing. Penalties define the costs for various situations, like, e.g., two edge paths crossing, or an edge path crossing a node, etc. Higher penalty for a specific situation means that the edge routing algorithm tries to avoid it and instead looks for other edge paths.

An EdgeLayoutDescriptor instance can be specified individually for single edges by means of a data provider that is bound to the graph. The data provider is expected to be registered with the graph using key EdgeLayoutDescriptorDpKey. In the absence of an individual descriptor for an edge, the default EdgeLayoutDescriptor instance that is registered with EdgeRouter will be used.

Monotonic Edge Paths

EdgeRouter supports edge routing such that the generated paths obey so-called monotonic path restrictions. This means that (ideally) each vertical and/or each horizontal segment of an edge path is directed the same way, namely from source node to target node. Thus, when following the edge path, there is never a "turning back" towards the source node, but instead a steady movement towards the target node.

Monotonic edge paths are useful, for example, when routing edges in UML class diagrams/inheritance diagrams or in a tree-like organization chart.

The following property from class EdgeLayoutDescriptor configures monotonic path generation:

Monotonic Path Restrictions
API
MonotonicPathRestriction MonotonicPathRestriction { get; set; }
Description

Specifies the kind of monotonic path restrictions for edges. The following restrictions are available:

Figure 10.87, “Edge routing with monotonic path restrictions” illustrates the results of specifying monotonic edge path restrictions. All figures have specified restrictions in vertical direction, i.e., each vertical edge segment shall be directed from source node to target node.

Figure 10.87. Edge routing with monotonic path restrictions

Ideal edge route with monotonic path restrictions.
Stairs-like edge path due to obstacles.
Path restrictions cannot be obeyed due to large obstacle.
Ideal edge route with monotonic path restrictions in vertical direction. Stairs-like edge path due to obstacles. Vertical path restrictions are obeyed. Vertical path restrictions cannot be obeyed due to large obstacle.

The following table lists the data provider look-up keys that are recognized by EdgeRouter in conjunction with individual layout settings for edges.

Table 10.73. Data provider look-up keys

Key Element Type Value Type Description
EdgeLayoutDescriptorDpKey edge EdgeLayoutDescriptor For each edge an EdgeLayoutDescriptor object that configures a number of edge-related options.

Supplemental Layout Data

Class EdgeRouter knows a number of data provider keys which are used to retrieve supplemental layout data for each graph element. The data is bound to the graph by means of a data provider which is registered using a given look-up key. Table 10.74, “Data provider look-up keys” lists all look-up keys that EdgeRouter tests during the layout process in order to query supplemental data.

Binding supplemental layout data to a graph is described in the section called “Providing Supplemental Layout Data”.

Table 10.74. Data provider look-up keys

Key Element Type Value Type Description
EdgeLayoutDescriptorDpKey edge EdgeLayoutDescriptor For each edge an EdgeLayoutDescriptor object that configures a number of edge-related options.
SourcePortConstraintDpKey edge PortConstraint For each edge a PortConstraint object encoding its source end's port constraint.
TargetPortConstraintDpKey edge PortConstraint For each edge a PortConstraint object encoding its target end's port constraint.
SourceGroupIdDpKey edge object For each edge an arbitrary object indicating the group its source end is affiliated with.
TargetGroupIdDpKey edge object For each edge an arbitrary Object indicating the group its target end is affiliated with.
NodeDpKey node PortCandidateSet For each node a PortCandidateSet object encoding the set of allowed anchor locations for bus connections.
SourcePcListDpKey edge ICollection For each edge an ICollection of PortCandidate objects that encode the subset of desired anchor locations where the source port likes to connect to.
TargetPcListDpKey edge ICollection For each edge an ICollection of PortCandidate objects that encode the subset of desired anchor locations where the target port likes to connect to.
PartitionGridDpKey graph PartitionGrid A PartitionGrid object that specifies the actual partition grid, including number of rows and columns, their respective heights and widths, and their insets.
NodeHaloDpKey node NodeHalo A NodeHalo object that specifies the halo sizes at each side of a node.
AbortHandlerDpKey graph AbortHandler An AbortHandler instance that will be queried by the layout algorithm to determine whether layout calculation shall be terminated.