y.layout.router
Class OrganicEdgeRouter

java.lang.Object
  y.layout.router.OrganicEdgeRouter

All Implemented Interfaces:

Layouter, LayoutStage

public class OrganicEdgeRouter
extends java.lang.Object
implements LayoutStage

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

Layout Style

Edges are routed organically, i.e. in smooth curves around the nodes observing a minimum distance to the nodes.

During the routing process, the positions of the nodes are considered to be fixed and the router will not modify their locations or their sizes in any way.

The edge routing algorithm can be applied whenever edge paths should avoid crossing any nodes in organic or cyclic layout styles.

Concept

The edge routing algorithm uses a force-directed approach to calculate the edge paths. Nodes are considered to be repulsive forces while edges will try to become as short as possible.

Each edge is routed separately and is influenced by the nodes in a certain area around it. The algorithm will add bends to the edge path that are placed by balancing the forces.

The quality of the result highly depends on how much space there is between the nodes. More precisely, the distance between each pair of nodes should be at least twice the specified minimum distance. If it is not necessary that the nodes keep their locations, this can be ensured using a combination of RemoveOverlapsLayoutStage and node enlargement stage.

Features

setMinimalDistance(double) will make edges keep a custom distance to the nodes. However, if there is not enough space between the nodes, this distance may be undershot (i.e. edges will be closer to nodes).

OrganicEdgeRouter is able to reuse existing bends. Edges will contain those bends along with other bends added by the layout algorithm. Another feature allows to consider bends such that they influence the route finding, however, their absolute location is not kept (see setExistingBendsConsiderationEnabled(boolean)).

This edge routing algorithm is realized as a LayoutStage which can be applied to a graph directly or using a core layout algorithm.

Field Summary

static java.lang.Object

ROUTE_EDGE_DPKEY A DataProvider key for selecting edges that should be routed

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

OrganicEdgeRouter()
Creates a new OrganicEdgeRouter instance with the default settings.

OrganicEdgeRouter(double minNodeDistance)
Creates a new OrganicEdgeRouter instance with a custom minimum distance between edges and nodes.

OrganicEdgeRouter(Layouter core)
Creates a new OrganicEdgeRouter with the given core layout algorithm.

Method Summary

boolean	canLayout(LayoutGraph graph) Accepts all graphs whose nodes have sizes greater than 0 and that the specified core layout algorithm can handle.
protected void	checkGroupNodeSize(GraphLayout layout, java.lang.Object node) Checks whether or not the given group node's width or height is 0.
protected void	checkNodeSize(GraphLayout layout, java.lang.Object node) Checks whether or not the given node's width or height is 0.
LayoutStage	createNodeEnlargementStage() Returns a LayoutStage which temporarily increases the sizes of the nodes to avoid overlaps.
void	doLayout(LayoutGraph graph) Performs the organic routing of the edges of the input graph.
Layouter	getCoreLayouter() Returns the core layout algorithm which arranges the graph before edge routing.
double	getMinimalDistance() Returns the minimum distance the algorithm should guarantee between nodes and non-incident edges.
boolean	isEdgeNodeOverlapAllowed() Returns whether or not edges are allowed to cross nodes.
boolean	isExistingBendsConsiderationEnabled() Returns whether or not the initial bend coordinates influence the path routing such that the calculated routes tend to have a similar overall shape.
boolean	isRoutingAll() Returns whether a rerouting step is performed on all edges or just on a subset where distances are violated.
boolean	isUsingBends() Returns whether or not the initial bend coordinates are kept when determining the edge path.
void	setCoreLayouter(Layouter coreLayouter) Specifies the core layout algorithm which arranges the graph before edge routing.
void	setEdgeNodeOverlapAllowed(boolean edgeNodeOverlapAllowed) Specifies whether or not edges are allowed to cross nodes.
void	setExistingBendsConsiderationEnabled(boolean considerExistingBends) Specifies whether or not the initial bend coordinates influence the path routing such that the calculated routes tend to have a similar overall shape.
void	setMinimalDistance(double minimumDistance) Specifies the minimum distance the algorithm should guarantee between nodes and non-incident edges.
void	setRoutingAll(boolean routingAll) Specifies whether a rerouting step is performed on all edges or just on a subset where distances are violated.
void	setUsingBends(boolean keepExistingBends) Specifies whether or not the initial bend coordinates are kept when determining the edge path.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

ROUTE_EDGE_DPKEY

public static final java.lang.Object ROUTE_EDGE_DPKEY

A DataProvider key for selecting edges that should be routed

Constructor Detail

OrganicEdgeRouter

