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

This class represents an orthogonal edge router. An orthogonal edge router is a layout algorithm that changes the coordinates of the edge paths in a way that the resulting layout of the edges is made up of vertical and horizontal segments only. The router does not change the location or the size of the nodes in a diagram in any way.

The edge router will not try to find a perfect route from source to edge like OrthogonalEdgeRouter does, but chooses the best path out of several fixed paths it can choose from. The best path out of these possible paths is determined by its cost. One can take influence on the costs by setting several cost factors. The distance, an edge will have from its source and target node is determined by setMinimumDistance(double).

The edges whose paths are to be routed can be defined using method setSphereOfAction(byte) or binding a data provider to the input graph with key ChannelEdgeRouter.AFFECTED_EDGES. Note: If the DataProvider is registered on the graph, it will determine all affected edges, regardless of the set sphere of action. So setting a sphere of action has lower priority than adding the specific DataProvider directly.

By default all edges are routed according to their best paths and afterwards overlapping edges will be redistributed. This can be prevented by calling method setDistributeEdgesEnabled(boolean).

ChannelEdgeRouter does also support grid routing setGridRoutingEnabled(boolean).Therefore the user can define the grid origin setGridOrigin(y.geom.YPoint) and the grid width setGridWidth(double).

This edge router will obey strong and weak port constraints. It expects the port constraints to be bound to the input graph by the data provider keys PortConstraintKeys.SOURCE_PORT_CONSTRAINT_KEY and PortConstraintKeys.TARGET_PORT_CONSTRAINT_KEY. Furthermore, this class supports the more advanced port constraint concept of PortCandidates. It expects collections of port candidates to be bound to the input graph by the data provider keys PortCandidate.SOURCE_PCLIST_DPKEY and PortCandidate.TARGET_PCLIST_DPKEY.

Field Summary

static Object	AFFECTED_EDGES DataProvider key that can be used to determine which edges the edge router will route.
static byte	MONOTONIC_BOTH Constant that specifies monotonic path restrictions for edges.
static byte	MONOTONIC_HORIZONTAL Constant that specifies monotonic path restrictions for edges.
static byte	MONOTONIC_NONE Constant that specifies monotonic path restrictions for edges.
static byte	MONOTONIC_VERTICAL Constant that specifies monotonic path restrictions for edges.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

OrthogonalPatternEdgeRouter()

Method Summary

