y.layout.organic
Class ShuffleLayouter

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