Search this API

y.layout.router
Class OrthogonalPatternEdgeRouter

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

public class OrthogonalPatternEdgeRouter
extends AbstractLayoutStage

OrthogonalPatternEdgeRouter routes edges orthogonally such that the resulting layout of the edges consists only of vertical and horizontal segments. Note that the location and size of the nodes in a diagram remains unchanged.

The edge router will not try to find a perfect route from source to edge (unlike to what EdgeRouter does) but chooses the best path out of a set of fixed paths. The best path out of these possible paths is determined by its cost. The costs may be influenced by setting several cost factors. The distance that an edge will have from its source and target node is determined by setMinimumDistance(double).

The edges whose paths have to be routed can be defined registering a DataProvider with key AFFECTED_EDGES.

 

Field Summary
static java.lang.Object AFFECTED_EDGES
          A DataProvider key for determining which edges are routed.
static byte MONOTONIC_BOTH
          A monotonic path restriction specifier that describes restrictions for the horizontal and vertical direction.
static byte MONOTONIC_HORIZONTAL
          A monotonic path restriction specifier that describes restrictions for the horizontal direction.
static byte MONOTONIC_NONE
          A monotonic path restriction specifier that describes no restrictions for edges.
static byte MONOTONIC_VERTICAL
          A monotonic path restriction specifier that describes restrictions for the vertical direction.
 
Fields inherited from interface y.layout.Layouter
EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES
 
Constructor Summary
OrthogonalPatternEdgeRouter()
          Creates a new instance of OrthogonalPatternEdgeRouter with default settings.
 
Method Summary
protected  double calculateBendCost(Edge edge, YList path, PortCandidate spc, PortCandidate tpc)
          Calculates the costs for all bends of the given path.
protected  double calculateCost(Edge edge, YList path, PortCandidate spc, PortCandidate tpc)
          Calculates the edge cost of a possible edge path, in order to determine which path is the best, i.e., the cheapest.
protected  double calculateCrossingCosts(Edge edge, YList path, PortCandidate spc, PortCandidate tpc)
          Calculates the overall crossing costs of the given path, including edge crossings, edge overlaps and node crossings.
protected  double calculateEdgeLength(Edge edge, YList path, PortCandidate spc, PortCandidate tpc)
          Calculates the costs for the length of the given path.
protected  double calculatePortCandidateCost(Edge edge, YList path, PortCandidate spc, PortCandidate tpc)
          Calculates the costs for the chosen PortCandidates.
protected  double calculateSelfLoopSelfSidePenaltyCost(Edge edge, YList path, PortCandidate spc, PortCandidate tpc)
          Calculates the extra penalty that is added to the path's cost if the edge is a self-loop and source and target ports have the same direction.
 boolean canLayout(LayoutGraph graph)
          Accepts all graphs that can be handled by the core layout algorithm.
protected  void checkGroupNodeSize(GraphLayout layout, java.lang.Object node)
          Checks the given group node for zero or negative width/height.
