Search this API

y.layout.router.polyline
Class EdgeRouter

java.lang.Object
  extended by y.layout.AbstractLayoutStage
      extended by y.layout.router.polyline.EdgeRouter
All Implemented Interfaces:
Layouter, LayoutStage

public class EdgeRouter
extends AbstractLayoutStage

This edge routing algorithm applies polyline routes to the edges of the graph.

Layout Style

Edges are normally routed in an orthogonal fashion, i.e., they only consist of horizontal and vertical segments. There is also a routing style in which, between horizontal and vertical segments, additional segments with other slopes are inserted.

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 as polyline or orthogonal 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 polyline routing and grouped edges

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

Sample output with bus-style routing

Concept

The edge routing algorithm basically performs three (four) steps to achieve an orthogonal (polyline) edge routing.

  1. Creating a Partition which divides the area of the graph area into several PartitionCells.
  2. Finding the shortest/cheapest paths for all edges through the Partition 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 (only if polyline routing is enabled).

The first two steps are customizable. GraphPartitionExtensions are able to influence how the Partition 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 Partition 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 EdgeLayoutDescriptors, it is possible to add individual layout settings like routing styles to edges. They are registered with the graph with key EDGE_LAYOUT_DESCRIPTOR_DPKEY. 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 PortCandidateSet.CandidateMatcher 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 ColumnDescriptor.getOriginalPosition(), RowDescriptor.getOriginalPosition() ColumnDescriptor.getOriginalWidth() and RowDescriptor.getOriginalHeight() 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. ColumnDescriptor.getComputedPosition()), 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 DataProviders that provide the same ID object for all edges in the same group. Those DataProviders are registered with the graph with key PortConstraintKeys.SOURCE_GROUPID_KEY for source groups or key PortConstraintKeys.TARGET_GROUPID_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 DataProvider and register it to the graph with key PortConstraintKeys.SOURCE_PORT_GROUP_ID_DPKEY for source port groups or key PortConstraintKeys.TARGET_PORT_GROUP_ID_DPKEY 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 BusDescriptor (see also BUS_DESCRIPTOR_DPKEY). 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 BusDescriptor.setBusPoints(YPointPath). 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.

 
All source/target grouped edges share the same source/target port. Hence, assigning them to different fixed port locations (with PortConstraints or PortCandidates) doesn't make sense.
 

Field Summary
static java.lang.Object BUS_DESCRIPTOR_DPKEY
          A DataProvider key for specifying a bus descriptor for each edge Edges can be assigned to a BusDescriptor instance; all edges associated to the same descriptor are routed in a bus-like style.
static java.lang.String EDGE_LAYOUT_DESCRIPTOR_DPKEY
          A DataProvider key for specifying individual edge layout information If this DataProvider does not contain an EdgeLayoutDescriptor for an edge, then the layout algorithm will use the default descriptor.
static java.lang.String LABEL_CROSSING_COST_FACTOR_DPKEY
          A DataProvider key for weighting the costs for crossing each label individually If the factor for a label is 0 then it is allowed to cross it.
static byte ROUTE_ALL_EDGES
          A scope specifier which defines that all edges of the input graph will be routed.
static byte ROUTE_EDGES_AT_SELECTED_NODES
          A scope specifier which defines that only edges incident to selected nodes will be routed.
static byte ROUTE_SELECTED_EDGES
          A scope specifier which defines that only the selected edges of the input graph will be routed.
 
Fields inherited from interface y.layout.Layouter
EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES
 
Constructor Summary
EdgeRouter()
          Creates a new EdgeRouter instance with default settings.
EdgeRouter(Layouter core)
          Creates a new EdgeRouter instance with a given core layouter and default settings.
 
Method Summary
 boolean canLayout(LayoutGraph graph)
          Accepts general graphs without exceptions.
protected  void checkGroupNodeSize(GraphLayout layout, java.lang.Object node)
          Checks whether or not the width/height of a given group node is zero or negative.
protected  void checkNodeSize(GraphLayout layout, java.lang.Object node)
          Checks whether or not the width/height of a given node is zero or negative.
protected  void cleanupGraphPartition(GraphPartition partition)
          Removes all registered GraphPartitionExtensions from a given GraphPartition instance.
protected  void configureGraphPartition(GraphPartition partition)
          Adds all registered GraphPartitionExtensions instances to a given GraphPartition instance.
protected  void configurePathSearch(PathSearch pathSearch)
          Adds all registered PathSearchExtensions to a given PathSearch instance.
protected  PathSearchConfiguration createConfiguration(LayoutGraph graph, Grouping grouping)
          Creates a PathSearchConfiguration that is used during the path searching process.
protected  java.util.Comparator createDefaultEdgeOrderComparator(LayoutGraph graph, PathSearchConfiguration configuration)
          Creates a default Comparator instance to determine the order of the edges according to which they will be routed.
protected  GraphPartition createGraphPartition(ObstaclePartition decomposition)
          Creates a GraphPartition instance that divides the area of the graph into several rectangles.
protected  DynamicObstacleDecomposition createObstacleDecomposition()
          Creates a DynamicObstacleDecomposition that is used by the GraphPartition to divide the graph area in rectangles.
