Search this API

y.layout.organic
Class ShuffleLayouter

java.lang.Object
  extended by y.layout.organic.ShuffleLayouter
All Implemented Interfaces:
Layouter, LayoutStage

public class ShuffleLayouter
extends java.lang.Object
implements LayoutStage

This layout algorithm removes overlaps between nodes in a graph.

Note: The usage of RemoveOverlapsLayoutStage instead of this class is recommended for most use cases involving the mere removal of overlaps. That stage offers a more powerful strategy to do the task.

Layout Style

The style of results often resembles the look of tiles which have been dropped onto each other, where tiles correspond to nodes of the graph. The reason is that overlapping nodes are moved in order to resolve the overlap. During this process, several nodes moving in the same direction may be stacked next to or above each other.

This algorithm does not route the edges of the input graph - edges might although be stretched due to the node movement.


Example with overlaps (left) and after executing the shuffle layout (right)

Example with overlaps (left) and after executing the shuffle layout (right)

Concept

Nodes overlapping with other nodes will be moved in horizontal or vertical direction in order to remove overlaps. The concept behind this removal step is based on a famous Russian arcade game.

Features

This layout stage can also be executed on its own, without specifying a core layout algorithm.

A minimum distance between nodes can be specified such that not only overlaps will be removed but nodes will keep this specified distance to other nodes. This distance can be defined separately for each node using a DataProvider registered with key MINIMAL_DISTANCE_DPKEY. The minimum distance can also be specified globally via setMinimalNodeDistance(double).

To specify that specific nodes should not be moved, they can be marked as fixed using a DataProvider registered with key FIXED_NODE_DPKEY.

 

Field Summary
static java.lang.Object FIXED_NODE_DPKEY
          A DataProvider key for marking nodes as fixed A node marked as fixed will not be moved by this algorithm but stay at its current position.
static byte HOC_INTERSECTION_BOX
          Horizontal overlap criterion defining an overlap as horizontal if the overlapping area is greater in height than in width.
static byte HOC_LESS_MOVEMENT
          Horizontal overlap criterion categorizing an overlap as horizontal if the required movement for solving the overlap is shorter in horizontal direction than in vertical direction.
static byte HOC_NODE_CENTER
          Horizontal overlap criterion categorizing an overlap as horizontal if the center-to-center difference between the overlapping nodes is greater in horizontal direction (x-coordinates) than in vertical direction (y-coordinates).
static java.lang.Object MINIMAL_DISTANCE_DPKEY
          A DataProvider key for specifying a minimum distance for each node The default minimum distance specified by setMinimalNodeDistance(double) will be ignored for a node if the DataProvider registered with this key contains a valid minimum distance for that node.
 
Fields inherited from interface y.layout.Layouter
EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES
 
Constructor Summary
ShuffleLayouter()
          Creates a new instance of ShuffleLayouter with default settings.
 
Method Summary
 boolean canLayout(LayoutGraph graph)
          Accepts all graphs that the specified core layout algorithm accepts.
 void doLayout(LayoutGraph graph)
          Performs the overlap removal (shuffle) algorithm on the given graph, after the core layout algorithm was applied to it.
 Layouter getCoreLayouter()
          Returns the core layout algorithm.
 byte getHorizontalOverlapCriterium()
          Returns the criterion for marking an overlap as horizontal.
 double getMinimalNodeDistance()
          Returns the default minimum distance that has to be obeyed between any two nodes.
 boolean isBarycenterModeActive()
          Returns whether or not the barycenter mode is used for node shuffling when removing overlaps.
 boolean isSimpleModeActive()
          Returns whether or not the simple, fast layout mode of this algorithm is active.
 void setBarycenterModeActive(boolean barycenterModeActive)
          Specifies whether or not the barycenter mode is used for node shuffling when removing overlaps.
 void setCoreLayouter(Layouter layouter)
          Specifies the core layout algorithm.
 void setHorizontalOverlapCriterium(byte hoc)
          Specifies the criterion for marking an overlap as horizontal.
 void setMinimalNodeDistance(double distance)
          Specifies the default minimum distance that has to be obeyed between any two nodes.
 void setSimpleModeActive(boolean s)
          Specifies whether or not the simple, fast layout mode of this algorithm is active.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

MINIMAL_DISTANCE_DPKEY

public static final java.lang.Object MINIMAL_DISTANCE_DPKEY
A DataProvider key for specifying a minimum distance for each node