public OrganicEdgeRouter()

Creates a new OrganicEdgeRouter instance with the default settings.

OrganicEdgeRouter

public OrganicEdgeRouter(double minNodeDistance)

Creates a new OrganicEdgeRouter instance with a custom minimum distance between edges and nodes.

Parameters:

minNodeDistance - the minimum distance between edges and nodes

Throws:

java.lang.IllegalArgumentException - if the given minimum distance is negative

OrganicEdgeRouter

public OrganicEdgeRouter(Layouter core)

Creates a new OrganicEdgeRouter with the given core layout algorithm.

Parameters:

core - the core layout algorithm

Method Detail

canLayout

public boolean canLayout(LayoutGraph graph)

Accepts all graphs whose nodes have sizes greater than 0 and that the specified core layout algorithm can handle. If there is no core layout algorithm specified, all general graphs without zero-sized nodes are accepted.

Specified by:

canLayout in interface Layouter

Parameters:

graph - the input graph

Returns:

true if the core layout algorithm can handle the given graph and this graph doesn't contain nodes with size 0, false otherwise

See Also:

Layouter.doLayout(LayoutGraph)

isEdgeNodeOverlapAllowed

public boolean isEdgeNodeOverlapAllowed()

Returns whether or not edges are allowed to cross nodes. Allowing edges to overlap with nodes will produce smoother edges, because the edge paths can be closer to the nodes.

If nodes cannot be enlarged, e.g., because the nodes should not move, allowing overlaps between nodes and edges may lead to better results in case the distances between nodes are small. The minimum distance cannot always be maintained.

Returns:

true if edge-node overlaps are allowed, false otherwise

See Also:

setEdgeNodeOverlapAllowed(boolean), createNodeEnlargementStage(), setMinimalDistance(double)

setEdgeNodeOverlapAllowed

public void setEdgeNodeOverlapAllowed(boolean edgeNodeOverlapAllowed)

Specifies whether or not edges are allowed to cross nodes. Allowing edges to overlap with nodes will produce smoother edges, because the edge paths can be closer to the nodes.

If nodes cannot be enlarged, e.g., because the nodes should not move, allowing overlaps between nodes and edges may lead to better results in case the distances between nodes are small. The minimum distance cannot always be maintained.

Default Value:

The default value is true. Edges are allowed to cross nodes.

Parameters:

edgeNodeOverlapAllowed - true if edge-node overlaps should be allowed, false otherwise

See Also:

createNodeEnlargementStage(), setMinimalDistance(double)

Sample Graphs:

false

true

doLayout

public void doLayout(LayoutGraph graph)

Performs the organic routing of the edges of the input graph.

Specified by:

doLayout in interface Layouter

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)

checkNodeSize

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

Checks whether or not the given node's width or height is 0. This method is called in doLayout(LayoutGraph) before the core layout algorithm is invoked. It can be overridden to remove/change this check.

Parameters:

layout - a graph layout object

node - the node

Throws:

java.lang.IllegalArgumentException - if width or height of the node object is zero

See Also:

checkGroupNodeSize(GraphLayout, Object)

checkGroupNodeSize

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

Checks whether or not the given group node's width or height is 0. This method is called in doLayout(LayoutGraph) before the core layout algorithm is invoked. It can be overridden to remove/change this check.

Parameters:

layout - a graph layout object

node - the group node

Throws:

java.lang.IllegalArgumentException - if width or height of the group node object is zero

See Also:

checkNodeSize(GraphLayout, Object)

getCoreLayouter

public Layouter getCoreLayouter()

Returns the core layout algorithm which arranges the graph before edge routing.

Specified by:

getCoreLayouter in interface LayoutStage

Returns:

the layout algorithm that arranges the graph

See Also:

setCoreLayouter(Layouter)

setCoreLayouter

public void setCoreLayouter(Layouter coreLayouter)

Specifies the core layout algorithm which arranges the graph before edge routing.

Specified by:

setCoreLayouter in interface LayoutStage

Default Value:

The default value is null.

Parameters:

coreLayouter - the layout algorithm that arranges the graph

getMinimalDistance

public double getMinimalDistance()

Returns the minimum distance the algorithm should guarantee between nodes and non-incident edges.

The distance also influences how many bends are added to the path (a higher distance leads to less bends).

The minimum distance is defined to be a non-negative value.

For best results, the distance should be at least 10.

If there is not enough space, the minimum distance may not be respected.

Returns:

the non-negative minimum distance between edges and nodes

See Also:

setMinimalDistance(double)

setMinimalDistance