protected  ChannelBasedPathRouting createPathRouting()
          Creates a ChannelBasedPathRouting instance that routes the edges using pre-calculated Path objects.
protected  PathSearch createPathSearch()
          Creates a PathSearch instance that finds the paths of the edges through the GraphPartition.
protected  PathSearchContext createPathSearchContext(PathSearch pathSearch, PathSearchConfiguration configuration)
          Creates a PathSearchContext that provides context information for the path searching algorithm.
 void doLayout(LayoutGraph graph)
          Performs the routing of the edges of the input graph.
 EdgeLayoutDescriptor getDefaultEdgeLayoutDescriptor()
          Returns the EdgeLayoutDescriptor instance used for all those edges that do not have a specific edge layout descriptor assigned.
protected  EdgeLayoutDescriptor getEdgeLayoutDescriptor(Edge edge)
          Returns the EdgeLayoutDescriptor instance for a given edge that is provided by a DataProvider which is registered with the graph with key EDGE_LAYOUT_DESCRIPTOR_DPKEY.
 java.util.Comparator getEdgeOrderComparator()
          Returns a custom Comparator to define the processing order of the edges.
 Grid getGrid()
          Returns the Grid instance on which the routing algorithm places the orthogonal segments.
 long getMaximumDuration()
          Returns the time limit (in milliseconds) set for the edge routing algorithm.
 double getMaximumPolylineSegmentRatio()
          Returns the maximum ratio between the horizontal/vertical part of a segment and the (non-orthogonal) polyline part.
 double getMinimalNodeToEdgeDistance()
          Returns the minimum distance between edges and node bounds.
 GraphPartition getPartition()
          Returns the GraphPartition instance used during the routing process.
 double getPreferredPolylineSegmentLength()
          Returns the preferred length of (non-orthogonal) polyline segments.
 java.util.List getRegisteredPartitionExtensions()
          Returns a list of all registered GraphPartitionExtensions.
 java.util.List getRegisteredPathSearchExtensions()
          Returns a list of all registered PathSearchExtensions.
 java.lang.Object getSelectedEdgesDpKey()
          Returns the DataProvider key to look up the selection state of the edges.
 java.lang.Object getSelectedNodesDpKey()
          Returns the DataProvider key to look up the selection state of the nodes.
 byte getSphereOfAction()
          Returns a (sub-)set of edges that shall be routed.
 boolean isConsiderEdgeLabelsEnabled()
          Returns whether or not the routing algorithm considers as obstacles the edge labels that do not belong to the (sub-)set of edges to be routed when calculating the edge routes.
 boolean isConsiderNodeLabelsEnabled()
          Returns whether or not the routing algorithm considers the labels of the nodes as obstacles when calculating the edge routes to avoid overlaps.
 boolean isIgnoreInnerNodeLabelsEnabled()
          Returns whether or not this routing algorithm ignores node labels that are inside the bounds of their owner as obstacles for edge routes.
 boolean isIntegratedEdgeLabelingEnabled()
          Returns whether or not the layout algorithm will place edge labels.
 boolean isPolylineRoutingEnabled()
          Returns whether or not the routing algorithm will route the edges of the graph with (non-orthogonal) polyline segments.
 boolean isReroutingEnabled()
          Returns whether or not the routing algorithm uses an additional step to reroute the edges that are considered to have the worst paths.
protected  boolean isSelected(Edge edge, Graph graph)
          Returns whether or not a given edge is selected.
 void setConsiderEdgeLabelsEnabled(boolean considerEdgeLabelsEnabled)
          Specifies whether or not the routing algorithm considers as obstacles the edge labels that do not belong to the (sub-)set of edges to be routed when calculating the edge routes.
 void setConsiderNodeLabelsEnabled(boolean considerNodeLabelsEnabled)
          Specifies whether or not the routing algorithm considers the labels of the nodes as obstacles when calculating the edge routes to avoid overlaps.
 void setEdgeOrderComparator(java.util.Comparator edgeOrderComparator)
          Specifies a custom Comparator to define the processing order of the edges.
 void setGrid(Grid grid)
          Specifies the Grid instance on which the routing algorithm places the orthogonal segments.
 void setIgnoreInnerNodeLabelsEnabled(boolean ignoreInnerNodeLabelsEnabled)
          Specifies whether or not this routing algorithm ignores node labels that are inside the bounds of their owner as obstacles for edge routes.
 void setIntegratedEdgeLabelingEnabled(boolean enabled)
          Specifies whether or not the layout algorithm will place edge labels.
 void setMaximumDuration(long maximumDuration)
          Specifies the time limit (in milliseconds) for the edge routing algorithm.
 void setMaximumPolylineSegmentRatio(double maximumPolylineSegmentRatio)
          Specifies the maximum ratio between the horizontal/vertical part of a segment and the (non-orthogonal) polyline part.
 void setMinimalNodeToEdgeDistance(double minimalNodeToEdgeDistance)
          Specifies the minimum distance between edges and node bounds.
 void setPolylineRoutingEnabled(boolean polylineRoutingEnabled)
          Specifies whether or not the routing algorithm will route the edges of the graph with (non-orthogonal) polyline segments.
 void setPreferredPolylineSegmentLength(double preferredPolylineSegmentLength)
          Specifies the preferred length of (non-orthogonal) polyline segments.
 void setReroutingEnabled(boolean reroutingEnabled)
          Specifies whether or not the routing algorithm uses an additional step to reroute the edges that are considered to have the worst paths.
 void setSelectedEdgesDpKey(java.lang.Object selectedEdgesDpKey)
          Specifies the DataProvider key to look up the selection state of the edges.
 void setSelectedNodesDpKey(java.lang.Object key)
          Specifies the DataProvider key to look up the selection state of the nodes.
 void setSphereOfAction(byte scope)
          Specifies a (sub-)set of edges that shall be routed.
 