The default minimum distance specified by setMinimalNodeDistance(double) will be ignored for a node if the DataProvider registered with this key contains a valid minimum distance for that node.

Minimum distance values need to be greater than 0.

 
If no DataProvider with this key is registered, the minimum distance for all nodes is specified by setMinimalNodeDistance(double).

FIXED_NODE_DPKEY

public static final java.lang.Object FIXED_NODE_DPKEY
A DataProvider key for marking nodes as fixed

A node marked as fixed will not be moved by this algorithm but stay at its current position.

 
If two nodes overlap and both nodes are fixed, then this algorithm will not remove the corresponding overlap.

HOC_INTERSECTION_BOX

public static final byte HOC_INTERSECTION_BOX
Horizontal overlap criterion defining an overlap as horizontal if the overlapping area is greater in height than in width.

Otherwise, if the overlap area's width is greater than or equal to its height, an overlap will be categorized as vertical.

The area of an overlap is defined as the rectangle where two nodes intersect with each other.

 
If there are no overlaps where a node contains a whole other node then this criterion is equal to HOC_LESS_MOVEMENT.
See Also:
setHorizontalOverlapCriterium(byte), Constant Field Values
Sample Graph:

The two highlighted overlaps are detected as being horizontal, the others are vertical

HOC_NODE_CENTER

public static final byte HOC_NODE_CENTER
Horizontal overlap criterion categorizing an overlap as horizontal if the center-to-center difference between the overlapping nodes is greater in horizontal direction (x-coordinates) than in vertical direction (y-coordinates).

Otherwise, if the center-to-center difference between two overlapping nodes is greater in vertical direction (y-coordinates), the corresponding overlap is categorized as vertical. The same applies if the differences in vertical and horizontal direction are equal.

See Also:
setHorizontalOverlapCriterium(byte), Constant Field Values
Sample Graph:

The three highlighted overlaps are detected as being horizontal, the other one is vertical

HOC_LESS_MOVEMENT

public static final byte HOC_LESS_MOVEMENT
Horizontal overlap criterion categorizing an overlap as horizontal if the required movement for solving the overlap is shorter in horizontal direction than in vertical direction.

Otherwise, an overlap will be categorized as vertical.

This criterion tries to avoid moving nodes too much because the direction for resolving overlaps will be chosen such that the shorter movement is preferred.

 
If there are no overlaps where a node contains a whole other node then this criterion is equal to HOC_INTERSECTION_BOX.
See Also:
setHorizontalOverlapCriterium(byte), Constant Field Values
Sample Graph:

The highlighted overlaps are detected as being horizontal, the others are vertical
Constructor Detail

ShuffleLayouter

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

Method Detail

doLayout

public void doLayout(LayoutGraph graph)
Performs the overlap removal (shuffle) algorithm on the given graph, after the core layout algorithm was applied to it.

Specified by:
doLayout in interface Layouter
Parameters:
graph - the input graph
See Also:
Layouter.canLayout(LayoutGraph)

canLayout

public boolean canLayout(LayoutGraph graph)
Accepts all graphs that the specified core layout algorithm accepts. If there is no core layout algorithm specified, all types of graphs 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 or the graph is not null in case that no core layout algorithm is specified, false otherwise
See Also:
Layouter.doLayout(LayoutGraph)

setCoreLayouter

public void setCoreLayouter(Layouter layouter)
Description copied from interface: LayoutStage
Specifies the core layout algorithm. This algorithm is wrapped by this stage. It is invoked in Layouter.doLayout(LayoutGraph). The LayoutStage may add pre- and post-processing steps before and after calling the core layout algorithm.

Specified by:
setCoreLayouter in interface LayoutStage
Parameters:
layouter - the core layout algorithm

getCoreLayouter

public Layouter getCoreLayouter()
Description copied from interface: LayoutStage
Returns the core layout algorithm. This algorithm is wrapped by this stage. It is invoked in Layouter.doLayout(LayoutGraph). The LayoutStage may add pre- and post-processing steps before and after calling the core layout algorithm.

Specified by:
getCoreLayouter in interface LayoutStage
Returns:
the core layout algorithm

setHorizontalOverlapCriterium

public void setHorizontalOverlapCriterium(byte hoc)
Specifies the criterion for marking an overlap as horizontal.

This criterion influences how overlaps will be resolved. If an overlap is considered horizontal, it will preferably be solved by moving nodes horizontally, else vertically.

 
This criterion will only have an effect if the simple mode is disabled.
Default Value:
The default value is HOC_LESS_MOVEMENT
Parameters:
hoc - one of the predefined overlap criteria
Throws:
java.lang.IllegalArgumentException - if the given criterion is unknown