public void setMinimalDistance(double minimumDistance)

Specifies the minimum distance the algorithm should guarantee between nodes and non-incident edges.

The distance also influences how many bends are added to the path (a higher distance leads to less bends).

The minimum distance is defined to be a non-negative value.

For best results, the distance should be at least 10.

If there is not enough space, the minimum distance may not be respected.

Default Value:

The default value is 10.

Parameters:

minimumDistance - the non-negative minimum distance between edges and nodes

Throws:

java.lang.IllegalArgumentException - if the given minimum distance is negative

Sample Graphs:

10

50

isUsingBends

public boolean isUsingBends()

Returns whether or not the initial bend coordinates are kept when determining the edge path. The bends are considered as fixed nodes and stay part of the path.

If existing bends should not be absolutely fixed but just considered for the routing, use property setExistingBendsConsiderationEnabled(boolean) instead and disable this one.

Returns:

true if the initial bend coordinates are kept, false otherwise

See Also:

setUsingBends(boolean)

setUsingBends

public void setUsingBends(boolean keepExistingBends)

Specifies whether or not the initial bend coordinates are kept when determining the edge path. The bends are considered as fixed nodes and stay part of the path.

If existing bends should not be absolutely fixed but just considered for the routing, use property setExistingBendsConsiderationEnabled(boolean) instead and disable this one.

Default Value:

The default value is false. Bends coordinates in the input graph are not kept fix.

Parameters:

keepExistingBends - true if the initial bend coordinates should be kept, false otherwise

Sample Graphs:

Initial graph

false

true

isExistingBendsConsiderationEnabled

public boolean isExistingBendsConsiderationEnabled()

Returns whether or not the initial bend coordinates influence the path routing such that the calculated routes tend to have a similar overall shape.

The existing bend coordinates are considered but not kept. If they shall be kept, enable property setUsingBends(boolean).

This setting is ignored when setUsingBends(boolean) is enabled.

Returns:

ture if the existing bends are considered, false otherwise

See Also:

setExistingBendsConsiderationEnabled(boolean)

setExistingBendsConsiderationEnabled

public void setExistingBendsConsiderationEnabled(boolean considerExistingBends)

Specifies whether or not the initial bend coordinates influence the path routing such that the calculated routes tend to have a similar overall shape.

The existing bend coordinates are considered but not kept. If they shall be kept, enable property setUsingBends(boolean).

This setting is ignored when setUsingBends(boolean) is enabled.

Default Value:

The default value is false. Bends in the input graph are not considered for edge routing.

Parameters:

considerExistingBends - ture if the existing bends should be considered, false otherwise

isRoutingAll

public boolean isRoutingAll()

Returns whether a rerouting step is performed on all edges or just on a subset where distances are violated.

If only a subset of edges is rerouted, only those edges which cross nodes or come too close to a node are included. During rerouting, more bends are added to the edges that will be influenced by the repulsive forces.

Rerouting all edges will result in a more organic routing that considers the minimum distances more closely. Disabling this feature, i.e., keeping the first calculated path will take less runtime.

Returns:

true if all edges are rerouted, false if only a subset is rerouted

See Also:

setRoutingAll(boolean)

setRoutingAll

public void setRoutingAll(boolean routingAll)

Specifies whether a rerouting step is performed on all edges or just on a subset where distances are violated.

If only a subset of edges is rerouted, only those edges which cross nodes or come too close to a node are included. During rerouting, more bends are added to the edges that will be influenced by the repulsive forces.

Rerouting all edges will result in a more organic routing that considers the minimum distances more closely. Disabling this feature, i.e., keeping the first calculated path will take less runtime.

Default Value:

The default value is false. Only edges being too close to nodes are rerouted.

Parameters:

routingAll - true if all edges are rerouted, false if only a subset is rerouted

Sample Graphs:

false

true

createNodeEnlargementStage

public LayoutStage createNodeEnlargementStage()

Returns a LayoutStage which temporarily increases the sizes of the nodes to avoid overlaps.

The edges will keep a greater distance to the nodes. Therefore, they won't cross them.

The stage should be used in conjunction with RemoveOverlapsLayoutStage, see the provided example. The following example demonstrates how to use this stage:

 OrganicEdgeRouter router = new OrganicEdgeRouter();
 CompositeLayoutStage cls = new CompositeLayoutStage();
 cls.appendStage(router.createNodeEnlargementStage());
 cls.appendStage(new RemoveOverlapsLayoutStage(0));

 router.setCoreLayouter(cls);
 router.doLayout(graph);
 

Returns:

the LayoutStage that resizes the nodes