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 performs three main steps to achieve the edge routing and an additional fourth step for edges with the octilinear or curved routing style.

1. Creating an IRouterPartition which divides the area of the graph area into several PartitionCells.
2. Finding the shortest/cheapest paths for all edges through the IRouterPartition using sophisticated path search algorithm.
3. Assigning coordinates to the segments of the edges based on the paths that were calculated before.
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. PartitionExtensions are able to influence how the IRouterPartition is created. They add PartitionCells and/or mark them for adding costs later in the process. To add custom extension implementations, use method addPartitionExtension.

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

PathSearchExtensions influence the path search by adding costs for traversing PartitionCells or narrowing their intervals to allow a less expensive traversal of a PartitionCell. Custom extension implementations can be added via addPathSearchExtension.

Using edge descriptors, it is possible to add individual layout settings like routing styles to edges by using the layout data property edgeDescriptors. If no descriptor is provided for an edge, the defaultEdgeDescriptor is used as fallback value.

Features

The routing algorithm supports EdgePortCandidates and NodePortCandidates to connect edges on a specific side or even on an exact location to a node. If an edge with registered EdgePortCandidates connects to nodes with NodePortCandidates, 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 port candidate specified for the edge is preferred.

Fixed LayoutPortCandidates 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 LayoutPortCandidates 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 LayoutPortCandidate.

A LayoutGrid 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 position, position, width and height are correctly specified.

Edges can be grouped so that they share common segments at the beginning or end of their routes. Edge groups are specified with the same ID object via properties sourceGroupIds for source groups and targetGroupIds 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 sourcePortGroupIds for source port groups and targetPortGroupIds for target port groups of the sub-data ports. 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 buses). 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.

Performance

Specifying a stopDuration can reduce the time the EdgeRouter takes to produce a result. The acceleration is achieved by skipping optional optimization steps during the path search in general as well as e.g. during integrated edge labeling and when choosing a possible bus placement. It should be noted that the stopDuration is not a guarantee for the maximum time spent, as the algorithm still has to produce a valid result.

In general, the EdgeRouter tends to perform better when there is sufficient space for the edges to be routed. Consequently, it can take noticeably longer to calculate edge routes for large graphs with densely packed nodes.