Methods inherited from class y.layout.AbstractLayoutStage
canLayoutCore, doLayoutCore, getCoreLayouter, setCoreLayouter
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

EDGE_LAYOUT_DESCRIPTOR_DPKEY

public static final java.lang.String EDGE_LAYOUT_DESCRIPTOR_DPKEY
A DataProvider key for specifying individual edge layout information If this DataProvider does not contain an EdgeLayoutDescriptor for an edge, then the layout algorithm will use the default descriptor.

See Also:
getDefaultEdgeLayoutDescriptor(), Constant Field Values

BUS_DESCRIPTOR_DPKEY

public static final java.lang.Object BUS_DESCRIPTOR_DPKEY
A DataProvider key for specifying a bus descriptor for each edge

Edges can be assigned to a BusDescriptor instance; all edges associated to the same descriptor are routed in a bus-like style. A bus is a segment shared by multiple edges to which shorter segments that connect to the actual nodes are attached. Observe that using such a bus representation with multiple edges drawn on top of each other, information like the individual edge direction might be occluded.

The mapped BusDescriptor allows to configure the bus formed by the associated edges.

 
Bus routing can, for example, be very useful in parts of a diagram where each node is connected to each other node.
 
Intermediate points are ignored for edges that are part of a bus structure.
See Also:
BusDescriptor

LABEL_CROSSING_COST_FACTOR_DPKEY

public static final java.lang.String LABEL_CROSSING_COST_FACTOR_DPKEY
A DataProvider key for weighting the costs for crossing each label individually If the factor for a label is 0 then it is allowed to cross it. Very important labels should get a high factor.

This factor is multiplied by the basic penalty arising when an edge must cross a node label or an edge label in order to determine the final costs arising when this label is crossed.

See Also:
getDefaultEdgeLayoutDescriptor(), EdgeLayoutDescriptor.getPenaltySettings(), Constant Field Values

ROUTE_ALL_EDGES

public static final byte ROUTE_ALL_EDGES
A scope specifier which defines that all edges of the input graph will be routed.

See Also:
setSphereOfAction(byte), Constant Field Values
Sample Graphs:
Initial graph All edges routed by this edge routing algorithm

ROUTE_SELECTED_EDGES

public static final byte ROUTE_SELECTED_EDGES
A scope specifier which defines that only the selected edges of the input graph will be routed.

The selection state of an edge is determined by a boolean value returned by a DataProvider registered with key getSelectedEdgesDpKey().

All other non-selected edges will be considered to have fixed routes.

See Also:
setSphereOfAction(byte), setSelectedEdgesDpKey(Object), Constant Field Values
Sample Graphs:
Initial graph Only selected (marked) edges routed by this edge routing algorithm

ROUTE_EDGES_AT_SELECTED_NODES

public static final byte ROUTE_EDGES_AT_SELECTED_NODES
A scope specifier which defines that only edges incident to selected nodes will be routed.

The selection state of a node is determined by a boolean value returned by a DataProvider registered with key getSelectedNodesDpKey().

All other edges that are incident to non-selected nodes will be considered to have fixed routes.

See Also:
setSphereOfAction(byte), setSelectedNodesDpKey(Object), Constant Field Values
Sample Graphs:
Initial graph Only edges connected to selected (marked) nodes routed by this edge routing algorithm
Constructor Detail

EdgeRouter

public EdgeRouter(Layouter core)
Creates a new EdgeRouter instance with a given core layouter and default settings.

Parameters:
core - the given core layouter

EdgeRouter

public EdgeRouter()
Creates a new EdgeRouter instance with default settings.

Method Detail

getMaximumDuration

public long getMaximumDuration()
Returns the time limit (in milliseconds) set for the edge routing algorithm.

The maximum duration has to be greater than or equal to 0.

 
Restricting the maximum duration may result in a lower layout quality. Furthermore, the real runtime may exceed the maximum duration since the edge routing algorithm still has to find a valid solution.
Returns:
a non-negative integer value
See Also:
setMaximumDuration(long)

setMaximumDuration

public void setMaximumDuration(long maximumDuration)
Specifies the time limit (in milliseconds) for the edge routing algorithm.

The maximum duration has to be greater than or equal to 0.

 
Restricting the maximum duration may result in a lower layout quality. Furthermore, the real runtime may exceed the maximum duration since the edge routing algorithm still has to find a valid solution.
Default Value:
The default value is Long.MAX_VALUE. The edge routing algorithm runs unrestricted.
Parameters:
maximumDuration - a non-negative integer value
Throws:
java.lang.IllegalArgumentException - if the maximum duration is negative

