EdgeRouter

Layout Style

Edges are by default routed in an orthogonal fashion, i.e., they only consist of horizontal and vertical segments. There are two additional routing styles: the octilinear style where additional sloped segments are inserted between horizontal and vertical segments and the curved style that replaces the segments with smooth curves.

During the routing process, the positions of the nodes are considered to be fixed and the routing algorithm will not modify their locations or their sizes in any way.

The edge routing algorithm can be applied wherever it is needed to route the edges using orthogonal, octilinear or curved segments without crossing any nodes, while keeping the positions of the nodes in the diagram fixed. Some potential applications include electric circuit design, floor planning and navigation maps.

Sample output of the edge routing algorithm with default settings

Sample output of the edge routing algorithm with octilinear routing and grouped edges

Sample output of the edge routing algorithm with octilinear routing and group nodes

Sample output of the edge routing algorithm with the curved routing style

Sample output with bus-style routing

Concept

The edge routing algorithm basically performs three steps to achieve the main edge routing and an additional fourth step for edges with the octilinear or curved routing style.

1. Creating a IPartition which divides the area of the graph area into several PartitionCells.
2. Finding the shortest/cheapest paths for all edges through the IPartition using PathSearch.
3. Assigning coordinates to the segments of the edges based on the paths that were calculated before with ChannelBasedPathRouting.
4. Inserting non-orthogonal segments where horizontal and vertical segments meet for edges with routing style OCTILINEAR or inserting curved segments for edges with routing style CURVED.

The first two steps are customizable. IGraphPartitionExtensions are able to influence how the IPartition is created. They add PartitionCells and/or mark them for adding costs later in the process. The currently used partition extensions can be dropped or extended by custom implementations.

For example, the extension 'Node Partition' adds a PartitionCell to the IPartition for each node and marks it as belonging to a node. During PathSearch, the extension 'Node Crossing' recognizes these PartitionCells and adds costs that penalizes crossing a node. The edge will be routed around the nodes.

PathSearchExtensions influence the PathSearch by adding costs for traversing PartitionCells or narrowing their intervals to allow a less expensive traversal of a PartitionCell. The currently used partition extensions can be dropped or extended by custom implementations.

Using EdgeRouterEdgeLayoutDescriptors, it is possible to add individual layout settings like routing styles to edges. They are registered with the graph with key EDGE_LAYOUT_DESCRIPTOR_DP_KEY. If no descriptor is provided for an edge, a default edge layout descriptor is used as fallback value.

Features

The routing algorithm supports two approaches to connect edges on a specific side or even on an exact location to a node. PortConstraints define a single constraint for the ports of an edge. To realize more complex port restrictions, several PortCandidates or PortCandidateSets can be assigned to edges or nodes. If an edge with registered PortCandidates connects to nodes with PortCandidateSets, the edge router will try to match both collections in order to find an appropriate port. In case there is no matching port candidate, a PortCandidate specified for the edge is preferred. Note that the routing algorithm doesn't consider custom IPortCandidateMatcher implementations. Since their simultaneous existence at the same node may be ambiguous, it is not recommended to use a combination of PortConstraints and PortCandidates in the same diagram.

Strong PortConstraints or fixed PortCandidates defined for an edge end at a group node where the strong/fixed port location is inside the group node are supported with the following characteristics. First of all, if there are multiple PortCandidates and one is not inside the group but, e.g., on its border, then such a candidate is always preferred over an inner one. When an inner constraint is considered, then the algorithm actually generates a proper route from the group's border to the port location. Obstacles on the way are considered like for any other route. The group node is also entered at the side which is defined by the PortConstraint or PortCandidate.

A PartitionGrid is respected in the way that the algorithm avoids that cell boundaries are left and re-entered. This way, edge routes stay inside a cell if both source and target are in the same cell. For this feature to work properly it is required that the values of the properties originalPosition, originalPosition originalWidth and originalHeight are correctly specified. This is usually automatically the case when executing the EdgeRouter as a standalone algorithm via layout execution convenience methods (e.g. the values are taken from the table visualization of the grid). However, if the router is applied as part of a more complex layout pipeline it might be necessary to specify the values manually. For example, if another algorithm previously computed the grid position values and stored them in the respective 'computed' properties (e.g. computedPosition), and afterwards EdgeRouter should be applied, then the 'computed' values of the first algorithm should be written to the 'original' values prior to the run of the EdgeRouter.

Edges can be grouped so that they share common segments at the beginning or end of their routes. Edge groups are specified using IDataProviders that provide the same ID object for all edges in the same group. Those IDataProviders are registered with the graph with key SOURCE_GROUP_ID_DP_KEY for source groups or key TARGET_GROUP_ID_DP_KEY for target groups. Besides edge grouping, the EdgeRouter also supports port grouping where all edges with the same port id at a node will share the same port location but are still routed independently (i.e., do not share multiple segments as for edge groups). To specify port groups use a IDataProvider and register it to the graph with key SOURCE_PORT_GROUP_ID_DP_KEY for source port groups or key TARGET_PORT_GROUP_ID_DP_KEY for target port groups. Note that an edge can either be associated with a (source/target) group or a (source/target) port group id, but not both at the same time.

Edges can be routed in a bus-style. Edges that should share common bus segments must be mapped to the same EdgeRouterBusDescriptor (see also BUS_DESCRIPTOR_DP_KEY). The algorithm tries to route a large part of the edge using the common bus segments. These segments are automatically selected depending on the involved edges/nodes, but they might also be specified manually using busPoints. Edges that are fixed (i.e. are not marked for routing) may also belong to a bus. Then, the bus segments will be derived using the existing path of the fixed edges. This way, buses can be incrementally updated, e.g., when a new edge should be added to an existing bus structure. Bus routing can, e.g., be very useful in parts of a diagram where each node is connected to each other node.