protected  void checkNodeSize(GraphLayout layout, java.lang.Object node)
          Checks the given node for zero or negative width/height.
 void doLayout(LayoutGraph graph)
          Routes the edges of the given graph orthogonally.
 java.lang.Object getAffectedEdgesDPKey()
          Returns the key to register a DataProvider which determines the edges that shall be routed by this algorithm.
 double getBendCost()
          Returns the costs for creating a bend on the edge's path.
 double getEdgeCrossingCost()
          Returns the costs for a crossing between two edges.
 double getEdgeOverlapCost()
          Returns the costs for overlapping edge paths.
 YPoint getGridOrigin()
          Returns the origin of the grid.
 double getGridWidth()
          Returns the spacing of the grid on which edges are routed.
 double getMinimumDistance()
          Returns the minimum distance that an edge will maintain from its source and target node.
 byte getMonotonicPathRestriction()
          Returns the monotonic path restriction that should be applied.
 double getNodeCrossingCost()
          Returns the costs for edges that cross nodes.
 boolean isGridRoutingEnabled()
          Returns whether or not to route the edges on a grid.
 void setAffectedEdgesDPKey(java.lang.Object key)
          Specifies the key to register a DataProvider which determines the edges that shall be routed by this algorithm.
 void setBendCost(double bendCost)
          Specifies the costs for creating a bend on the edge's path.
 void setEdgeCrossingCost(double edgeCrossingCost)
          Specifies the costs for a crossing between two edges.
 void setEdgeOverlapCost(double edgeOverlapCost)
          Specifies the costs for overlapping edge paths.
 void setGridOrigin(YPoint gridOrigin)
          Specifies the origin of the grid.
 void setGridRoutingEnabled(boolean gridRoutingEnabled)
          Specifies whether or not to route the edges on a grid.
 void setGridWidth(double gridSpacing)
          Specifies the spacing of the grid on which edges are routed.
 void setMinimumDistance(double minDist)
          Specifies the minimum distance that an edge will maintain from its source and target node.
 void setMonotonicPathRestriction(byte monotonicPathRestriction)
          Specifies the monotonic path restriction that should be applied.
 void setNodeCrossingCost(double nodeCrossingCost)
          Specifies the costs for edges that cross nodes.
 
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

AFFECTED_EDGES

public static final java.lang.Object AFFECTED_EDGES
A DataProvider key for determining which edges are routed.


MONOTONIC_NONE

public static final byte MONOTONIC_NONE
A monotonic path restriction specifier that describes no restrictions for edges.

See Also:
setMonotonicPathRestriction(byte), Constant Field Values

MONOTONIC_VERTICAL

public static final byte MONOTONIC_VERTICAL
A monotonic path restriction specifier that describes restrictions for the vertical direction.

Each vertical edge segment should be directed from the source to the target. Furthermore, each edge path starts and ends with a vertical segment.

See Also:
setMonotonicPathRestriction(byte), Constant Field Values

MONOTONIC_HORIZONTAL

public static final byte MONOTONIC_HORIZONTAL
A monotonic path restriction specifier that describes restrictions for the horizontal direction.

Each horizontal edge segment should be directed from the source to the target. Furthermore, each edge path starts and ends with a horizontal segment.

See Also:
setMonotonicPathRestriction(byte), Constant Field Values

MONOTONIC_BOTH

public static final byte MONOTONIC_BOTH
A monotonic path restriction specifier that describes restrictions for the horizontal and vertical direction.

Each horizontal as well as each vertical edge segment is directed from the source to the target.

See Also:
setMonotonicPathRestriction(byte), Constant Field Values
Constructor Detail

OrthogonalPatternEdgeRouter

public OrthogonalPatternEdgeRouter()
Creates a new instance of OrthogonalPatternEdgeRouter with default settings.

Method Detail

getMonotonicPathRestriction

public byte getMonotonicPathRestriction()
Returns the monotonic path restriction that should be applied.

Returns:
one of the valid monotonic path restrictions
See Also:
setMonotonicPathRestriction(byte)

setMonotonicPathRestriction

public void setMonotonicPathRestriction(byte monotonicPathRestriction)
Specifies the monotonic path restriction that should be applied.

Default Value:
The default value is MONOTONIC_NONE
Parameters:
monotonicPathRestriction - one of the valid monotonic path restrictions
Throws:
java.lang.IllegalArgumentException - if the specified path restriction is unknown

canLayout

public boolean canLayout(LayoutGraph graph)
Accepts all graphs that can be handled by the core layout algorithm.

If there is no core layout algorithm, all graphs whose nodes have width and height greater than 0 are accepted.

Parameters:
graph - the input graph
Returns:
true if there is no core layout algorithm or the core layout algorithm accepts the graph, false otherwise
See Also:
Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)
Routes the edges of the given graph orthogonally.