getDefaultEdgeLayoutDescriptor

public EdgeLayoutDescriptor getDefaultEdgeLayoutDescriptor()
Returns the EdgeLayoutDescriptor instance used for all those edges that do not have a specific edge layout descriptor assigned.

Returns:
the default EdgeLayoutDescriptor
See Also:
EDGE_LAYOUT_DESCRIPTOR_DPKEY

getEdgeLayoutDescriptor

protected EdgeLayoutDescriptor getEdgeLayoutDescriptor(Edge edge)
Returns the EdgeLayoutDescriptor instance for a given edge that is provided by a DataProvider which is registered with the graph with key EDGE_LAYOUT_DESCRIPTOR_DPKEY.

For all those edges that do not have a specific layout descriptor assigned, the default layout descriptor returned by getDefaultEdgeLayoutDescriptor() will be assigned.

This method may be overridden in order to create an EdgeLayoutDescriptor with custom configuration.

Parameters:
edge - the given edge
Returns:
the current EdgeLayoutDescriptor instance for a given edge
See Also:
getDefaultEdgeLayoutDescriptor(), EDGE_LAYOUT_DESCRIPTOR_DPKEY

isIntegratedEdgeLabelingEnabled

public boolean isIntegratedEdgeLabelingEnabled()
Returns whether or not the layout algorithm will place edge labels.

Enabling this feature, the routes of edges with labels can change significantly. The algorithm finds a position for labels and routes the edge near the label trying to consider the PreferredPlacementDescriptor. To do so, the route itself maybe needs to take a detour that might otherwise not have been necessary. This especially holds true in case that there is very little space for the labels and/or the labels are rather large.

 
When this option is enabled, the overall runtime may increase significantly. Hence, if a short runtime is required or the resulting routes have too many bend artifacts (mainly happens if there is little space), applying the generic labeling as post-processing step may be an alternative.
Returns:
true if edge labels should be placed, false otherwise
See Also:
setIntegratedEdgeLabelingEnabled(boolean), setConsiderEdgeLabelsEnabled(boolean)

setIntegratedEdgeLabelingEnabled

public void setIntegratedEdgeLabelingEnabled(boolean enabled)
Specifies whether or not the layout algorithm will place edge labels.

Enabling this feature, the routes of edges with labels can change significantly. The algorithm finds a position for labels and routes the edge near the label trying to consider the PreferredPlacementDescriptor. To do so, the route itself maybe needs to take a detour that might otherwise not have been necessary. This especially holds true in case that there is very little space for the labels and/or the labels are rather large.

 
When this option is enabled, the overall runtime may increase significantly. Hence, if a short runtime is required or the resulting routes have too many bend artifacts (mainly happens if there is little space), applying the generic labeling as post-processing step may be an alternative.
Default Value:
The default value is false. Integrated edge labeling is disabled.
Parameters:
enabled - true if edge labels should be placed, false otherwise
See Also:
setConsiderEdgeLabelsEnabled(boolean)

isPolylineRoutingEnabled

public boolean isPolylineRoutingEnabled()
Returns whether or not the routing algorithm will route the edges of the graph with (non-orthogonal) polyline segments.

 
Backbone segments of a bus are always routed orthogonally, even if this property is enabled. On the other hand, bus connections that lead from the backbone to the actual end nodes comply with this property.
Returns:
true if the routing algorithm creates (non-orthogonal) polyline segments, false otherwise
See Also:
setPolylineRoutingEnabled(boolean), getPreferredPolylineSegmentLength(), getMaximumPolylineSegmentRatio()

setPolylineRoutingEnabled

public void setPolylineRoutingEnabled(boolean polylineRoutingEnabled)
Specifies whether or not the routing algorithm will route the edges of the graph with (non-orthogonal) polyline segments.

 
Backbone segments of a bus are always routed orthogonally, even if this property is enabled. On the other hand, bus connections that lead from the backbone to the actual end nodes comply with this property.
Default Value:
The default value is false. The polyline edge routing is disabled.
Parameters:
polylineRoutingEnabled - true if the routing algorithm creates (non-orthogonal) polyline segments, false otherwise
See Also:
setPreferredPolylineSegmentLength(double), setMaximumPolylineSegmentRatio(double)
Sample Graphs:
false true

getPreferredPolylineSegmentLength

public double getPreferredPolylineSegmentLength()
Returns the preferred length of (non-orthogonal) polyline segments. If there is not enough space to use this preferred length, polyline segments may also be shorter.

The preferred length of (non-orthogonal) polyline segments has to be greater than or equal to 0.

 
This restriction applies only if polyline routing is enabled.
Returns:
the preferred length of (non-orthogonal) polyline segments
See Also:
setPreferredPolylineSegmentLength(double), getMaximumPolylineSegmentRatio()

setPreferredPolylineSegmentLength

public void setPreferredPolylineSegmentLength(double preferredPolylineSegmentLength)
Specifies the preferred length of (non-orthogonal) polyline segments. If there is not enough space to use this preferred length, polyline segments may also be shorter.

