Channel Edge Routing

ChannelEdgeRouter is an orthogonal edge routing algorithm that uses a two step approach for finding edge routes. First, a path finding phase assigns preliminary paths for all edges. In a second step, the distribution phase, these edge paths are then distributed so that edge segments take up the space between the nodes. The available space that an edge segment can use is also referred to as its "channel."

ChannelEdgeRouter is particularly well suited for routing bus-like structures, i.e., sets of parallel edges between common nodes. Compared to OrthogonalEdgeRouter, edge segments can be very close to each other, and edges may also overlap with nodes when using the default pattern routing scheme for the path finding phase (see below). However, there are many situations where this algorithm will be faster.

Figure 10.94. Sample edge routing produced by ChannelEdgeRouter

Sample edge routing produced by ChannelEdgeRouter

By default, ChannelEdgeRouter delegates the path finding and distribution steps to specialized layout providers, namely classes OrthogonalPatternEdgeRouter and OrthogonalSegmentDistributionStage, respectively. The strategies for both path finding and distribution can be easily customized.

Supplemental Layout Data

Both the default path finding as well as the default distribution strategy of class ChannelEdgeRouter know a number of data provider keys which are used to retrieve supplemental layout data for a graph's elements. The data is bound to the graph by means of a data provider, which is registered using a given look-up key. Table 10.78, “Data provider look-up keys” lists all look-up keys for ChannelEdgeRouter's default path finding and distribution strategies.

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

Table 10.78. Data provider look-up keys

Key Element Type Value Type Description
AffectedEdgesDpKey edge bool For each edge a boolean value indicating whether it should be routed or not.
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.
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.

Routing Options

Class ChannelEdgeRouter itself has no special routing options beyond the properties which allow to customize the strategies used for the two routing phases:

ILayouter PathFinderStrategy { get; set; }
ILayouter EdgeDistributionStrategy { get; set; }
Description Enable setting the ChannelEdgeRouter strategies for the routing phases.

Affected Edges

Determines the set of edges from the graph that should be processed. When only a subset should be routed, a data provider holding the selection state for each edge is looked up. The data provider is expected to be registered with the graph using key AffectedEdgesDpKey.

OrthogonalPatternEdgeRouter and OrthogonalSegmentDistributionStage, which are used as the default path finding and distribution strategy, respectively, both support this routing option. Also, they provide convenience properties that allow to map other already registered data providers to the AffectedEdges key:

object AffectedEdgesDPKey { get; set; }
Description Enables mapping of data providers. The same property is available in classes OrthogonalPatternEdgeRouter and OrthogonalSegmentDistributionStage.

Advanced Routing Features

Port Constraints

Both the default path finding as well as the default distribution strategy of class ChannelEdgeRouter obey both types of port constraints, weak and strong. The port constraints are retrieved from data providers that are bound to the graph using the look-up keys SourcePortConstraintDpKey and TargetPortConstraintDpKey, respectively.

Port Candidates

In addition to the support provided for port constraints, ChannelEdgeRouter's default path finding and distribution strategies also supports port candidates that model enhanced port constraints, comprising, for example, multiple sides of a node at once. 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.

See the section called “Modeling Enhanced Port Constraints Using Port Candidates” for a detailed description of this port candidates use case.

Incremental Routing

ChannelEdgeRouter supports incremental routing through the "Affected Edges" feature. See the above description.

Related Classes

By default, OrthogonalPatternEdgeRouter is set as the path finding stategy for ChannelEdgeRouter. It supports two different policies for finding edge paths, "free" routing, which is the default, and grid routing. Common to both routing policies is the general technique for finding an edge path: depending on the relative location of source and target node, an edge path is chosen from a set of possible routing "patterns." The paths from this set are associated with costs, and OrthogonalPatternEdgeRouter chooses the routing pattern that causes the least costs.

The properties listed below can be used to specify the costs for specific situations, for example, edge segments that overlap. Note that, despite the different cost factors, the actual routing chosen by OrthogonalPatternEdgeRouter may overlap with nodes, for example, when an edge's channels offer not enough space for a proper non-overlapping route.

double NodeCrossingCost { get; set; }
double EdgeCrossingCost { get; set; }
double EdgeOverlapCost { get; set; }
Description Allow to specify the costs for specific situations during the routing process.

As an alternative to OrthogonalPatternEdgeRouter, nested class OrthogonalShortestPathPathFinder, a specialized variant of class OrthogonalEdgeRouter, can be used as the path finding strategy for ChannelEdgeRouter.

Applicable Layout Stages

Table 10.79, “Layout Stages” lists layout stages that can be used to enhance the routing process of class ChannelEdgeRouter.

Table 10.79. Layout Stages

Classname Description
PolylineLayoutStage With class ChannelEdgeRouter as the core layouter, this stage adds octilinear edge routing to the diagram that results from the channel edge router calculation.

Tutorial Demo Code

The layout module class ChannelEdgeRouterModule.cs from the LayoutModulesWindow demo application presents the setup of class ChannelEdgeRouter in an application context.