protected double	calculateBendCost(Edge edge, YList path, PortCandidate spc, PortCandidate tpc) Calculates the costs for all bends of the given path by simple multiplying all bends with the bend costs.
protected double	calculateCost(Edge edge, YList path, PortCandidate spc, PortCandidate tpc) Calculates the edge cost of a possible edge path, to determine which path is the best (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 ports.
protected double	calculateSelfLoopSelfSidePenaltyCost(Edge edge, YList path, PortCandidate spc, PortCandidate tpc) Calculates the extra penalty that is added to the paths cost if the edge is a selfloop and source and target ports have the same direction.
boolean	canLayout(LayoutGraph graph) Returns true iff the given graph can be laid out by this algorithm.
protected void	checkGroupNodeSize(GraphLayout layout, Object node) This method throws an IllegalArgumentException if the width/height of the given group node object is zero.
protected void	checkNodeSize(GraphLayout layout, Object node) This method throws an IllegalArgumentException if the width/height of the given node object is zero.
void	doLayout(LayoutGraph graph) Main layout routine that assigns new layout information to the given graph.
Object	getAffectedEdgesDPKey() Returns the DataProvider key, which determines the edges, that shall be routed by the algorithm.
double	getBendCost() Returns the edge cost a bend inside an edge's path will cause.
double	getEdgeCrossingCost() Returns the edge cost an edge crossing will cause.
double	getEdgeOverlapCost() Returns the cost an edge overlap will cause.
YPoint	getGridOrigin() Returns the origin of the grid, which is used for grid routing if enabled.
double	getGridWidth() Returns the grid width, that defines the space between two grid lines.
double	getMinimumDistance() Returns the minimum distance an edge will have to its source and target node.
byte	getMonotonicPathRestriction() Returns the specified kind of monotonic path restrictions.
double	getNodeCrossingCost() Returns the node cost an edge node overlap will cause.
boolean	isGridRoutingEnabled() Returns whether or not grid routing is enabled.
void	setAffectedEdgesDPKey(Object key) Sets the DataProvider key, which determines the edges, that shall be routed by the algorithm.
void	setBendCost(double bendCost) Sets the edge cost a bend inside an edge's path will cause.
void	setEdgeCrossingCost(double edgeCrossingCost) Sets the edge cost an edge crossing will cause.
void	setEdgeOverlapCost(double edgeOverlapCost) Sets the cost an edge overlap will cause.
void	setGridOrigin(YPoint gridOrigin) Sets the origin of the grid.
void	setGridRoutingEnabled(boolean gridRoutingEnabled) Specifies whether or not to use grid routing.
void	setGridWidth(double gridWidth) Sets the grid width of the grid on which edges shall be routed.
void	setMinimumDistance(double minDist) Sets the minimum distance an edge will have to its source and target node.
void	setMonotonicPathRestriction(byte monotonicPathRestriction) Specifies which kind of monotonic path restrictions should be applied.
void	setNodeCrossingCost(double nodeCrossingCost) Sets the node cost an edge node overlap will cause.

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 Object AFFECTED_EDGES

DataProvider key that can be used to determine which edges the edge router will route.

MONOTONIC_NONE

public static final byte MONOTONIC_NONE

Constant that specifies monotonic path restrictions for edges. This constant specifies that there are no restrictions.

See Also:

setMonotonicPathRestriction(byte), Constant Field Values

MONOTONIC_VERTICAL

public static final byte MONOTONIC_VERTICAL

Constant that specifies monotonic path restrictions for edges. This constant specifies restrictions for the vertical direction, i.e., each vertical edge segment is 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

Constant that specifies monotonic path restrictions for edges. This constant specifies restrictions for the horizontal direction, i.e., each horizontal edge segment is 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

Constant that specifies monotonic path restrictions for edges. This constant specifies restrictions for the horizontal and vertical direction, i.e., 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()

Method Detail

getMonotonicPathRestriction

public byte getMonotonicPathRestriction()

Returns the specified kind of monotonic path restrictions.

See Also:

setMonotonicPathRestriction(byte)

setMonotonicPathRestriction

public void setMonotonicPathRestriction(byte monotonicPathRestriction)

Specifies which kind of monotonic path restrictions should be applied. Possible values are MONOTONIC_NONE, MONOTONIC_VERTICAL, MONOTONIC_HORIZONTAL and MONOTONIC_BOTH.

Parameters:

monotonicPathRestriction - the monotonic path restriction.

canLayout

public boolean canLayout(LayoutGraph graph)

Description copied from interface: Layouter

Returns true iff the given graph can be laid out by this algorithm. Calling doLayout with the given graph as its argument will only success if this method returns true.

doLayout

public void doLayout(LayoutGraph graph)

Description copied from interface: Layouter

Main layout routine that assigns new layout information to the given graph.

checkNodeSize

protected void checkNodeSize(GraphLayout layout,
                             Object node)
                      throws IllegalArgumentException

This method throws an IllegalArgumentException if the width/height of the given node object is zero. It is called by the doLayout(LayoutGraph) method for each node object in the input graph.

Throws:

IllegalArgumentException - thrown if the width/height of the node object is zero.

Parameters:

layout - a graph layout object.

node - the node object to test.

See Also:

checkGroupNodeSize(GraphLayout,Object)

checkGroupNodeSize

protected void checkGroupNodeSize(GraphLayout layout,
                                  Object node)
                           throws IllegalArgumentException

This method throws an IllegalArgumentException if the width/height of the given group node object is zero. It is called by the doLayout(LayoutGraph) method for each group node object in the input graph.

Throws:

IllegalArgumentException - thrown if the width/height of the group node object is zero.

Parameters:

layout - a graph layout object.

node - the group node object to test.

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, to determine which path is the best (cheapest).

Parameters:

edge - the edge whose cost to calculate.

path - the edge's path.

spc - the source port candidate chosen for this path.

tpc - the target port candidate chosen for this path.

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 ports. By default these costs are determined from set port candidates. If no PortCandidates have been set on the given edge, the cost is 0. If PortConstraints have been set for this edge, the cost is also 0.

Parameters:

edge - the edge the penalty is calculated for.

path - the path this penalty is calculated for.

spc - the used source PortCandidate for this path.

tpc - the used target PortCandidate for this path.

Returns:

the costs for all bends of this path

calculateBendCost

protected double calculateBendCost(Edge edge,
                                   YList path,
                                   PortCandidate spc,
                                   PortCandidate tpc)

Calculates the costs for all bends of the given path by simple multiplying all bends with the bend costs.

Note: Only bends are taken into account, not the source and target ports, that are also part of the given path.

Parameters:

edge - the edge the penalty is calculated for.

path - the path this penalty is calculated for.

spc - the used source PortCandidate for this path.

tpc - the used target PortCandidate for this path.

Returns:

the costs for all 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 paths cost if the edge is a selfloop and source and target ports have the same direction. By default this penalty is a bit more than adding another bend to the path so that patterns with different source and target directions are cheaper and thus preferred.

Parameters:

edge - the edge the penalty is calculated for.

path - the path this penalty is calculated for.

spc - the used source PortCandidate for this path.

tpc - the used target PortCandidate for this path.

Returns:

an extra penalty for paths

calculateEdgeLength

protected double calculateEdgeLength(Edge edge,
                                     YList path,
                                     PortCandidate spc,
                                     PortCandidate tpc)

Calculates the costs for the length of the given path. By default this cost is between 0 (short path) and 1 (long path) so this has very little impact on the overall costs.

Parameters:

edge - the edge the penalty is calculated for.

path - the path this penalty is calculated for.

spc - the used source PortCandidate for this path.

tpc - the used target PortCandidate for this path.

Returns:

the length costs of the given path between 0 and 1

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.

Parameters:

edge - the edge the penalty is calculated for.

path - the path this penalty is calculated for.

spc - the used source PortCandidate for this path.

tpc - the used target PortCandidate for this path.

Returns:

the overall crossing costs of the given path including edge crossings, edge overlaps and node crossings.

setAffectedEdgesDPKey

public void setAffectedEdgesDPKey(Object key)

Sets the DataProvider key, which determines the edges, that shall be routed by the algorithm.

By default, AFFECTED_EDGES is used.

Parameters:

key - the key, which determines the edges, that shall be routed by the algorithm.

getAffectedEdgesDPKey

public Object getAffectedEdgesDPKey()

Returns the DataProvider key, which determines the edges, that shall be routed by the algorithm.

By default, AFFECTED_EDGES is used.

Returns:

the DataProvider key which determines the edges, that shall be routed by the algorithm.

setMinimumDistance

public void setMinimumDistance(double minDist)

Sets the minimum distance an edge will have to its source and target node. Default value is 10.0.

Parameters:

minDist - the minimum distance an edge will have to its source and target node.

getMinimumDistance

public double getMinimumDistance()

Returns the minimum distance an edge will have to its source and target node. Default value is 10.0.

Returns:

the minimum distance an edge will have to its source and target node.

setGridWidth

public void setGridWidth(double gridWidth)

Sets the grid width of the grid on which edges shall be routed. Only takes effect if grid routing is enabled.

Default value is 10.0.

Throws:

IllegalArgumentException - if the specified grid width is less than 2.

Parameters:

gridWidth - the width between two grid lines.

See Also:

getGridWidth()

getGridWidth

public double getGridWidth()

Returns the grid width, that defines the space between two grid lines.

Default value is 10.0

.

Returns:

the grid width, that defines the space between two grid lines.

See Also:

setGridWidth(double)

setGridOrigin

public void setGridOrigin(YPoint gridOrigin)

Sets the origin of the grid. Takes effect if grid routing is enabled isGridRoutingEnabled(). Note that grid routing has lower priority than the minimum Distance setting setMinimumDistance(double). Thus it is possible that edges are not routed on the grid if there is not enough space between two borders. Default origin is at x = 0, y = 0

Parameters:

gridOrigin - the origin, which shall be set for the grid.

getGridOrigin

public YPoint getGridOrigin()

Returns the origin of the grid, which is used for grid routing if enabled. isGridRoutingEnabled(). Default origin is at x = 0, y = 0

Returns:

the origin of the grid, which is used for grid routing if enabled.

setGridRoutingEnabled

public void setGridRoutingEnabled(boolean gridRoutingEnabled)

Specifies whether or not to use grid routing. Grid routing means edges are routed on a grid's lines only. The grid can be defined using method setGridOrigin(y.geom.YPoint) and setGridWidth(double). Note that grid routing has lower priority than the minimum Distance setting setMinimumDistance(double). Thus it is possible that edges are not routed on the grid if there is not enough space between two borders.

Also, 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 ports or assign coordinates that already lie on the grid for these ports, if grid routing is wanted.

By default grid routing is not enabled.

Parameters:

gridRoutingEnabled - whether or not to enable grid routing

isGridRoutingEnabled

public boolean isGridRoutingEnabled()

Returns whether or not grid routing is enabled. By default grid routing is not enabled.

Returns:

true, if grid routing is enabled false, otherwise

setEdgeCrossingCost

public void setEdgeCrossingCost(double edgeCrossingCost)

Sets the edge cost an edge crossing will cause. Used to find the best path out of the predefined paths the router can choose from. Default value is 5.

Parameters:

edgeCrossingCost - the edge cost an edge crossing will cause.

getEdgeCrossingCost

public double getEdgeCrossingCost()

Returns the edge cost an edge crossing will cause. Used to find the best path out of the predefined paths the router can choose from. Default value is 5.

Returns:

edgeNodeOverlapCost the edge cost an edge crossing will cause.

getNodeCrossingCost

public double getNodeCrossingCost()

Returns the node cost an edge node overlap will cause. Used to find the best path out of the predefined paths the router can choose from. Default value is 50.

Returns:

the cost an edge node overlap will cause.

setNodeCrossingCost

public void setNodeCrossingCost(double nodeCrossingCost)

Sets the node cost an edge node overlap will cause. Used to find the best path out of the predefined paths the router can choose from. Default value is 50.

Parameters:

nodeCrossingCost - the edge cost an edge node overlap will cause.

setBendCost

public void setBendCost(double bendCost)

Sets the edge cost a bend inside an edge's path will cause. Used to find the best path out of the predefined paths the router can choose from. Default value is 1.

Parameters:

bendCost - the edge cost a bend inside an edge's path will cause.

getBendCost

public double getBendCost()

Returns the edge cost a bend inside an edge's path will cause. Used to find the best path out of the predefined paths the router can choose from. Default value is 1.

Returns:

the edge cost a bend inside an edge's path will cause.

getEdgeOverlapCost

public double getEdgeOverlapCost()

Returns the cost an edge overlap will cause. By default this edge router is used in conjunction with a segment distribution stage like OrthogonalSegmentDistributionStage, so edge overlaps are wanted and thus should not cause any costs. Default value is therefore 0. If this edge router is used stand-alone, one can determine a higher cost to prevent edge overlaps.

Returns:

the cost an edge overlap will cause.

setEdgeOverlapCost

public void setEdgeOverlapCost(double edgeOverlapCost)

Sets the cost an edge overlap will cause. By default this edge router is used in conjunction with a segment distribution stage like OrthogonalSegmentDistributionStage, so edge overlaps are wanted and thus should not cause any costs. Default value is therefore 0. If this edge router is used stand-alone, one can determine a higher cost to prevent edge overlaps.

Parameters:

edgeOverlapCost - the cost an edge overlap shall cause.