The preferred length of (non-orthogonal) polyline segments has to be greater than or equal to 0.

 
This restriction applies only if polyline routing is enabled.
Default Value:
The default value is 30.
Parameters:
preferredPolylineSegmentLength - the preferred length of (non-orthogonal) polyline segments
Throws:
java.lang.IllegalArgumentException - if the preferred polyline segment length is negative
See Also:
setPolylineRoutingEnabled(boolean), setMaximumPolylineSegmentRatio(double)
Sample Graphs:
Preferred polyline segment 10 Preferred polyline segment 50

getMaximumPolylineSegmentRatio

public double getMaximumPolylineSegmentRatio()
Returns the maximum ratio between the horizontal/vertical part of a segment and the (non-orthogonal) polyline part.

When polyline segments are added to an edge path, corners between horizontal and vertical segments are cut and replaced by the new segment. This ratio describes the cutting points on a segment. If it is zero, the route stays orthogonal. The value cannot be larger than 0.5 because there may be another polyline segment at the other side of the segment. For long orthogonal segments the length of the polyline segment is determined by the value returned by getPreferredPolylineSegmentLength().

The maximum polyline segment ratio must be between 0 and 0.5.

Returns:
the maximum polyline segment ratio
See Also:
setMaximumPolylineSegmentRatio(double)

setMaximumPolylineSegmentRatio

public void setMaximumPolylineSegmentRatio(double maximumPolylineSegmentRatio)
Specifies the maximum ratio between the horizontal/vertical part of a segment and the (non-orthogonal) polyline part.

When polyline segments are added to an edge path, corners between horizontal and vertical segments are cut and replaced by the new segment. This ratio describes the cutting points on a segment. If it is zero, the route stays orthogonal. The value cannot be larger than 0.5 because there may be another polyline segment at the other side of the segment. For long orthogonal segments the length of the polyline segment is determined by the value returned by getPreferredPolylineSegmentLength().

The maximum polyline segment ratio must be between 0 and 0.5.

Default Value:
The default value is 0.3.
Parameters:
maximumPolylineSegmentRatio - the maximum polyline segment ratio
Throws:
java.lang.IllegalArgumentException - if the maximum segment length is negative or greater than 0.5
Sample Graphs:
Ratio 0.3, the octilinear parts from left and right both cover a third of the horizontal distance Ratio 0.5, the octilinear parts from left and right both cover half of the horizontal distance

isReroutingEnabled

public boolean isReroutingEnabled()
Returns whether or not the routing algorithm uses an additional step to reroute the edges that are considered to have the worst paths.

 
The rerouting step will only be applied if the maximum duration has not been exceeded yet.
Returns:
true if the rerouting step will be performed, false otherwise
See Also:
setReroutingEnabled(boolean)

setReroutingEnabled

public void setReroutingEnabled(boolean reroutingEnabled)
Specifies whether or not the routing algorithm uses an additional step to reroute the edges that are considered to have the worst paths.

 
The rerouting step will only be applied if the maximum duration has not been exceeded yet.
Default Value:
The default value is false. The rerouting step will not be performed.
Parameters:
reroutingEnabled - true if the rerouting step will be performed, false otherwise

setSphereOfAction

public void setSphereOfAction(byte scope)
Specifies a (sub-)set of edges that shall be routed.

Default Value:
The default value is ROUTE_ALL_EDGES
Parameters:
scope - one of the default scope values
Throws:
java.lang.IllegalArgumentException - if the given scope is unknown
See Also:
getSelectedEdgesDpKey()

getSphereOfAction

public byte getSphereOfAction()
Returns a (sub-)set of edges that shall be routed.

Returns:
one of the default scope values
See Also:
setSphereOfAction(byte), getSelectedEdgesDpKey()

getSelectedNodesDpKey

public java.lang.Object getSelectedNodesDpKey()
Returns the DataProvider key to look up the selection state of the nodes.

If the scope is set to ROUTE_EDGES_AT_SELECTED_NODES, only the edges that are incident to selected nodes will be routed, while all other edges will be considered to have fixed routes.

Returns:
the DataProvider key for the node selection
See Also:
setSphereOfAction(byte), setSelectedNodesDpKey(Object)

setSelectedNodesDpKey

public void setSelectedNodesDpKey(java.lang.Object key)
Specifies the DataProvider key to look up the selection state of the nodes.

If the scope is set to ROUTE_EDGES_AT_SELECTED_NODES, only the edges that are incident to selected nodes will be routed, while all other edges will be considered to have fixed routes.

Default Value:
The default value is Layouter.SELECTED_NODES
Parameters:
key - the DataProvider key for node selection
Throws:
java.lang.IllegalArgumentException - if the specified DataProvider key is null
See Also:
setSphereOfAction(byte), getSelectedNodesDpKey()

getSelectedEdgesDpKey

public java.lang.Object getSelectedEdgesDpKey()
Returns the DataProvider key to look up the selection state of the edges.

If the scope is set to ROUTE_SELECTED_EDGES, only the selected edges will be routed, while all other edges will be considered to have fixed routes.

Returns:
the DataProvider key for the edge selection
See Also:
setSphereOfAction(byte), setSelectedEdgesDpKey(Object)

setSelectedEdgesDpKey

public void setSelectedEdgesDpKey(java.lang.Object selectedEdgesDpKey)
Specifies the DataProvider key to look up the selection state of the edges.

