y.layout.router
Class OrthogonalPatternEdgeRouter

java.lang.Object
  y.layout.AbstractLayoutStage
      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, NODE_TYPE_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