Parameters:
graph - the input graph
See Also:
Layouter.canLayout(LayoutGraph)

checkNodeSize

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

This method is called before the invocation of the core layouter for each normal node of the input graph. It may be overridden in order to obtain a custom implementation of node-size check or to remove it entirely.

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

checkGroupNodeSize

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

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 group-node-size check or to remove it entirely.

Parameters:
layout - the GraphLayout instance
node - the 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)

calculateCost

protected double calculateCost(Edge edge,
                               YList path,
                               PortCandidate spc,
                               PortCandidate tpc)
Calculates the edge cost of a possible edge path, in order to determine which path is the best, i.e., the cheapest.

This method is called by doLayout(LayoutGraph) in order to decide which path is the best. The default implementation considers the edge length, the number of bends, edge crossings, PortCandidates and monotonic path restrictions. It may be overridden to apply a different set of costs or a different weighting.

Parameters:
edge - the edge whose costs to calculate
path - the edge's path
spc - the source PortCandidate for this edge
tpc - the target PortCandidate for this edge
Returns:
the sum of all costs for this edge's path

calculatePortCandidateCost

protected double calculatePortCandidateCost(Edge edge,
                                            YList path,
                                            PortCandidate spc,
                                            PortCandidate tpc)
Calculates the costs for the chosen PortCandidates.

This method is called by calculateCost(Edge, YList, PortCandidate, PortCandidate). The default implementation will return the candidates' costs. It may be overridden to change the calculation of these costs.

Parameters:
edge - the edge for which the costs are calculated
path - the path of the given edge
spc - the source PortCandidate for this edge
tpc - the target PortCandidate for this edge
Returns:
the costs for the PortCandidates

calculateBendCost

protected double calculateBendCost(Edge edge,
                                   YList path,
                                   PortCandidate spc,
                                   PortCandidate tpc)
Calculates the costs for all bends of the given path.

This method is called by calculateCost(Edge, YList, PortCandidate, PortCandidate). The default implementation multiplies the number of bends with the according costs. It may be overridden to change the calculation of these costs.

 
Only bends are taken into account. The source and target ports, that are also part of the given path, are excluded.
Parameters:
edge - the edge for which the costs are calculated
path - the path of the given edge
spc - the source PortCandidate for this edge
tpc - the target PortCandidate for this edge
Returns:
the costs for the bends of this path

calculateSelfLoopSelfSidePenaltyCost

protected double calculateSelfLoopSelfSidePenaltyCost(Edge edge,
                                                      YList path,
                                                      PortCandidate spc,
                                                      PortCandidate tpc)
Calculates the extra penalty that is added to the path's cost if the edge is a self-loop and source and target ports have the same direction.

This method is called by calculateCost(Edge, YList, PortCandidate, PortCandidate). The default implementation adds costs for another bend if source and target ports share the same node side. In this manner, paths with different source and target directions are cheaper and thus preferred. The method may be overridden to change the calculation of this penalty.

Parameters:
edge - the edge for which the costs are calculated
path - the path of the given edge
spc - the source PortCandidate for this edge
tpc - the target PortCandidate for this edge
Returns:
an extra penalty for specific self-loop paths

calculateEdgeLength

protected double calculateEdgeLength(Edge edge,
                                     YList path,
                                     PortCandidate spc,
                                     PortCandidate tpc)
Calculates the costs for the length of the given path.

This method is called by calculateCost(Edge, YList, PortCandidate, PortCandidate). The default implementation returns costs between 0 for short paths and 1 for long paths. Hence, it has relatively little impact on the overall costs. The method may be overridden to introduce a different weighting of the edge length.

Parameters:
edge - the edge for which the costs are calculated
path - the path of the given edge
spc - the source PortCandidate for this edge
tpc - the target PortCandidate for this edge
Returns:
the costs for the length of the given path

calculateCrossingCosts

protected double calculateCrossingCosts(Edge edge,
                                        YList path,
                                        PortCandidate spc,
                                        PortCandidate tpc)