If the scope is set to ROUTE_SELECTED_EDGES, only the selected edges will be routed, while all other edges will be considered to have fixed routes.

Default Value:
The default value is Layouter.SELECTED_EDGES
Parameters:
selectedEdgesDpKey - the DataProvider key for edge selection
Throws:
java.lang.IllegalArgumentException - if the specified DataProvider key is null
See Also:
setSphereOfAction(byte), getSelectedEdgesDpKey()

getEdgeOrderComparator

public java.util.Comparator getEdgeOrderComparator()
Returns a custom Comparator to define the processing order of the edges.

 
The processing order may affect the quality of the individual edge paths. When routing an edge, only the paths of the already routed edges and of the fixed edges (that will not be routed at all) can be considered. Therefore, edges that are processed first have to consider less other edge paths than the edges that are processed later, which might have to use less optimal alternative paths.
 
When defining edge or port groups, the custom processing order defined by this property is not fully obeyed. Edges that are grouped are routed together as a bundle. For example, assume that edge0 and edge2 are grouped and edge1 should be routed after edge0 but before edge2: the grouped edges are routed as a bundle, either both before or both after edge1. Note that the same is true for edges that share common bus segments, see BUS_DESCRIPTOR_DPKEY.
Returns:
the current Comparator instance
See Also:
setEdgeOrderComparator(Comparator), createDefaultEdgeOrderComparator(LayoutGraph, PathSearchConfiguration)

setEdgeOrderComparator

public void setEdgeOrderComparator(java.util.Comparator edgeOrderComparator)
Specifies a custom Comparator to define the processing order of the edges.

 
The processing order may affect the quality of the individual edge paths. When routing an edge, only the paths of the already routed edges and of the fixed edges (that will not be routed at all) can be considered. Therefore, edges that are processed first have to consider less other edge paths than the edges that are processed later, which might have to use less optimal alternative paths.
 
When defining edge or port groups, the custom processing order defined by this property is not fully obeyed. Edges that are grouped are routed together as a bundle. For example, assume that edge0 and edge2 are grouped and edge1 should be routed after edge0 but before edge2: the grouped edges are routed as a bundle, either both before or both after edge1. Note that the same is true for edges that share common bus segments, see BUS_DESCRIPTOR_DPKEY.
Default Value:
The default value is Comparator. The comparator returned by getEdgeOrderComparator().
Parameters:
edgeOrderComparator - the current Comparator instance

canLayout

public boolean canLayout(LayoutGraph graph)
Accepts general graphs without exceptions.

Parameters:
graph - the input graph
Returns:
true for all input graphs
See Also:
Layouter.doLayout(LayoutGraph)

isSelected

protected boolean isSelected(Edge edge,
                             Graph graph)
Returns whether or not a given edge is selected.

If all the edges of the graph will be routed by EdgeRouter, i.e., the scope is set to ROUTE_ALL_EDGES, this utility method returns true for all edges.

This method may be overridden in order to determine differently whether or not a given edge is considered to be selected.

Parameters:
edge - the given edge
graph - the input graph
Returns:
true if the given edge is selected, false otherwise

setConsiderNodeLabelsEnabled

public void setConsiderNodeLabelsEnabled(boolean considerNodeLabelsEnabled)
Specifies whether or not the routing algorithm considers the labels of the nodes as obstacles when calculating the edge routes to avoid overlaps.

 
This option takes effect only if getSphereOfAction() is set to ROUTE_EDGES_AT_SELECTED_NODES and a DataProvider instance with the key getSelectedNodesDpKey() is registered with the graph.
Default Value:
The default value is false. Node labels are not considered.
Parameters:
considerNodeLabelsEnabled - true if the node labels should be considered, false otherwise
See Also:
PenaltySettings.getNodeLabelCrossingPenalty()
Sample Graphs:
falsetrue

isConsiderNodeLabelsEnabled

public boolean isConsiderNodeLabelsEnabled()
Returns whether or not the routing algorithm considers the labels of the nodes as obstacles when calculating the edge routes to avoid overlaps.

 
This option takes effect only if getSphereOfAction() is set to ROUTE_EDGES_AT_SELECTED_NODES and a DataProvider instance with the key getSelectedNodesDpKey() is registered with the graph.
Returns:
true if the node labels are considered, false otherwise
See Also:
setConsiderNodeLabelsEnabled(boolean), PenaltySettings.getNodeLabelCrossingPenalty()

setIgnoreInnerNodeLabelsEnabled

public void setIgnoreInnerNodeLabelsEnabled(boolean ignoreInnerNodeLabelsEnabled)
Specifies whether or not this routing algorithm ignores node labels that are inside the bounds of their owner as obstacles for edge routes.

 
This setting can be applied only if node labels are considered and is especially useful in order to ignore inner node labels of group nodes.
Default Value:
The default value is false. Node labels that are inside the bounds of their owner are not ignored.
Parameters:
ignoreInnerNodeLabelsEnabled - true if the routing algorithm should ignore inner node labels, false otherwise
See Also:
isConsiderNodeLabelsEnabled(), PenaltySettings.getNodeLabelCrossingPenalty(), LABEL_CROSSING_COST_FACTOR_DPKEY
Sample Graphs:
false true