getHorizontalOverlapCriterium

public byte getHorizontalOverlapCriterium()
Returns the criterion for marking an overlap as horizontal.

This criterion influences how overlaps will be resolved. If an overlap is considered horizontal, it will preferably be solved by moving nodes horizontally, else vertically.

 
This criterion will only have an effect if the simple mode is disabled.
Returns:
one of the predefined overlap criteria

setMinimalNodeDistance

public void setMinimalNodeDistance(double distance)
Specifies the default minimum distance that has to be obeyed between any two nodes.

This default distance will be considered for a node if the DataProvider registered with the graph with key MINIMAL_DISTANCE_DPKEY does not contain a valid, positive distance for that node. If there is no DataProvider registered with the mentioned key, then this default distance will be applied to all nodes.

The minimum distance needs to be a non-negative value.

Default Value:
The default value is 5.
Parameters:
distance - the non-negative minimum node distance
Throws:
java.lang.IllegalArgumentException - if the given distance is negative
See Also:
MINIMAL_DISTANCE_DPKEY
Sample Graphs:

Minimum node distance set to 0

Minimum node distance set to 20

getMinimalNodeDistance

public double getMinimalNodeDistance()
Returns the default minimum distance that has to be obeyed between any two nodes.

This default distance will be considered for a node if the DataProvider registered with the graph with key MINIMAL_DISTANCE_DPKEY does not contain a valid, positive distance for that node. If there is no DataProvider registered with the mentioned key, then this default distance will be applied to all nodes.

The minimum distance needs to be a non-negative value.

Returns:
the non-negative minimum node distance
See Also:
setMinimalNodeDistance(double), MINIMAL_DISTANCE_DPKEY

setSimpleModeActive

public void setSimpleModeActive(boolean s)
Specifies whether or not the simple, fast layout mode of this algorithm is active.

Enabling this mode, the overlap removal step will be executed using a simpler and less sophisticated approach. All overlaps will only be solved by moving nodes vertically. The algorithm will not try to figure out which direction might be better for overlap removal.

The runtime will improve, but results may be of lower quality when using this mode.

 
When enabling this mode, the specified horizontal overlap criterion will not have any effect.
Default Value:
The default value is false.
Parameters:
s - true if the simple and fast layout mode should be enabled, false otherwise.
Sample Graphs:

false - input on left hand side, result on right hand side

true - input on left hand side, result on right hand side

isSimpleModeActive

public boolean isSimpleModeActive()
Returns whether or not the simple, fast layout mode of this algorithm is active.

Enabling this mode, the overlap removal step will be executed using a simpler and less sophisticated approach. All overlaps will only be solved by moving nodes vertically. The algorithm will not try to figure out which direction might be better for overlap removal.

The runtime will improve, but results may be of lower quality when using this mode.

 
When enabling this mode, the specified horizontal overlap criterion will not have any effect.
Returns:
true if the simple and fast layout mode is enabled, false otherwise.
See Also:
setSimpleModeActive(boolean)

isBarycenterModeActive

public boolean isBarycenterModeActive()
Returns whether or not the barycenter mode is used for node shuffling when removing overlaps.

If this mode is active, the overlap removal step will be executed two times for each direction, once with the normal node ordering and once with the reversed ordering. Finally, the barycenter between both results will be used for assigning the node coordinates.

Activating the barycenter mode allows more symmetric results for some graphs. However, the runtime might increase.

Returns:
true if the barycenter placement mode is active false otherwise
See Also:
setBarycenterModeActive(boolean)

setBarycenterModeActive

public void setBarycenterModeActive(boolean barycenterModeActive)
Specifies whether or not the barycenter mode is used for node shuffling when removing overlaps.

If this mode is active, the overlap removal step will be executed two times for each direction, once with the normal node ordering and once with the reversed ordering. Finally, the barycenter between both results will be used for assigning the node coordinates.

Activating the barycenter mode allows more symmetric results for some graphs. However, the runtime might increase.

Default Value:
The default value is false. The barycenter mode is disabled.
Parameters:
barycenterModeActive - true if the barycenter placement mode should be active false otherwise
Sample Graphs:

false - Note the two highlighted small nodes aligned with the large neighbor node.

true - Note the two highlighted small nodes placed in the barycenter between their possible upper and lower alignment positions

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