Calculates the overall crossing costs of the given path, including edge crossings, edge overlaps and node crossings.

This method is called by calculateCost(Edge, YList, PortCandidate, PortCandidate). The default implementation will determine overlaps and crossings between edge segments and nodes and sum up the costs. It may be overridden to use a different combination of costs.

Parameters:
edge - the edge for which the costs are calculated
path - the path of the given edge
spc - the source PortCandidate for this edge
tpc - the target PortCandidate for this edge
Returns:
the overall crossing costs of the given path, including edge crossings, edge overlaps and node crossings

setAffectedEdgesDPKey

public void setAffectedEdgesDPKey(java.lang.Object key)
Specifies the key to register a DataProvider which determines the edges that shall be routed by this algorithm.

Default Value:
The default value is AFFECTED_EDGES
Parameters:
key - the key to register a DataProvider which determines the edges to be routed
Throws:
java.lang.IllegalArgumentException - if the specified DataProvider key is null

getAffectedEdgesDPKey

public java.lang.Object getAffectedEdgesDPKey()
Returns the key to register a DataProvider which determines the edges that shall be routed by this algorithm.

Returns:
the key to register a DataProvider which determines the edges to be routed
See Also:
setAffectedEdgesDPKey(Object)

setMinimumDistance

public void setMinimumDistance(double minDist)
Specifies the minimum distance that an edge will maintain from its source and target node.

The distance needs to be non-negative.

 
When setting the minimum distance to zero, edge segments may exactly overlap the borders of the source or target node. For example, a vertical segment can run on the left or right node border.
Default Value:
The default value is 10.0.
Parameters:
minDist - the minimum distance between the edge and its source and target node
Throws:
java.lang.IllegalArgumentException - if the specified distance is negative

getMinimumDistance

public double getMinimumDistance()
Returns the minimum distance that an edge will maintain from its source and target node.

The distance needs to be non-negative.

 
When setting the minimum distance to zero, edge segments may exactly overlap the borders of the source or target node. For example, a vertical segment can run on the left or right node border.
Returns:
the minimum distance between the edge and its source and target node
See Also:
setMinimumDistance(double)

setGridWidth

public void setGridWidth(double gridSpacing)
Specifies the spacing of the grid on which edges are routed.

The spacing between two grid lines must be at least 2.

 
The spacing will only be considered if grid routing is enabled.
Default Value:
The default value is 10.0.
Parameters:
gridSpacing - the spacing between two grid lines
Throws:
java.lang.IllegalArgumentException - if the specified grid spacing is less than 2
See Also:
setGridRoutingEnabled(boolean)

getGridWidth

public double getGridWidth()
Returns the spacing of the grid on which edges are routed.

The spacing between two grid lines must be at least 2.

 
The spacing will only be considered if grid routing is enabled.
Returns:
the spacing between two grid lines
See Also:
setGridWidth(double), setGridRoutingEnabled(boolean)

setGridOrigin

public void setGridOrigin(YPoint gridOrigin)
Specifies the origin of the grid.

 
Grid routing has lower priority than the minimum distance. Thus, it is possible that edges are not routed on the grid if there is not enough space between two borders.
 
The spacing will only be considered if grid routing is enabled.
Default Value:
The default value is YPoint.ORIGIN
Parameters:
gridOrigin - the origin of the grid
Throws:
java.lang.IllegalArgumentException - if the specified point is null
See Also:
setGridRoutingEnabled(boolean)

getGridOrigin

public YPoint getGridOrigin()
Returns the origin of the grid.

 
Grid routing has lower priority than the minimum distance. Thus, it is possible that edges are not routed on the grid if there is not enough space between two borders.
 
The spacing will only be considered if grid routing is enabled.
Returns:
the origin of the grid
See Also:
setGridOrigin(YPoint), setGridRoutingEnabled(boolean)

setGridRoutingEnabled