isIgnoreInnerNodeLabelsEnabled

public boolean isIgnoreInnerNodeLabelsEnabled()
Returns whether or not this routing algorithm ignores node labels that are inside the bounds of their owner as obstacles for edge routes.

 
This setting can be applied only if node labels are considered and is especially useful in order to ignore inner node labels of group nodes.
Returns:
true if the routing algorithm ignores inner node labels, false otherwise
See Also:
setIgnoreInnerNodeLabelsEnabled(boolean), isConsiderNodeLabelsEnabled(), PenaltySettings.getNodeLabelCrossingPenalty(), LABEL_CROSSING_COST_FACTOR_DPKEY

setConsiderEdgeLabelsEnabled

public void setConsiderEdgeLabelsEnabled(boolean considerEdgeLabelsEnabled)
Specifies whether or not the routing algorithm considers as obstacles the edge labels that do not belong to the (sub-)set of edges to be routed when calculating the edge routes.

 
If labels of routed edges should be placed, too, enable property setIntegratedEdgeLabelingEnabled(boolean).
 
This option takes effect only if getSphereOfAction() is set to ROUTE_SELECTED_EDGES and a DataProvider instance with the key getSelectedEdgesDpKey() is registered with the graph.
Default Value:
The default value is false. Edge labels of fixed edges are not considered.
Parameters:
considerEdgeLabelsEnabled - true if labels of fixed edges should be considered, false otherwise
See Also:
setSphereOfAction(byte), setSelectedEdgesDpKey(Object), PenaltySettings.getEdgeLabelCrossingPenalty()
Sample Graphs:
false true

isConsiderEdgeLabelsEnabled

public boolean isConsiderEdgeLabelsEnabled()
Returns whether or not the routing algorithm considers as obstacles the edge labels that do not belong to the (sub-)set of edges to be routed when calculating the edge routes.

 
If labels of routed edges should be placed, too, enable property setIntegratedEdgeLabelingEnabled(boolean).
 
This option takes effect only if getSphereOfAction() is set to ROUTE_SELECTED_EDGES and a DataProvider instance with the key getSelectedEdgesDpKey() is registered with the graph.
Returns:
true if labels of fixed edges are considered, false otherwise
See Also:
setConsiderEdgeLabelsEnabled(boolean), setSphereOfAction(byte), setSelectedEdgesDpKey(Object), PenaltySettings.getEdgeLabelCrossingPenalty()

getGrid

public Grid getGrid()
Returns the Grid instance on which the routing algorithm places the orthogonal segments.

Returns:
the Grid instance
See Also:
setGrid(Grid)

setGrid

public void setGrid(Grid grid)
Specifies the Grid instance on which the routing algorithm places the orthogonal segments.

Default Value:
The default value is null. No grid is specified.
Parameters:
grid - the Grid instance
Sample Graphs:
No grid Grid with spacing 20

setMinimalNodeToEdgeDistance

public void setMinimalNodeToEdgeDistance(double minimalNodeToEdgeDistance)
Specifies the minimum distance between edges and node bounds.

The minimum distance should have a non-negative value.

Default Value:
The default value is 10.
Parameters:
minimalNodeToEdgeDistance - the non-negative minimum distance
Throws:
java.lang.IllegalArgumentException - if the minimum node-to-edge distance is negative
See Also:
PenaltySettings.getMinimalNodeToEdgeDistancePenalty()
Sample Graphs:
Minimum node-to-edge distance 10 Minimum node-to-edge distance 100

getMinimalNodeToEdgeDistance

public double getMinimalNodeToEdgeDistance()
Returns the minimum distance between edges and node bounds.

The minimum distance should have a non-negative value.

Returns:
the non-negative minimum distance
See Also:
setMinimalNodeToEdgeDistance(double), PenaltySettings.getMinimalNodeToEdgeDistancePenalty()

createGraphPartition

protected GraphPartition createGraphPartition(ObstaclePartition decomposition)
Creates a GraphPartition instance that divides the area of the graph into several rectangles.

This implementation creates a GraphPartition using the current ObstaclePartition instance.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to create a new GraphPartition object with a custom configuration.

Parameters:
decomposition - the current ObstaclePartition
Returns:
a GraphPartition instance
See Also:
configureGraphPartition(GraphPartition), getRegisteredPartitionExtensions()

configureGraphPartition

protected void configureGraphPartition(GraphPartition partition)
Adds all registered GraphPartitionExtensions instances to a given GraphPartition instance.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to adjust the configuration of the GraphPartition instance.

Parameters:
partition - the given GraphPartition instance
See Also:
getRegisteredPartitionExtensions(), cleanupGraphPartition(GraphPartition)

cleanupGraphPartition

protected void cleanupGraphPartition(GraphPartition partition)
Removes all registered GraphPartitionExtensions from a given GraphPartition instance.

This method is called by doLayout(LayoutGraph) after the edge routes are calculated. It may be overridden in order to provide a custom implementation for cleaning up a GraphPartition instance.

Parameters:
partition - the given GraphPartition instance
See Also:
configureGraphPartition(GraphPartition), getRegisteredPartitionExtensions()

getRegisteredPartitionExtensions

public java.util.List getRegisteredPartitionExtensions()
Returns a list of all registered GraphPartitionExtensions.

