y.layout.router
Class EdgeBundlingStage

java.lang.Object
  y.layout.AbstractLayoutStage
      y.layout.router.EdgeBundlingStage

All Implemented Interfaces:

Layouter, LayoutStage

public class EdgeBundlingStage
extends AbstractLayoutStage

A LayoutStage that bundles the edges of general undirected graphs to avoid visual cluttering.

Bundling together multiple edges means that their common parts are to some degree merged into a bundled part, which is a useful technique to increase the readability of straight-line graph drawings with a high number of edges that connect a comparably small number of nodes. This stage provides means to generate bundled edge paths for any given layout, i.e., the layout generated by a specified core layout algorithm. To determine whether two edges can be bundled, the algorithm computes a compatibility measure that is composed of various criteria (e.g. edges that are closer together or have similar length are more compatible). Note that this stage ignores the edge bends and handles them all as straight-lines. Furthermore, it doesn't prevent overlaps between nodes and edges.

A result of this stage with default settings

Concept

The implemented algorithm is based on the description in: "Force-directed Edge Bundling for Graph Visualization" by Danny Holten and Jarke J. van Wijk, in Computer Graphics Forum 28(3): 893-990, 2009.

The main idea of the algorithm is that the edges are subdivided into segments and between each pair of consecutive subdivision points spring and electrostatic forces are exerted. At each iteration step, each subdivision point is moved according to the combined force exerted on it. The algorithm runs in six cycles and starts with an initial number of subdivision points for each edge and an initial step size that determines the distance to which each subdivision point can be moved in the direction of the combined force (exerted on it) at each iteration step of the algorithm. After each cycle run, the value of the step size is halved.

Features

Global settings of the bundling can be configured using an EdgeBundling instance. In particular, it is possible to determine which of the edges are compatible and thus, can be bundled together by specifying the strength of the edge bundles using the EdgeBundling.getBundlingStrength() property. For the particular algorithm, the default value for this property is 0.4. The bundling quality is related to the distance to which a subdivision point can be moved at each iteration step of the algorithm. The default value is 1.

The individual style of each edge can be configured using an EdgeBundleDescriptor. A DataProvider can be registered with the input graph with key EdgeBundling.EDGE_BUNDLE_DESCRIPTOR_DPKEY to assign descriptors to edges. This allows, for example, to define which edges should actually be bundled.

To visualize better the result of the edge bundling algorithm, it is recommended that the edges are rendered using an opacity factor. In this manner, edges that are strongly bundled together will be emphasized more, in comparison to others that are not bundled.

This algorithm doesn't consider the current bends of the edges, i.e., it always handles them as straight-line. Furthermore, this stage doesn't prevent overlaps between nodes and edges.

Using high values of for the bundling strength can significantly affect the performance of the algorithm, especially for large graphs. A value close to 0.4 is recommended. On the other hand, using zero values for the bundling strength or the bundling quality leads to straight-line edges.

Complexity:

O(N * graph.E()^2 * K) where: N is the number of iterations and K the number of subdivision points per edge

Field Summary

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

EdgeBundlingStage()
Creates a new EdgeBundlingStage instance with default settings.

EdgeBundlingStage(Layouter core)
Creates a new EdgeBundlingStage instance with the given core layout algorithm and default settings.

Method Summary

boolean	canLayout(LayoutGraph graph) Accepts all graphs that are accepted by the core layout algorithm.
void	doLayout(LayoutGraph graph) Applies the edge bundling algorithm after invoking the core layout algorithm.
EdgeBundling	getEdgeBundling() Returns the EdgeBundling instance that defines the settings of the edge bundling feature.
long	getMaximumDuration() Returns the maximum duration in milliseconds that this bundling algorithm is allowed to run.
void	setMaximumDuration(long maximumDurationMillis) Specifies the maximum duration in milliseconds that this bundling algorithm is allowed to run.

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

Constructor Detail

EdgeBundlingStage

public EdgeBundlingStage()

Creates a new EdgeBundlingStage instance with default settings.

EdgeBundlingStage

public EdgeBundlingStage(Layouter core)

Creates a new EdgeBundlingStage instance with the given core layout algorithm and default settings.

Parameters:

core - the core layout algorithm

Method Detail

setMaximumDuration

public void setMaximumDuration(long maximumDurationMillis)

Specifies the maximum duration in milliseconds that this bundling algorithm is allowed to run.

The duration needs to be non-negative.

Restricting the maximum duration may result in a lower bundling quality. Furthermore, the real runtime may exceed the maximum duration since the algorithm still has to find a valid solution.

Default Value:

The default value is Long.MAX_VALUE. The bundling algorithm runs unrestricted.

Parameters:

maximumDurationMillis - the non-negative duration in milliseconds

Throws:

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

getMaximumDuration

public long getMaximumDuration()

Returns the maximum duration in milliseconds that this bundling algorithm is allowed to run.

The duration needs to be non-negative.

Restricting the maximum duration may result in a lower bundling quality. Furthermore, the real runtime may exceed the maximum duration since the algorithm still has to find a valid solution.

Returns:

the non-negative duration in milliseconds

See Also:

setMaximumDuration(long)

getEdgeBundling

public EdgeBundling getEdgeBundling()

Returns the EdgeBundling instance that defines the settings of the edge bundling feature.

The specified EdgeBundling defines global bundling properties. Settings for individual edges can be defined by assigning an EdgeBundleDescriptor to an edge using a DataProvider registered with key EdgeBundling.EDGE_BUNDLE_DESCRIPTOR_DPKEY.

By default, all edges are bundled (property EdgeBundleDescriptor.isBundled() of the default bundle descriptor is enabled). The default for EdgeBundling.getBundlingStrength() is 0.4 and the default for property EdgeBundling.getBundlingQuality() is 1.0.

Returns:

the EdgeBundling instance defining the edge bundling setup

canLayout

public boolean canLayout(LayoutGraph graph)

Accepts all graphs that are accepted by the core layout algorithm. If the core layout algorithm is null, every graph gets accepted.

Parameters:

graph - the graph.

Returns:

true if the core layout algorithm accepts the graph, false otherwise.

See Also:

Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)

Applies the edge bundling algorithm after invoking the core layout algorithm.

Parameters:

graph - the input graph

See Also:

Layouter.canLayout(LayoutGraph)