public void setGridRoutingEnabled(boolean gridRoutingEnabled)
Specifies whether or not to route the edges on a grid.

The grid can be defined using methods setGridOrigin(YPoint) and setGridWidth(double).

 
The edges' source and target ports are not reassigned if they have fixed coordinates. Therefore, the first and last segments of an edge might not be routed on the grid. Use weak PortConstraints or assign coordinates that already lie on the grid for these ports if grid routing is desired.
Default Value:
The default value is false. Edges are not routed on a grid.
Parameters:
gridRoutingEnabled - true if edges should be routed on grid, false otherwise

isGridRoutingEnabled

public boolean isGridRoutingEnabled()
Returns whether or not to route the edges on a grid.

The grid can be defined using methods setGridOrigin(YPoint) and setGridWidth(double).

 
The edges' source and target ports are not reassigned if they have fixed coordinates. Therefore, the first and last segments of an edge might not be routed on the grid. Use weak PortConstraints or assign coordinates that already lie on the grid for these ports if grid routing is desired.
Returns:
true if edges are routed on grid, false otherwise
See Also:
setGridRoutingEnabled(boolean), setGridOrigin(YPoint), setGridWidth(double)

setEdgeCrossingCost

public void setEdgeCrossingCost(double edgeCrossingCost)
Specifies the costs for a crossing between two edges.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

Default Value:
The default value is 5.
Parameters:
edgeCrossingCost - the costs for an edge crossing
Throws:
java.lang.IllegalArgumentException - if the specified costs are negative

getEdgeCrossingCost

public double getEdgeCrossingCost()
Returns the costs for a crossing between two edges.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

Returns:
the costs for an edge crossing
See Also:
setEdgeCrossingCost(double)

getNodeCrossingCost

public double getNodeCrossingCost()
Returns the costs for edges that cross nodes.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

Returns:
the costs for edges crossing nodes
See Also:
setNodeCrossingCost(double)

setNodeCrossingCost

public void setNodeCrossingCost(double nodeCrossingCost)
Specifies the costs for edges that cross nodes.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

Default Value:
The default value is 50.
Parameters:
nodeCrossingCost - the costs for edges crossing nodes
Throws:
java.lang.IllegalArgumentException - if the specified costs are negative

setBendCost

public void setBendCost(double bendCost)
Specifies the costs for creating a bend on the edge's path.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

Default Value:
The default value is 1.
Parameters:
bendCost - the costs for edges crossing nodes
Throws:
java.lang.IllegalArgumentException - if the specified costs are negative

getBendCost

public double getBendCost()
Returns the costs for creating a bend on the edge's path.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

Returns:
the costs for edges crossing nodes
See Also:
setBendCost(double)

getEdgeOverlapCost

public double getEdgeOverlapCost()
Returns the costs for overlapping edge paths.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

 
In case this OrthogonalPatternEdgeRouter is used stand-alone, one can determine a higher cost to prevent edge overlaps.
 
By default this OrthogonalPatternEdgeRouter is used in conjunction with a OrthogonalSegmentDistributionStage. Hence, edge overlaps are desired and thus should not cause any costs.
Returns:
the costs for overlapping edge segments
See Also:
setEdgeOverlapCost(double)

setEdgeOverlapCost

public void setEdgeOverlapCost(double edgeOverlapCost)
Specifies the costs for overlapping edge paths.

These costs are used for finding the best path out of the predefined paths from which the router can choose.

The costs need to be non-negative.

 
In case this OrthogonalPatternEdgeRouter is used stand-alone, one can determine a higher cost to prevent edge overlaps.
 
By default this OrthogonalPatternEdgeRouter is used in conjunction with a OrthogonalSegmentDistributionStage. Hence, edge overlaps are desired and thus should not cause any costs.
Default Value:
The default value is 0.
Parameters:
edgeOverlapCost - the costs for overlapping edge segments
Throws:
java.lang.IllegalArgumentException - if the specified costs are negative

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