GraphPartitionExtensions can be added to a GraphPartition in order to create new Obstacles or can be removed from a GraphPartition instance.

By default, the following GraphPartitionExtensions are registered with a given GraphPartition instance:

Returns:
a list containing all registered GraphPartitionExtensions
See Also:
createGraphPartition(ObstaclePartition), configureGraphPartition(GraphPartition)

createPathSearch

protected PathSearch createPathSearch()
Creates a PathSearch instance that finds the paths of the edges through the GraphPartition.

This method may be overridden in order to create a new PathSearch object with custom configuration.

Returns:
a PathSearch instance
See Also:
configurePathSearch(PathSearch), getRegisteredPathSearchExtensions()

configurePathSearch

protected void configurePathSearch(PathSearch pathSearch)
Adds all registered PathSearchExtensions to a given PathSearch instance.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to adjust the configuration of a PathSearch instance.

Parameters:
pathSearch - a PathSearch instance
See Also:
createPathSearch(), getRegisteredPathSearchExtensions()

getRegisteredPathSearchExtensions

public java.util.List getRegisteredPathSearchExtensions()
Returns a list of all registered PathSearchExtensions.

PathSearchExtensions can be added to a PathSearch instance in order to influence the path searching process or can be removed from a PathSearch instance.

By default, the following PathSearchExtensions are registered with a PathSearch instance:

Returns:
a list containing all registered PathSearchExtensions
See Also:
createPathSearch(), configurePathSearch(PathSearch)

createPathRouting

protected ChannelBasedPathRouting createPathRouting()
Creates a ChannelBasedPathRouting instance that routes the edges using pre-calculated Path objects.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to create a new ChannelBasedPathRouting object with custom configuration.

Returns:
a ChannelBasedPathRouting instance

createObstacleDecomposition

protected DynamicObstacleDecomposition createObstacleDecomposition()
Creates a DynamicObstacleDecomposition that is used by the GraphPartition to divide the graph area in rectangles.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to create a new DynamicObstacleDecomposition object with custom configuration.

Returns:
a DynamicObstacleDecomposition instance
See Also:
createGraphPartition(ObstaclePartition)

createPathSearchContext

protected PathSearchContext createPathSearchContext(PathSearch pathSearch,
                                                    PathSearchConfiguration configuration)
Creates a PathSearchContext that provides context information for the path searching algorithm.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to create a new PathSearchContext object with custom configuration.

Parameters:
pathSearch - a given PathSearch instance
configuration - a given configuration for the path searching process
Returns:
a PathSearchContext instance

createConfiguration

protected PathSearchConfiguration createConfiguration(LayoutGraph graph,
                                                      Grouping grouping)
Creates a PathSearchConfiguration that is used during the path searching process.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to create a new PathSearchConfiguration object with custom configuration.

Parameters:
graph - the input graph
grouping - the grouping structure of the graph
Returns:
a PathSearchConfiguration instance

doLayout

public void doLayout(LayoutGraph graph)
Performs the routing of the edges of the input graph.

This method also prepares the graph for the edge routing process.

 
The given graph will not be copied during the edge routing process and the result will be immediately applied to the input graph.
Parameters:
graph - the input graph
See Also:
Layouter.canLayout(LayoutGraph)

createDefaultEdgeOrderComparator

protected java.util.Comparator createDefaultEdgeOrderComparator(LayoutGraph graph,
                                                                PathSearchConfiguration configuration)
Creates a default Comparator instance to determine the order of the edges according to which they will be routed.

This method is called by doLayout(LayoutGraph) before the edge routes are calculated. It may be overridden in order to create a new Comparator object with a custom configuration.

By default, this method returns an instance of the default implementation.

Parameters:
graph - the input graph
configuration - the given configuration for the path searching process
Returns:
a Comparator instance

checkNodeSize

protected void checkNodeSize(GraphLayout layout,
                             java.lang.Object node)
                      throws java.lang.IllegalArgumentException
Checks whether or not the width/height of a given node is zero or negative.

This method is called by doLayout(LayoutGraph) for each node of the input graph. It may be overridden in order to obtain a custom implementation of the node size check.

Parameters:
layout - a given GraphLayout instance
node - a given node object
Throws:
java.lang.IllegalArgumentException - if the width/height of the node object is zero or negative
See Also:
checkGroupNodeSize(GraphLayout,Object)

checkGroupNodeSize

protected void checkGroupNodeSize(GraphLayout layout,
                                  java.lang.Object node)
                           throws java.lang.IllegalArgumentException
Checks whether or not the width/height of a given group node is zero or negative.

This method is called by doLayout(LayoutGraph) for each group node of the input graph. It may be overridden in order to obtain a custom implementation of the group node size check.

Parameters:
layout - a given GraphLayout instance
node - a given group node object
Throws:
java.lang.IllegalArgumentException - if the width/height of the group node object is zero or negative
See Also:
checkNodeSize(GraphLayout,Object)

getPartition

public GraphPartition getPartition()
Returns the GraphPartition instance used during the routing process.

 
If the routing process is not running, null will be returned.
Returns:
the current GraphPartition instance

© Copyright 2000-2019,
yWorks GmbH.
All rights reserved.