y.layout.organic
Class OrganicRemoveOverlapsStage

java.lang.Object
  y.layout.AbstractLayoutStage
      y.layout.organic.OrganicRemoveOverlapsStage

All Implemented Interfaces:

Layouter, LayoutStage

public class OrganicRemoveOverlapsStage
extends AbstractLayoutStage

This layout stage removes node overlaps while changes to the original layout structure are avoided and a specified minimum node distance is guaranteed.

Layout Style

Unlike the overlap removal approach implemented by RemoveOverlapsLayoutStage, this stage tries to keep the original layout structure, i.e., it tries to keep the geometric distances between the nodes.

The strategy for removing overlaps is similar to the layout strategy used by organic (force-directed) layout algorithms (e.g. SmartOrganicLayouter). Therefore, this stage is especially well suited to remove node overlaps in undirected graph drawings with straight-line edges, as produced by organic layout approaches.

A graph containing overlaps (left) and the result after applying this layout stage

Features

It is possible to define a minimum distance between nodes. This feature allows to not only remove overlaps but forces nodes to keep the specified distance to other nodes.

Nodes can be marked as fixed. Such nodes will not be moved during the overlap removal process. A DataProvider with key FIXED_NODE_DPKEY can be registered to mark the fixed nodes. Note that inputs with fixed nodes may significantly increase the overall runtime. Hence class ShuffleLayouter may be the better choice for such inputs.

Overlaps between nodes and edges are not removed by this stage.

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.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

OrganicRemoveOverlapsStage()
Creates a new instance of OrganicRemoveOverlapsStage with default settings.

OrganicRemoveOverlapsStage(Layouter core)
Creates a new instance of OrganicRemoveOverlapsStage with the given layout algorithm as core algorithm.

Method Summary

boolean	canLayout(LayoutGraph graph) Accepts general graphs without exception.
void	doLayout(LayoutGraph graph) Removes node overlaps and displaces nodes of the given graph such that they keep the specified minimum distance to each other.
long	getMaximumDuration() Returns the maximum duration in milliseconds that this layout stage is allowed to run.
double	getMinimalNodeDistance() Returns the minimum distance to be kept between any two nodes of the graph.
void	setMaximumDuration(long maximumDuration) Specifies the maximum duration in milliseconds that this layout stage is allowed to run.
void	setMinimalNodeDistance(double minimumNodeDistance) Sets the minimum distance to be kept between any two nodes of the graph.

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

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.

Constructor Detail

OrganicRemoveOverlapsStage

public OrganicRemoveOverlapsStage(Layouter core)

Creates a new instance of OrganicRemoveOverlapsStage with the given layout algorithm as core algorithm.

Parameters:

core - the core layout algorithm

OrganicRemoveOverlapsStage

public OrganicRemoveOverlapsStage()

Creates a new instance of OrganicRemoveOverlapsStage with default settings.

Method Detail

getMaximumDuration

public long getMaximumDuration()

Returns the maximum duration in milliseconds that this layout stage is allowed to run.

This maximum time does not include the time required for the core layout algorithm.

The duration needs to be non-negative.

Restricting the maximum duration may result in a worse layout quality, i.e., there could still be some node overlaps. Furthermore, the actual runtime may exceed the maximum duration since the algorithm still has to find a valid result.

Returns:

the non-negative maximum duration in milliseconds

See Also:

setMaximumDuration(long)

setMaximumDuration

public void setMaximumDuration(long maximumDuration)

Specifies the maximum duration in milliseconds that this layout stage is allowed to run.

This maximum time does not include the time required for the core layout algorithm.

The duration needs to be non-negative.

Restricting the maximum duration may result in a worse layout quality, i.e., there could still be some node overlaps. Furthermore, the actual runtime may exceed the maximum duration since the algorithm still has to find a valid result.

Default Value:

The default value is Long.MAX_VALUE.

Parameters:

maximumDuration - the non-negative maximum duration in milliseconds

Throws:

java.lang.IllegalArgumentException - if the specified duration has a negative value

getMinimalNodeDistance

public double getMinimalNodeDistance()

Returns the minimum distance to be kept between any two nodes of the graph.

Due to this distance not only nodes that overlap will be moved to resolve the overlap, but also nodes which are too close to each other with respect to this distance will be displaced.

The distance needs to be a non-negative value.

Returns:

the non-negative minimum node distance

See Also:

setMinimalNodeDistance(double)

setMinimalNodeDistance

public void setMinimalNodeDistance(double minimumNodeDistance)

Sets the minimum distance to be kept between any two nodes of the graph.

Due to this distance not only nodes that overlap will be moved to resolve the overlap, but also nodes which are too close to each other with respect to this distance will be displaced.

The distance needs to be a non-negative value.

Default Value:

The default value is 10.

Parameters:

minimumNodeDistance - the non-negative minimum node distance

Throws:

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

Sample Graphs:

Minimum distance 0

Minimum distance 20

canLayout

public boolean canLayout(LayoutGraph graph)

Accepts general graphs without exception.

Parameters:

graph - the input graph

Returns:

true for all inputs

See Also:

Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)

Removes node overlaps and displaces nodes of the given graph such that they keep the specified minimum distance to each other.

If a core layout algorithm is specified, it will be executed first.

The given graph will not be copied during the layout process and the layout will be immediately applied to the given graph.

Parameters:

graph - the input graph

See Also:

Layouter.canLayout(LayoutGraph)